Олимпиадная задача по теории алгоритмов для 7-9 классов: симметрия двоичной строки
Задача
Играют двое. Первый выписывает в строку слева направо цифры, произвольно чередуя 0 и 1, пока цифр не станет всего 1999. Каждый раз после того, как первый выписал очередную цифру, второй меняет между собой две цифры из уже написанного ряда (когда написана только одна цифра, второй пропускает ход). Всегда ли второй может добиться того, чтобы после его последнего хода расположение цифр было симметричным относительно средней цифры?
Решение
Второй, например, может действовать так. До 1000-й цифры он ходит произвольно. Когда первый напишет 1001-ю цифру, второй сравнивает её с 999-й (симметричной относительно 1000-й цифры). Если эти цифры совпадают, второй меняет их местами. Если же 1001-я и 999-я цифры разные, то одна из них не совпадает с 1000-й цифрой. Тогда второй меняет эту цифру с 1000-й.
В любом случае после хода второго 1001-я цифра совпадает с 999-й. Аналогично второй действует и дальше, добиваясь совпадения 1002-й и 998-й, ..., 1999-й и 1-й цифр.
Ответ
Всегда.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь