2014/12/09

三堆球、每次從任意一堆拿走幾顆、拿最後一顆輸

問題:
有三堆球,每堆球數量不一。參加遊戲的兩人,輪流在其中,選擇任意一堆,拿走幾顆球。
每次拿走的數量任意,但不能跨堆拿。
拿到最後一顆球的人,就輸了比賽。
請問,要怎麼拿,才能確保必勝?

解答:

先想特例。
1.只有一堆球,是個無聊的特例。只留下最後一顆,其他全部移走。
2.兩堆球。數量分別p和q。為了方便,我們把它記做(p q)。這時也很單純,只有兩種狀況。
 2.0.數量為(1 x)時,把它變成1
 2.1.不是上述狀況,數量為一般的(p q), p大於1而且p小於q時,把它變成(p p)
 意思就是說,當兩堆的數量都不是只剩一顆的時候,不管對手怎麼拿,我方就保持讓兩堆一樣多,直到出現(1 x)這種組合時,我方把那一堆x全數拿走,留下1顆給對手。

好了,現在進入一般狀況的討論。
3.三堆球(p q r)
 3.0.數量為(1 1 x)時,把它變成(1 1 1)
 3.1.不是上述狀況,數量為一般(p q r),在十進位的表示之下,不容易看出做法。把p q r改用二進位表示,就容易得多。要做的事情是:在二進位表示下,不要讓某一位元落單,只有在其中一堆出現;也不要讓某一位元在三堆當中都出現。要做到的是,從最高位元到最低位元,都是成對出現。
 例如,(3 8 9)用二進位表示是(0011 1000 1001)。這個例子當中,標紅色的那個1在三組當中單獨存在,其他位置的1則是成對的。我方得把它變成(0001 1000 1001)也就是(1 8 9)。再拿(8 10 13)做第二個例子:(8 10 13)用二進位表示是(1000 1010 1101),此例當中所有位置的1都不是成對出現。它要不是單獨存在,就是三個都是1。我方得把它變成(1000 1010 0010)也就是(8 10 2),或者重新依大小順序記為(2 8 10),這樣就是每個位置的1都成對出現。第三個例子,是有兩堆相同數量,也就是(p p r)而且p不等於1的狀況,很容易得知要讓每一位元皆成對出現就是要拿掉數量不同的那一堆,成為(p p 0)。
 前面三個都是例子,至於實際上面對三堆球,應該動哪一堆,並且要拿走多少顆,才能夠在『只更動其中一堆的數量』的限制之下,讓每一位元都成對出現?檢查的通則,是從最高位元看起。如果此位元只有某一堆為1其他兩堆為0,就挑這一堆下手。如果不是這樣的狀況,而是此位元有兩堆甚至三堆都是1,就往低位元移動一位,繼續做相同的檢查,直到確定了某一堆為止。一旦確定了挑哪一堆下手之後,要拿走幾顆才會讓『最高位元至最低位元,每一位元都成對出現』?這個問題就很簡單了。

 前述的檢查,有兩種情況,即使從最高位元一路檢查到最低位元,都沒有辦法決定唯一的一堆。第一種狀況是對手給我方的數字已經是位元成對的,例如對方給我們(1 8 9)或者(1 4 5)之類的數字。倘若對方用正確的步驟玩下去,是立於不敗之地的。另外一個情況是某一(或者某些)位元曾經出現三堆都是1,其他位元要不是皆0就是已經成對。這樣的狀況下,我方挑哪一堆動手,皆可以找到讓『最高位元至最低位元,每一位元都成對出現』的數量。

 在3.1.當中提到的,二進位的每個位元成對出現,就能確保必勝,這是前面2.1.推廣的一般狀況。至於為什麼保證必勝,可以用數學證明,適合做為練習題。此外,這個問題可以一般化,變成n堆球的遊戲。

5 則留言:

匿名 提到...

太難了,這世上能解的人寥寥可數。
偷看答案,才知道自己應該永遠解不出來。
我倒是可以記下答案,用來打敗同事。

PANTU 提到...

謝謝留言。寫這個就是給大家享受偷看答案的樂趣啊:)

匿名 提到...

我輸了.
當initial是(p,p,r),
閒家先拿走r,就沒救了.
好在沒有打賭....

匿名 提到...

(3 8 9)的二進制寫錯了. 真難得.
應該是命題寫錯了.

PANTU 提到...

不好意思,typo,然後表達能力又不夠。看來沒能講清楚做法。