Разные суммы непересекающихся пар

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Одинаковое кратное в каждой паре
  2. Ответ: нет

    Сначала: Одинаковое кратное в каждой паре

  3. Граница количества пар

    Сначала: Ответ: нет

  4. Ответ: нет

    Сначала: Граница количества пар

  5. Граница количества пар

    Сначала: Ответ: нет

  6. Достижение верхней границы пар

    Сначала: Граница количества пар

  7. Ответ

    Сначала: Достижение верхней границы пар

Разобранный пример

Из первых 22 натуральных чисел 1, 2, …, 22 выбрали 2k2k различных чисел. Выбранные числа разбили на пары и посчитали суммы чисел в каждой паре. Оказалось, что все полученные суммы различны и не превосходят 27.

а) Может ли получиться так, что сумма всех 2k2k выбранных чисел равняется 170 и в каждой паре одно из чисел ровно в три раза больше другого?

б) Может ли число kk быть равным 11?

в) Найдите наибольшее возможное значение числа kk.

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Если в паре числа xx и rxrx, её сумма равна (r+1)x(r+1)x. Поэтому общая сумма должна делиться на r+1r+1. При делимости достаточно всех x≤⌊Nr⌋x\leq\left\lfloor \frac{N}{r}\right\rfloor, с (r+1)x≤Q(r+1)x\leq Q, и всех поднаборов этих пар: проверяем непересечение чисел, разные суммы и нужную общую сумму. Область конечна.
R=3R=3
T=170T=170
Шаг 2. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. Сумма 2k2k разных натуральных чисел не меньше k(2k+1)k(2k+1). При разных суммах пар, не больших QQ, их общая сумма не больше kQ−k(k−1)2kQ-\frac{k(k-1)}{2}. Следовательно, 5k≤2Q−15k\leq 2Q-1. Также 2k≤N2k\leq N. Это даёт верхнюю границу числа пар.
N=22N=22
R=27R=27
Шаг 2. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. Сумма 2k2k разных натуральных чисел не меньше k(2k+1)k(2k+1). При разных суммах пар, не больших QQ, их общая сумма не больше kQ−k(k−1)2kQ-\frac{k(k-1)}{2}. Следовательно, 5k≤2Q−15k\leq 2Q-1. Также 2k≤N2k\leq N. Это даёт верхнюю границу числа пар.
Шаг 2. В конечном наборе 1, …, N1,\,\ldots,\,N поочерёдно берём наименьшее ещё не рассмотренное число. Либо не используем его, если остаётся достаточно чисел, либо образуем пару с одним из оставшихся. Исключаем только суммы выше QQ и уже использованные суммы. Так охвачены все непересекающиеся пары с разными суммами. Приведённый набор достигает доказанной верхней границы.
T=((1;22);(2;20);(3;21);(4;17);(5;15);(6;19);(7;12);(8;9);(10;16);(13;14))\mathcal T=\left(\left(1;22\right);\left(2;20\right);\left(3;21\right);\left(4;17\right);\left(5;15\right);\left(6;19\right);\left(7;12\right);\left(8;9\right);\left(10;16\right);\left(13;14\right)\right)
Шаг 3. Записываем полученное значение.
1010

Открыть задачу целиком

Попробовать самостоятельно