Задача 3. Игра с числом 9999

Безопасные ходы и тупики

Назовём ход безопасным, если после него число не меньше $2024$. Проигрывает тот, кто первым сделает небезопасный ход. Пока у игрока есть безопасный ход, проигрывать ему незачем: делать небезопасный ход вынужден только тот, у кого безопасных ходов нет.

Число не меньше $2024$, из которого любой ход делает число меньше $2024$, назовём тупиком. Кто начинает свой ход в тупике, тот проигрывает.

Игра не может длиться вечно: каждый ход уменьшает одну цифру на $1$, поэтому сумма цифр уменьшается на $1$. В начале она равна $9+9+9+9=36$, так что больше $36$ ходов быть не может, и кто-то обязательно сделает число меньше $2024$.

Значит, чтобы доказать, что выигрывает первый, достаточно придумать для него способ игры, при котором перед каждым его ходом у него есть безопасный ход (и он его делает). Тогда сам он ниже $2024$ никогда не опустится, и это сделает второй.

Зачем так переформулировать: вопрос «кто первым опустится ниже 2024» превращается в вопрос «кому достанется тупик». Тупики — это концы игры, с них и начнём.

Все тупики: их ровно четыре

Пусть на доске число не меньше $2024$. Будем пробовать ходы, которые уменьшают число меньше всего: сначала единицы (число уменьшается на $1$), потом десятки (на $10$), сотни (на $100$), тысячи (на $1000$).

• Единиц не $0$. Уменьшим единицы — число уменьшится на $1$. Оно останется не меньше $2024$, если было не меньше $2025$. Не подходит только само $2024$. И $2024$ действительно тупик: его ходы — $1024$, $2014$ и $2023$ (сотни равны $0$, их уменьшать нельзя), все меньше $2024$.
• Единиц $0$, десятков не $0$. Уменьшим десятки: число уменьшится на $10$ и останется не меньше $2024$, если было не меньше $2034$. Среди чисел от $2024$ до $2033$ на ноль оканчивается только $2030$. Его ходы — $1030$ и $2020$, оба меньше $2024$: это тупик.
• Единиц и десятков $0$, сотен не $0$. Уменьшим сотни: минус $100$, безопасно, если число не меньше $2124$. Среди чисел от $2024$ до $2123$ на $00$ оканчивается только $2100$. Его ходы — $1100$ и $2000$: тупик.
• Сотни, десятки и единицы — нули. Тогда число — одно из $3000$, $4000$, …, $9000$; число $2000$ не подходит, оно меньше $2024$. Уменьшить можно только тысячи. Из $4000$ и больших чисел получится не меньше $3000$ — безопасно, а из $3000$ получится $2000$: тупик.

Других случаев нет. Итак, тупиков ровно четыре: 2024, 2030, 2100 и 3000 (рисунок ниже). Из любого другого числа не меньше $2024$ есть безопасный ход.

Сумма цифр подсказывает, чей ход

Каждый ход уменьшает одну цифру на $1$, поэтому сумма цифр каждый раз уменьшается ровно на $1$. Первый делает ход при сумме $36$, второй — при $35$, первый — при $34$, и так далее. Значит, перед ходом первого сумма цифр всегда чётная, а перед ходом второго — нечётная.

Посчитаем суммы цифр тупиков: у $2024$ это $2+0+2+4=8$, у $2030$ — $5$, у $2100$ — $3$, у $3000$ — $3$. Тупики $2030$, $2100$ и $3000$ с нечётной суммой могут достаться только второму! Для первого опасен единственный тупик — $2024$.

Но одной чётности мало: второй может сам привести первого к числу $2024$. Например, пусть перед ходом первого на доске $2035$ (сумма цифр $10$, чётная). Тысячи уменьшать нельзя — получится $1035$, сотни равны $0$. Остаются два безопасных хода: в $2034$ или в $2025$. А из каждого из этих чисел второй ходит в $2024$, и первый оказывается в тупике (рисунок ниже).

Вывод: первый выиграет, если позаботится о числе $2024$ заранее.

Стратегия первого: убрать 2024 из игры

Число $2024$ оканчивается на $4$. Цифры только уменьшаются, поэтому, как только цифра единиц станет $3$ или меньше, число $2024$ появиться уже не сможет.

Первый игрок так и делает: пока цифра единиц не меньше $4$, он своим ходом уменьшает цифру единиц. В начале единиц $9$, поэтому хватит не больше шести его ходов ($9\to3$). Если второй тоже уменьшает единицы, получится ещё быстрее.

Не проиграет ли первый в это время? Перед его шестым (или более ранним) ходом второй успел сделать не больше пяти ходов и мог уменьшить цифру тысяч самое большее до $9-5=4$. Первый меняет только единицы, поэтому после его хода цифра тысяч не меньше $4$, а число не меньше $4000$. Значит, все эти ходы первого безопасны.

Дальше годится любой безопасный ход

Когда цифра единиц стала не больше $3$, первый делает любой безопасный ход. Почему он у него всегда найдётся? Посмотрим на число перед его ходом.

• Оно не меньше $2024$ — иначе второй уже проиграл.
• Сумма его цифр чётная (шаг 3), поэтому это не $2030$, не $2100$ и не $3000$.
• Это и не $2024$: цифра единиц не больше $3$.

По шагу 2 других тупиков нет, значит, у первого есть безопасный ход. Итак, первый ни разу не сделает число меньше $2024$ — ни в начале (шаг 4), ни потом. А игра не бесконечна (шаг 1), поэтому меньше $2024$ число сделает второй. Значит, при правильной игре выигрывает тот, кто делает первый ход.