theJam.ru

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

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

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

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

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

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

  1. nogard пишет:

    Условие победы 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. SoVictor пишет:

    Совершенно верно и ничего лишнего, браво

  3. Iney пишет:

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

Комментировать!

Друзья, обращаю ваше внимание, что все бессмысленные и пустые сообщения будут удаляться, ровно как и комментарии с заведомо не существующми e-mail адресами. Спасибо!


Случайное:
ОБЗОР ИГРЫ ASSASIN’S CREED ROGUE
Assassin’s Creed Rogue, последняя на сегодняшний день «полноценная», если так можно сказать, часть и
Полезные советы перед началом прохождения The Witcher 3
Относительно недавно состоялся выход, наверное, одной из самых ожидаемых игр как в жанре RPG, так
История возникновения компьютерных игр
Многие пользователи интересуются феноменом огромной популярности индии - игр, несмотря на то, что мн
Обзор Игры FAR CRY 3
Far Cry 3 – это игра, которая у многих ассоциируется всего лишь с одним словом – «безумие». Мы играе
Какие бывают на данный момент типы компьютерных игр?
Классификация компьютерных игр – это достаточно спорный вопрос, поскольку на данный момент предостав


 
2005-2011 theДжем.ru - сайт для тех, кто умеет читать и думать. ↑ вверх
полезно знать