На доске написано несколько различных натуральных чисел, причем любые два из них отличаются не более чем в 3 раза.
а) Может ли на доске быть написано 5 чисел, сумма которых равна 47?
б) Может ли на доске быть написано 10 чисел, сумма которых равна 94?
в) Сколько чисел может быть написано на доске, если их произведение равно 8000?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Пусть из k различных чисел наименьшее m, а все не превосходят 3m. В отрезке [m,3m] только 2m+1 целых чисел, поэтому 2m+1≥k. Кроме того, их сумма не меньше km+2k(k−1). При заданной сумме T это даёт конечный диапазон m; для каждого m выбираем k−1 разных чисел от m+1 до 3m с суммой T−m.
k=5
T=47
Шаг 2. Показываем найденное распределение или набор.
T=(5;9;10;11;12)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Пусть из k различных чисел наименьшее m, а все не превосходят 3m. В отрезке [m,3m] только 2m+1 целых чисел, поэтому 2m+1≥k. Кроме того, их сумма не меньше km+2k(k−1). При заданной сумме T это даёт конечный диапазон m; для каждого m выбираем k−1 разных чисел от m+1 до 3m с суммой T−m.
k=10
T=94
Шаг 2. Показываем найденное распределение или набор.
T={}
Шаг 3. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. Каждое исходное число является делителем заданного произведения P. Выбираем их строго по возрастанию, деля остаток произведения на очередной множитель; наибольший множитель не больше утроенного первого. При достижении остатка 1 получен набор. Эта конечная рекурсия охватывает все разложения на разные натуральные множители, поэтому таблица даёт все возможные количества чисел.