Покори Воробьёвы горы! 2023, 9 класс, задача 5
Алиса и Боря по очереди зачеркивают буквы в надписи «Покори Воробьевы горы». За ход разрешается зачеркнуть одну букву или несколько одинаковых букв (большие и маленькие буквы не различаются). Проигрывает тот, кто не может сделать ход. Алиса ходит первой. Есть ли у одного из игроков стратегия, гарантированно позволяющая выиграть?
Ответ: Да, Алиса первым ходом зачеркивает буквы «О».
Решение. В надписи букв «О», «Р», «В», «Ы» и по одной «Б», «Г», «Е», «И», «К», «П», «Ь».
Для краткости запишем это в виде и будем называть этот набор чисел позицией игры. Заметим, что если позиция симметрична (например ), то начинающий с этой позиции игрок проигрывает, т.к. второй может просто повторять его ходы. Первый ход Алисы приводит к позиции . Рассмотрим, как может пойти Боря:
Удалить группу размера и получить позицию . Тогда Алиса удаляет одну букву (и группы размера ) и получает симметричную позицию .
Удалить буквы из группы размера , позиция . Тогда удалив буквы, Алиса получит симметричную позицию .
Удалить одну букву из группы размера . Получаем , из которого можно получить .
Удалить группу размера и получить . Тогда Алиса удаляет буквы из первой группы и получает .
Удалить одну букву из группы размера и получить . Тогда удаляем первую группу и получаем .
Удалить букву из группы размера и получить . Удалив одну букву из первой группы получим .