Есть две кучи по восемь камней в каждой. За ход разрешается взять любое количество камней из одной кучи или по два камня из обеих куч. В игре участвуют два игрока. кто выиграет при правильной игре?
Напишите, пожалуйста, выигрышную стратегию.

задан 8 Янв '14 21:07

10|600 символов нужно символов осталось
3

Здесь в условии не сказано, что проигрывает тот, у кого нет возможности сделать ход. Я буду исходить из такого предположения.

Назовём игровую позицию критической, если тот, кто делает в ней первый ход, проигрывает при правильной игре оппонента. Для выявления того, как выглядит выигрышная стратегия, достаточно знать все критические позиции. Тогда стратегия будет состоять в том, чтобы предлагать оппоненту оказаться в одной из критических позиций. Если этого добиться нельзя, то сама анализируемая позиция будет критической.

По определению, позиция 0;0 будет критической (позицию обозначаем как пару чисел, означающих количество камней в кучках). Соответственно, никакая позиция вида 0;n при $%n\ne0$% критической не будет, потому что в ней можно выиграть. Позиция 1;1 критическая, потому что от неё не перейти к 0;0, а все остальные "нижестоящие" позиции нами проанализированы. В позиции вида 1;n при $%n\ne1$% побеждает начинающий.

В позиции 2;2 побеждает начинающий: он забирает по 2 камня из обеих куч. Позиция 2;3 (а также 3;2) критическая: от неё нельзя перейти к "нижестоящей" критической. Поэтому все позиции вида 2;m при $%m\ne3$% и 3;n при $%n\ne2$% к числу критических не относится.

Позиция 4;4 критическая: от неё нельзя перейти ни к одной из проклассифицированных выше критических позиций. Соответственно, все позиции вида 4;n при $%n\ne4$% выигрышные для начинающего. Критической будет и 5;5, а при 5;n, где $%n\ne5$% и 6;6, выигрывает начинающий. Далее критическими будут 6;7 и 7;6, а также 8;8, что проверяется тем же способом. Поэтому 8;8 будет позицией, где выигрывает второй игрок. На любой ход своего противника он имеет возможность оставить ему одну из критических позиций, что видно непосредственно из описания.

Надеюсь, что нигде не обсчитался (здесь это довольно легко сделать).

ссылка

отвечен 8 Янв '14 22:26

изменен 8 Янв '14 23:38

@falcao, спасибо!

(8 Янв '14 23:27) Uchenitsa

@falcao, решение логичное и Вы нигде не обсчитались. Исправьте ради красоты решения: при 5;n, где n≠5

(8 Янв '14 23:34) Uchenitsa

@Uchenitsa: да, я менял буквы в тексте в какой-то момент, и там осталось не то неравенство. Сейчас я исправлю опечатку.

(8 Янв '14 23:37) falcao

Добрый вечер! А почему Вы не рассматриваете позицию (7,7)? Ведь она тоже критическая и выигрывает второй игрок. А позиции (6,7) и (7,6), по-моему, не являются критическими, т.к. не при любом ходе первого игрока выигрывает второй. Или я чего-то недопонимаю?

(15 Янв '14 21:11) Tat

@Tat: позиция (7,7) критической не будет. От неё можно перейти, например, к (5,5).

Если Вы считаете, что в позиции (7,6) имеется выигрывающий ход, то давайте просто сыграем. Я где-то мог обсчитаться, поэтому полезно лишний раз проверить.

(15 Янв '14 21:33) falcao

Спасибо, я поняла свою ошибку - считала из левого нижнего угла, а надо из верхнего правого.

(15 Янв '14 22:47) Tat
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×81
×70

задан
8 Янв '14 21:07

показан
4955 раз

обновлен
15 Янв '14 22:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru