игра Грунди, разделяющая кучу на две неравные кучки - PullRequest
Новая
       32

игра Грунди, разделяющая кучу на две неравные кучки

1 голос
/ 20 марта 2012

Я столкнулся с проблемой.

Есть N груд камней, где в i-й куче есть камни XI. Алиса и Боб играют в следующую игру: 

a. Alice starts, and they alternate turns.

b. In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the piles you create should have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5). 

c. The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

Учитывая начальный набор стопок, кто выигрывает игру, если оба игрока играют оптимально?

Самое важное утверждение: «Ответ должен быть Алисой, если Алиса выиграет, иначе ответ Боб.»

Теперь мой вопрос заключается в том, что если у нас изначально есть только одна куча из 8 камней, то фактический ответ - Боб. Но, насколько я думаю, если Алиса разбивает начальный набор из 8 камней на две стопки по 7 и 1, т.е. 8-> 7 + 1 тогда Боб не сможет выиграть, если Алиса сыграет с лучшей стратегией (оптимально). И все же ответ - Боб. Может кто-нибудь помочь мне выяснить, почему ответ Боб? Я думаю, что утверждение, которое я назвал самым важным выше, имеет большое значение в этом ответе, но я пока не могу его понять. Кто-нибудь может помочь? Вы можете обратиться к этой ссылке, которая показывает точно такую ​​же иллюстрацию в Википедии "Grundy's Game"

Любая элементарная идея также приветствуется.

Ребята, это именно та проблема, с которой я сталкиваюсь. Любая маленькая идея также приветствуется.

Игра Гранди расширена до более чем двух куч

Ответы [ 2 ]

2 голосов
/ 20 марта 2012

Если Алиса пойдет первой, ни один из доступных ей ходов не позволит ей выиграть. Доказательство истощением:

Если Алиса делит камни на 5,2,1, то Боб выигрывает следующим образом:

  1. Ход Боба. 5,2,1 -> 4,2,1,1
  2. Ход Алисы. Ее единственный законный ход - разделить четыре. 4,2,1,1 -> 3,2,1,1,1
  3. Ход Боба. 3,2,1,1,1 -> 2,2,1,1,1,1
  4. Ход Алисы. Нет доступных ходов. Алиса проигрывает.

Если Алиса делит камни на 4,3,1, то Боб выигрывает следующим образом:

  1. Ход Боба. 4,3,1 -> 3,3,1,1
  2. Ход Алисы. Ее единственный законный ход - разделить три. 3,3,1,1 -> 3,2,1,1,1
  3. Боб Боб. 3,2,1,1,1 -> 2,2,1,1,1,1
  4. Ход Алисы. Нет доступных ходов. Алиса проигрывает.

Если Алиса делит камни на 7,1, то Боб выигрывает следующим образом:

  1. Ход Боба. 7,1 -> 4,2,1,1 (Обратите внимание, что этот шаг невозможен в соответствии с правилом Википедии "делить только на две кучи", но не в соответствии с правилом ОП "делить на любое количество куч".)
  2. Ход Алисы. Ее единственный законный ход - разделить четыре. 4,2,1,1 -> 3,2,1,1,1
  3. Ход Боба. 3,2,1,1,1 -> 2,2,1,1,1,1
  4. Алиса. Нет доступных ходов. Алиса проигрывает.

Если Алиса делит камни на 6,2, то Боб выигрывает следующим образом:

  1. Ход Боба. 6,2 -> 4,2,2
  2. Ход Алисы. Ее единственный законный ход - разделить четыре. 4,2,2 -> 3,2,2,1
  3. Ход Боба. 3,2,2,1 -> 2,2,2,1,1
  4. Ход Алисы. Нет доступных ходов. Алиса проигрывает.

Если Алиса делит камни на 5,3, то Боб выигрывает следующим образом:

  1. Ход Боба. 5,3 -> 3,3,2
  2. Алиса. Ее единственный законный ход - разделить три. 3,3,2 -> 3,2,2,1
  3. Ход Боба. 3,2,2,1 -> 2,2,2,1,1
  4. Ход Алисы. Нет доступных ходов. Алиса проигрывает.
0 голосов
/ 20 марта 2012

Я не вижу, как Боб сможет выиграть, если Алиса сыграет оптимально.Википедия объясняет это правильно.Если оба игрока играют оптимально и если 8 - начальное количество камней, то Алиса должна выиграть.Потому что после 1 полного раунда (оба занимают по 1 ходу каждый) Алиса всегда может принудить Боба с конфигурацией 4 + 2 + 1 + 1.Из этой конфигурации все, что может сделать Боб, это 3 + 1 + 2 + 1 + 1. Следовательно, Алиса выигрывает

...