пятница, 5 декабря 2014 г.

0 и 9

Играют двое. Ходят по очереди. Первому игроку разрешается за один ход записать на доске одну из цифр, 0 или 9, в одну строчку слева направо. Второй игрок за свой ход должен поменять любые две цифры существующего ряда местами (если на доске одна цифра, то он пропускает ход). Игра заканчивается, когда на доске будет записано 99 цифр. Если получившийся ряд симметричен относительно средней цифры, то выигрывает второй игрой. Если не симметричен, то побеждает первый. Существует ли выигрышная стратегия у второго игрока и как он должен играть?
update
Первый - Константин Кноп.
Ответ
Существует.
Первые 50 ходов можно играть как угодно. После этого используем такую стратегию. Пусть i>50 - номер хода. Если i-я и (100-i)-я цифра совпадают, то можно их поменять местами, все равно это ничего не меняет. Если не совпадают, то одна из них не равна 50-й цифре, и ее можно поменять с 50-й цифрой. Итог перестановки - i-я и (100-i)-я цифра равны. Поскольку это верно для всех i>50, то ряд будет симметричным.

Похожее - игра с 999 спичками.

2 комментария:

  1. Первые 50 ходов можно играть как угодно. После этого используем такую стратегию. Пусть i>50 - номер хода. Если i-я и (100-i)-я цифра совпадают, то можно их поменять местами, все равно это ничего не меняет.
    Если не совпадают, то одна из них не равна 50-й цифре, и ее можно поменять с 50-й цифрой. Итог перестановки - i-я и (100-i)-я цифра равны.
    Поскольку это верно для всех i>50, то ряд будет симметричным

    ОтветитьУдалить