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

0 и 9

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

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

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

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

    ОтветитьУдалить
  2. The way this problem sounds, the game ends withe the first player writing the 99th digit. Hence this player can always choose a digit different from the first one. If you want your strategy to work, you must explicitly state that the second player is allowed his step after the 99th digit is written.

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