Разделы 
Дополнительно
Задача по математике - 3294
2019-06-02 
Двое играют в следующую игру: первый выписывает в ряд по своему желанию буквы $А$ или $Б$ (слева направо, одну за другой; по одной букве за ход), а второй после каждого хода первого меняет местами любые две из выписанных букв или ничего не меняет (это тоже считаться ходом). После того, как оба игрока сделают по 1999 ходов, игра заканчивается. Может ли второй играть так, чтобы при любых действиях первого игрока в результате получился палиндром (т. е. слово, которое читается одинаково слева направо и справа налево)?
Решение:
Приведем стратегию второго игрока. Первые 1000 ходов он пропускает. Ход с номером $k+1000$ он делает так, чтобы последние $2k + 1$ букв образовывали палиндром. Докажем, что он всегда может это сделать.
Для этого проведем индукцию по $k$. При $k = 0$ это очевидно. Пусть после $(k-1) + 1000$ ходов последние $2k - 1$ букв образуют палиндром. Если приписанная первым игроком $(1000+k)$-я буква совпадает с $(1000-k)$-й буквой, то второму игроку ничего делать не нужно.
Если же $(1000+k)$-я и $(1000-k)$-я буквы различны, то одна из них не совпадает с буквой, стоящей на 1000-м месте. Второй игрок меняет ее с 1000-й буквой. При этом палиндром из $2k - 1$ буквы не разрушится, потому что второй игрок изменил его серединную букву. Итак, последние $2k + 1$ букв образуют палиндром.
После 1999 ходов все слово будет палиндромом.
Ответ: Может.
Двое играют в следующую игру: первый выписывает в ряд по своему желанию буквы $А$ или $Б$ (слева направо, одну за другой; по одной букве за ход), а второй после каждого хода первого меняет местами любые две из выписанных букв или ничего не меняет (это тоже считаться ходом). После того, как оба игрока сделают по 1999 ходов, игра заканчивается. Может ли второй играть так, чтобы при любых действиях первого игрока в результате получился палиндром (т. е. слово, которое читается одинаково слева направо и справа налево)?
Решение:
Приведем стратегию второго игрока. Первые 1000 ходов он пропускает. Ход с номером $k+1000$ он делает так, чтобы последние $2k + 1$ букв образовывали палиндром. Докажем, что он всегда может это сделать.
Для этого проведем индукцию по $k$. При $k = 0$ это очевидно. Пусть после $(k-1) + 1000$ ходов последние $2k - 1$ букв образуют палиндром. Если приписанная первым игроком $(1000+k)$-я буква совпадает с $(1000-k)$-й буквой, то второму игроку ничего делать не нужно.
Если же $(1000+k)$-я и $(1000-k)$-я буквы различны, то одна из них не совпадает с буквой, стоящей на 1000-м месте. Второй игрок меняет ее с 1000-й буквой. При этом палиндром из $2k - 1$ буквы не разрушится, потому что второй игрок изменил его серединную букву. Итак, последние $2k + 1$ букв образуют палиндром.
После 1999 ходов все слово будет палиндромом.
Ответ: Может.
