grundy的遊戲把一堆東西劃分成兩個不等長的樁

Question

我碰到過一個問題。

有N堆石頭，其中ith堆有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. 

鑑於樁的起始組，誰假設兩個球員都打出最佳狀態而贏得比賽？

最重要的說法 - 「如果Alice贏了別人，答案應該是Alice，答案是Bob。」

現在我的問題是，如果我們最初只有一堆8塊石頭，實際的答案是鮑勃。但據我所知，如果愛麗絲將8個寶石的初始組合分成兩組，即7和1，即 8-> 7 + 1 ，那麼如果愛麗絲以最佳策略玩耍，則無法贏得鮑勃）。但答案是鮑勃。有人能幫我找出答案是鮑勃的原因嗎？我認爲我上面標記爲最重要的陳述在這個答案中很重要，但我還沒有弄明白。誰能幫忙？你可以參考這個鏈接，其中顯示了完全相同的插圖Wikipedia of "Grundy's Game"

任何基本的想法也讚賞。

---

夥計們這就是我面臨的確切問題。任何小想法也表示讚賞。

Grundy's game extended to more than two heaps

Answer 1

如果愛麗絲先走，她的任何舉動都不會讓她贏。證明由耗盡：

如果Alice劃分石頭變成5,2,1，然後鮑勃勝在以下方式：

1. Bob的轉變。 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. 愛麗絲輪到了。沒有任何動作可用。愛麗絲失去了。

如果Alice劃分石頭變成4,3,1，然後鮑勃勝在以下方式：

1. Bob的轉變。 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. 愛麗絲輪到了。沒有任何動作可用。愛麗絲失去了。

如果Alice劃分石頭變成7,1，然後鮑勃勝在以下方式：

1. Bob的轉變。 7,1 - >4,2,1,1（請注意，根據維基百科的「僅分成兩堆」規則，這一舉措是不可能的，但不是根據OP的「分成任意數量的樁」規則。）
2. Alice輪到了。她唯一合法的舉動是將四人分開。 4,2,1,1 - >3,2,1,1,1
3. 鮑勃輪到了。 3,2,1,1,1 - >2,2,1,1,1,1
4. 愛麗絲輪到了。沒有任何動作可用。愛麗絲失去了。

如果Alice劃分石頭變成6,2，然後鮑勃勝在以下方式：

1. Bob的轉變。 6,2 - >4,2,2
2. 愛麗絲輪到了。她唯一合法的舉動是將四人分開。 4,2,2 - >3,2,2,1
3. 鮑勃輪到了。 3,2,2,1 - >2,2,2,1,1
4. 愛麗絲輪到了。沒有任何動作可用。愛麗絲失去了。

如果Alice劃分石頭變成5,3，然後鮑勃勝在以下方式：

1. Bob的轉變。 5,3 - >3,3,2
2. 愛麗絲輪到了。她唯一合法的舉動是分三個。 3,3,2 - >3,2,2,1
3. 輪到鮑勃了。 3,2,2,1 - >2,2,2,1,1
4. 愛麗絲輪到了。沒有任何動作可用。愛麗絲失去了。

Answer 2

我沒有看到任何方式鮑勃可以贏得這一點，如果愛麗絲髮揮最佳狀態。維基百科正確地解釋了它。如果兩位球員都打得最好，並且如果8是最初的棋子數，那麼愛麗絲應該贏。因爲在1輪完成之後（每輪都需要1轉），愛麗絲總是可以通過配置4 + 2 + 1 + 1執行鮑勃。從這個配置中，鮑勃可以做的是3 + 1 + 2 + 1 + 1因此，愛麗絲贏得了