三堆取物

三堆取物

這是個有趣的小遊戲,說有三堆各若干個物品(彈子、棋子、瓜子等等),兩個人輪流從某一堆取任意多的物品,規定每次至少取一個,最多一堆,最後取光者得勝。

三堆取物

是個有趣的小遊戲,說有三堆各若干個物品(彈子、棋子、瓜子等等),兩個人輪流從某一堆取任意多的物品,規定每次至少取一個,多者不限,最後取光者得勝。

這其實涉及到尼姆博弈定理的一個套用。不過尼姆博弈很多人看不明白,下面我來說說通俗的講法。

通俗講法

先列舉一串數列1 2 4 8 16 32 ......很容易看明白吧,就是2的0次冪1次冪2次冪3次冪4次冪5次冪(不理解也沒關係)......

任何一個自然數(每堆物品個數)都可以分為不重複2的冪相加,比如:6=2+4 15=1+2+4+8

舉例子就容易看明白了,比如說4、5、7這樣3堆

拆成上面的數相加4=4 5=1+4 7=1+2+4等號右面的拆開數字1、1、2、4、4、4,拿掉7裡面的6,就剩1、1、4、4了,每個數字成對沒有多餘的時候,我管這個叫平衡狀態,掌握住這個平衡就掌握了這個遊戲的輸贏。控制平衡會到最終平衡狀態,是你選著輸贏的時候了,比如0、2、2,輪到對方,他拿一個,你也拿一個,他再1,你贏了;要是他拿倆,你直接把剩下的拿了OK。你自己再想想1、2、3咋拿......哈哈......

再舉個例子,2、9、13,2=2、9=1+8 15=1+2+4+8,誰先拿誰贏,直接去拿15里的4,接下來等對方去破壞平衡,你接著找平衡......

有點遺憾的是,很容掌握這個小遊戲的贏法,倆人都明白的時候就失去了遊戲的樂趣......

2進制解釋

用(a,b,c)表示某種局勢,首先(0,0,0)顯然是奇異局勢,無論誰面對奇異局勢,都必然失敗。第二種奇異局勢是(0,n,n),只要與對手拿走一樣多的物品,最後都將導致(0,0,0)。仔細分析一下,(1,2,3)也是奇異局勢,無論對手如何拿,接下來都可以變為(0,n,n)的情形。

計算機算法裡面有一種叫做按位模2加,也叫做異或的運算,我們用符號(+)表示這種運算,先看(1,2,3)的按位模2加的結果:

1 =二進制01

2 =二進制10

3 =二進制11 (+)

———————

0 =二進制00 (注意不進位)

對於奇異局勢(0,n,n)也一樣,結果也是0。

任何奇異局勢(a,b,c)都有a(+)b(+)c =0。

注意到異或運算的交換律和結合律,及a(+)a=0,:

a(+)b(+)(a(+)b)=(a(+)a)(+)(b(+)b)=0(+)0=0。

所以從一個非奇異局勢向一個奇異局勢轉換的方式可以是:

1)使 a = c(+)b

2)使 b = a(+)c

3)使 c = a(+)b

相關詞條

熱門詞條

聯絡我們