Логические задачи → Задача из теории игр - 1

21 мая 2010 | Добавил: SoVictor

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

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

Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку

Версия для печати.
RSS комментариев записи.

Метки → логические игры, математические, теория игр

Комментариев: 3

nogard пишет:
21 мая 2010 в 14:39

Условие победы 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 игрок.
SoVictor пишет:
21 мая 2010 в 21:43

Совершенно верно и ничего лишнего, браво
Iney пишет:
28 мая 2010 в 22:59

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