На доске написаны числа 1, 2, 3,…, 30. За один ход разрешается стереть три числа, сумма которых меньше 35 и отлична от каждой из сумм троек чисел, стёртых на предыдущих ходах.
а) Приведите пример 5 ходов.
б) Можно ли сделать 10 ходов?
в) Какое наибольшее число ходов можно сделать?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Для достижения границы используем 3k наименьших чисел. Берём наименьшее свободное число и любую пару из остальных, если сумма меньше H и ещё не встречалась. Каждое разбиение обязательно содержит такую тройку с наименьшим числом, поэтому этот конечный поиск охватывает все разбиения. Если сумма ещё свободных чисел выше суммы максимально возможных различных оставшихся сумм троек, ветвь невозможна. Приведённые тройки достигают границы.
Шаг 2. Приводим полученный набор, параметры или распределение.
Шаг 1. За k ходов стираются 3k разных натуральных чисел с общей суммой не меньше 23k(3k+1). Разные целые суммы троек, меньшие H, имеют общую сумму не больше k(H−1)−2k(k−1). Сравнение этих границ даёт 5k≤H−2. Также 3k не больше количества чисел на доске.
Шаг 2. Нет. Доказанная граница исключает возможность.
Шаг 1. За k ходов стираются 3k разных натуральных чисел с общей суммой не меньше 23k(3k+1). Разные целые суммы троек, меньшие H, имеют общую сумму не больше k(H−1)−2k(k−1). Сравнение этих границ даёт 5k≤H−2. Также 3k не больше количества чисел на доске.
Шаг 2. Для достижения границы используем 3k наименьших чисел. Берём наименьшее свободное число и любую пару из остальных, если сумма меньше H и ещё не встречалась. Каждое разбиение обязательно содержит такую тройку с наименьшим числом, поэтому этот конечный поиск охватывает все разбиения. Если сумма ещё свободных чисел выше суммы максимально возможных различных оставшихся сумм троек, ветвь невозможна. Приведённые тройки достигают границы.