Из первых 22 натуральных чисел 1, 2, …, 22 выбрали 2k различных чисел. Выбранные числа разбили на пары и посчитали суммы чисел в каждой паре. Оказалось, что все полученные суммы различны и не превосходят 27.
а) Может ли получиться так, что сумма всех 2k выбранных чисел равняется 170 и в каждой паре одно из чисел ровно в три раза больше другого?
б) Может ли число k быть равным 11?
в) Найдите наибольшее возможное значение числа k.
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Если в паре числа x и rx, её сумма равна (r+1)x. Поэтому общая сумма должна делиться на r+1. При делимости достаточно всех x≤⌊rN⌋, с (r+1)x≤Q, и всех поднаборов этих пар: проверяем непересечение чисел, разные суммы и нужную общую сумму. Область конечна.
R=3
T=170
Шаг 2. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. Сумма 2k разных натуральных чисел не меньше k(2k+1). При разных суммах пар, не больших Q, их общая сумма не больше kQ−2k(k−1). Следовательно, 5k≤2Q−1. Также 2k≤N. Это даёт верхнюю границу числа пар.
N=22
R=27
Шаг 2. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. Сумма 2k разных натуральных чисел не меньше k(2k+1). При разных суммах пар, не больших Q, их общая сумма не больше kQ−2k(k−1). Следовательно, 5k≤2Q−1. Также 2k≤N. Это даёт верхнюю границу числа пар.
Шаг 2. В конечном наборе 1,…,N поочерёдно берём наименьшее ещё не рассмотренное число. Либо не используем его, если остаётся достаточно чисел, либо образуем пару с одним из оставшихся. Исключаем только суммы выше Q и уже использованные суммы. Так охвачены все непересекающиеся пары с разными суммами. Приведённый набор достигает доказанной верхней границы.