|
|
 |
Условие
На доске можно либо написать две единицы, либо стереть любые два уже написанных одинаковых числа n и написать вместо них числа n + 1 и n – 1. Какое минимальное количество таких операций требуется, чтобы получить число 2005? (Сначала доска была чистой.)
Решение
При каждой операции сумма S квадратов всех чисел увеличивается на 2. В частности, она всегда чётна.
Пусть 2005 получено за минимальное количество операций (ходов). Предположим, что в этот момент на доске отсутствует натуральное число n < 2004. Рассмотрим момент, когда n в последний раз было стёрто (очевидно, когда-то оно присутствовало). В этот момент появились числа n + 1 и
n – 1, но далее ни одно из них не "использовалось" (иначе n снова бы появилось). Это противоречит минимальности: указанный ход оказался ненужным.
Итак, в последний момент на доске присутствуют числа 2005, 2003, 2002, ..., 2, 1. Кроме них на доске должно присутствовать ещё хотя бы одно ненулевое число, поскольку сумма квадратов указанных чисел нечётна.
Следовательно, в последний момент S ≥ 2005² + 2003² + 2002² + ... + 2² + 1 + 1, а число ходов не меньше ½ (2005² + 2003² + 2002² + ... + 2² + 1 + 1).
Докажем, что можно получить набор чисел, соответствующий такому числу ходов, то есть 1, 1, 2, ..., 2003, 2005 и некоторое количество нулей (количество нулей можно указать точно, так как количество чисел на доске всегда равно их сумме).
Обозначим через (1) набор чисел, состоящий из одной или двух единиц и нескольких нулей. Назовем сдвигом последовательность операций, позволяющую из позиции (1), 2, 3, ..., n – 1, n получить позицию (1), 2, 3, ..., n – 1, n + 1. Чтобы осуществить сдвиг, нужно из двух единиц (если (1) содержит одну единицу, добавим предварительно две единицы) получить двойку, затем из двух двоек – 3 и 1, из двух троек – 4 и 2...
Покажем теперь, как осуществить расширение: из позиции (1), 2, 3, ..., n, n + 2 получить позицию (1), 2, 3, ..., n + 1, n + 3. Для этого сначала проведём n – 1 сдвиг: превратим n в n + 1, затем n – 1 – в n, ..., 2 – в 3. В результате получим позицию (1), 3, 4, ..., n + 1, n + 2. Теперь превратим две единицы в двойку и проведём заключительный сдвиг.
За пять ходов из пустой доски нетрудно получить позицию 0, 0, 1, 3, то есть (1), 3. Применив к ней 2002 раза расширение, получим, наконец, позицию (1), 2, ..., 2003, 2005.
Ответ
1342355520 = ½ (2005² + 2003² + 2002² + ... + 2² + 1 + 1).
Замечания
8 баллов
