Олимпиада имени Леонарда Эйлера 2024-2025 учебный год, I тур заключительного этапа

Тақтада 9999 саны жазылған. Бір жүрісте осы төрт цифрдың кез келген біреуін 1-ге азайтуға болады (бірақ цифрды нөлден кіші қылуға болмайды). Екі ойыншы кезекпен жүріс жасайды. Қай ойыншы алғаш рет 2024-тен кіші санын алса, сол ойыншы ұтылады. Дұрыс ойында қай ойыншы ұтады: бірінші болып жүретін ойыншы ма, әлде оның қарсыласы ма? ( И. Рубанов )

Комментарий/решение

1 выйграет

Рассмотрим все числа, где тот, чья очередь

ходить, сразу проигрывает. Это 3000, 2100, 2030 и 2024. Так как сумма цифр исходного

числа 9999 четна, и каждый ход меняет четность суммы цифр, в трех первых позициях, у

которых сумма цифр нечетна, очередь хода за вторым. Значит, первый победит, если не

допустит появления в игре числа 2024. Для этого ему достаточно не более чем шестью

своими первыми ходами уменьшать на 1 последнюю цифру, пока она не станет меньше 4

(при этом он не проиграет, так как даже после его шестого хода первая цифра останется

не меньше 4). После этого он может делать любые не проигрывающие немедленно ходы

и, как уже объяснено выше, гарантированно выиграет.

очевидно что терминальными числами могут являтся числа $2100, 2030, 2024, 3000$. Что бы достичь $2024$ требуется четное кол-во ходов, а для остальных нечетное кол-во ходов, Т.Е. только если достичь $2024$ выигрывает второй игрок, тогда тактикой для первого игрока будет менять цифру единиц , пока она не станет $< 4$ , и он может это сделать так как требуется как минимум $6$ ходов , а для других чисел сделав $6$ ходов они не станут меньше $3$, и число не станет меньше $2024$, тогда очевидно что терминальным числом теперь могут являться числа $2100, 2030, 3000$ при которых выигрывает первый игрок.

(в самой олимпиаде не требуется доказывать что 2100, 2030, 3000, 2024 являются единственными терминальными числами)