Задача из теории игр — 1 | Логические задачи

В кучке n > 1 камней. Двое игроков ходят по очереди. За один ход игроку разрешается взять от 1 до k < n камней. Выигрывает тот, кто взял последний камень.

При всех k и n определить выигрышную стратегию и игрока, выигрывающего при правильной игре.

Задача из теории игр — 1 | Логические задачи: 3 комментария

  1. Условие победы 2 игрока n = 0 (mod k+1) (под знаком = подразумевается знак сравнимости)
    Во все остальных случаях побеждает 1 игрок.
    Стратегии таковы:
    1) Общая часть разделим все камни на кучки по k+1 камень.
    Собственно условие говорит, что если все камни разделились на такие кучки, то побеждает 2 игрок, а если после деления осталась кучка где меньше k+1 камня, то первый.
    2) Пусть разделились (стратегия за 2 игрока).
    Из какой бы кучки не брал 1 игрок сколько угодно камней, второй своим ходом забирает оставшиеся камни. Таким образом каждый «полный» ход (ход 1 + ход 2) у нас уменьшается количество кучек. Итого останиться 1 кучка — k+1 камень из которой первый вынужден забрать сколько камней, а второй забирает себе все остальное, тем самым, выигрывая.
    3) Не разделились (стратегия за 1 игрока).
    Тогда есть кучка, где меньше k+1 камней => 1 игрок своим первым ходом забирает ее всю. Теперь формально игроки поменялись местами и получился предыдущий случай. В нем выибрывает 2, а в силу того, что они поменялись, то это изначальный 1 игрок.

  2. А я такое, помнится, на калькуляторе программировал. А потом приходилось читить, т.к. он всегда выбирал, кто будет первым ходить и, соответственно, выигрывал 🙂

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *