Стирание троек с разными суммами

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

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

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

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

  1. Построение стираемых троек
  2. Конструкция и точный результат

    Сначала: Построение стираемых троек

  3. Верхняя граница количества ходов

    Сначала: Конструкция и точный результат

  4. Ответ: нет

    Сначала: Верхняя граница количества ходов

  5. Верхняя граница количества ходов

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

  6. Построение стираемых троек

    Сначала: Верхняя граница количества ходов

  7. Ответ

    Сначала: Построение стираемых троек

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

На доске написаны числа 1, 2, 3,…, 30. За один ход разрешается стереть три числа, сумма которых меньше 35 и отлична от каждой из сумм троек чисел, стёртых на предыдущих ходах.

а) Приведите пример 5 ходов.

б) Можно ли сделать 10 ходов?

в) Какое наибольшее число ходов можно сделать?

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

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

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

Шаг 1. Для достижения границы используем 3k3k наименьших чисел. Берём наименьшее свободное число и любую пару из остальных, если сумма меньше HH и ещё не встречалась. Каждое разбиение обязательно содержит такую тройку с наименьшим числом, поэтому этот конечный поиск охватывает все разбиения. Если сумма ещё свободных чисел выше суммы максимально возможных различных оставшихся сумм троек, ветвь невозможна. Приведённые тройки достигают границы.
Шаг 2. Приводим полученный набор, параметры или распределение.
T=((1;2;8);(3;9;18);(4;10;17);(5;11;16);(6;12;15))\mathcal T=\left(\left(1;2;8\right);\left(3;9;18\right);\left(4;10;17\right);\left(5;11;16\right);\left(6;12;15\right)\right)
Шаг 1. За kk ходов стираются 3k3k разных натуральных чисел с общей суммой не меньше 3k(3k+1)2\frac{3k(3k+1)}{2}. Разные целые суммы троек, меньшие HH, имеют общую сумму не больше k(H−1)−k(k−1)2k(H-1)-\frac{k(k-1)}{2}. Сравнение этих границ даёт 5k≤H−25k\leq H-2. Также 3k3k не больше количества чисел на доске.
Шаг 2. Нет. Доказанная граница исключает возможность.
Шаг 1. За kk ходов стираются 3k3k разных натуральных чисел с общей суммой не меньше 3k(3k+1)2\frac{3k(3k+1)}{2}. Разные целые суммы троек, меньшие HH, имеют общую сумму не больше k(H−1)−k(k−1)2k(H-1)-\frac{k(k-1)}{2}. Сравнение этих границ даёт 5k≤H−25k\leq H-2. Также 3k3k не больше количества чисел на доске.
Шаг 2. Для достижения границы используем 3k3k наименьших чисел. Берём наименьшее свободное число и любую пару из остальных, если сумма меньше HH и ещё не встречалась. Каждое разбиение обязательно содержит такую тройку с наименьшим числом, поэтому этот конечный поиск охватывает все разбиения. Если сумма ещё свободных чисел выше суммы максимально возможных различных оставшихся сумм троек, ветвь невозможна. Приведённые тройки достигают границы.
T=((1;2;8);(3;9;18);(4;10;17);(5;11;16);(6;12;15);(7;13;14))\mathcal T=\left(\left(1;2;8\right);\left(3;9;18\right);\left(4;10;17\right);\left(5;11;16\right);\left(6;12;15\right);\left(7;13;14\right)\right)
Шаг 3. Записываем полученный ответ.
66

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

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