Игра(точней задачка) :)

← →
JediMaster (2004-02-06 20:49) [0]

Игра, в которой два участника по очереди берут из кучки от 1 до 3 камней, и проигрывает тот, кто взял последний камень. Мы немного обобщим эту задачу: будем считать, что оба игрока могут брать не по 1, 2, 3 камня, а по k1, k2,..., km камней. Нас опять будет интересовать вопрос, кто из игроков выигрывает при правильной игре. Гарантируется, что вне зависимости от уже сделанных игроками ходов, всегда возможно сделать очередной ход.

Как определить, какой игрок выиграл, 1(делал ход первым) или 2(делал ход вторым) с тем учетом, что игроки играли правильно !!!!!!
У меня вариянтов нет! :(

← →
Cr@sh (2004-02-06 21:09) [1]

Там есть ряд конечных критичных чисел, которое должно выпасть одному из игроков для гарантированой победы.
в идеале это 2k+1... тогда игрок берет k камней, остается k+1, тогда сколько бы не взял другой - первый выиграет, тк ему последний камень не достанется точно.
Это число может доходит до 3k, но там уже нужно смотреть на алгоритм дальнейшей игры.

Вывод: вне зависимости от начала игры, нужно стремиться чтобы тебе досталось 2k+1 камней.

k - max кол-во камней, которое может взять один игрок за один раз.

← →
Юрий Зотов (2004-02-06 21:19) [2]

Пусть N - первоначальное число камней, M - максимальное число камней, которое один игрок может взять за ход. Пойдем от конца игры.

Если перед последним ходом первого игрока в куче осталось M+1 камней, то проигрывает второй игрок. Значит, первый игрок должен стремиться свести игру к этой ситуации.

Она достигается, если перед ПРЕДпоследним ходом первого игрока в куче осталось 2*(M+1) камней. И т.д. - если перед любым ходом первого игрока число камней в куче кратно M+1, то выигрывает первый игрок, если нет - то второй игрок перехватывает инициативу, сводит игру к той же самой цепочке и выигрывает.

Отсюда вытекает правильная стратегия игроков и решение задачи.

Игра(точней задачка) :) Найти похожие ветки