|
|
 |
Условие
Придя в школу, Коля и Алиса обнаружили на доске надпись: "ГОРОДСКАЯ УСТНАЯ ОЛИМПИАДА". Они договорились сыграть в следующую игру: за один ход в этой надписи разрешается стереть произвольное количество одинаковых букв, а выигрывает тот, кто стирает последнюю букву. Первым ходил Коля и стёр последнюю букву "А". Как надо играть Алисе, чтобы обеспечить себе выигрыш?
Решение
Назовём кратностью буквы то количество раз, в котором эта буква встречается в надписи. После хода Коли, буквы "А" и "О" имеют кратность 3, буквы "Д", "И", "С" и "Я" – кратность 2, а буквы "Г", "К", "Л", "М", "Н", "П", "Р", "Т" и "У" – кратность 1. Для того, чтобы выиграть, Алисе надо сначала стереть любую букву кратности 1, чтобы количество букв каждой кратности стало чётным. Далее Алисе надо играть так, чтобы после каждого её хода количество букв каждой кратности было чётным. Для этого ей следует в ответ на каждый Колин ход стирать такое же количество букв той же кратности. Например, если Коля сотрёт три буквы "А", то Алиса должна стереть три буквы "О", а если Коля сотрёт одну букву "Д", то Алиса может стереть также одну букву "И". Тогда на каждый ход Коли у Алисы будет ответный ход, поэтому именно она сделает последний ход и выиграет.
Замечания
Наглядно эту стратегию можно представить, например, так. Пусть Алиса мысленно упорядочит буквы по-другому: "АААДДИИКЛМНГПРТУССЯЯООО". Тогда первым своим ходом она стирает букву "Г", а далее делает ходы, симметричные ходам Коли относительно середины этого "слова".
