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,然後表達能力又不夠。看來沒能講清楚做法。

Labels

七條 (1) 大かまど芝 (2) 小狗教我的事 (5) 巴黎印象 (7) 日本大阪 (22) 日本北海道 (40) 日本印象 (27) 日本東京 (40) 日航關西機場飯店 (1) 水井茶堂 (4) 火星在線 (4) 北工房 (1) 台南遠東香格里拉 (4) 台灣旅遊 (46) 本湖月 (4) 甘味處 花 (1) 甲殼公司 (30) 吉崎食堂 (3) 竹北 (10) 牡蠣料理 開 (1) 咖啡 (26) 東京麵通團 (1) 南半球 (5) 叛徒心情日記 (120) 科普 (13) 紀の善 (1) 美瑛選果 (1) 音樂 (15) 香港旅遊 (11) 香港機場富豪酒店 (1) 倫敦旅遊 (7) 宮本 (1) 馬雅烘焙 (3) 強羅花壇 (2) 涵碧樓 (1) 野球 (6) 森の時計 (2) 菡萏咖啡 (3) 新竹喜來登飯店 (1) 溫味 (2) 銀座 古川 (1) 線性代數與信號處理 (1) 閱讀與影劇 (100) 韓國印象 (17) 攝影習作 (40) ANA Gate Tower Hotel Osaka (1) Auberge de Tefutefu (7) Cafe de la Paix (1) COEX (4) Conrad Hotel Singapore (1) Dommy's Dining and Bar (1) Gender (16) Haneda Excel Hotel Tokyu (1) Hilton KL (1) Hotel Monterey Sanno (1) Hotel Nikko Narita (1) Hotel Okura Sapporo (3) HOTEL日航福岡 (1) JAL修行 (36) KAMADO MARUYAMA (3) KLCC Trader Hotel (1) La Sante (2) Mitsui Garden Hotel (1) Moliere (1) Pres Vert (2) Relais Saint Germain (2) Rihga Royal Hotel (4) Sapporo Grand Hotel (3) Sapporo Park Hotel (2) Swissotel Nankai Osaka (1) うさぎや(兔屋) (1) おしどり (2) おばんざい とらや (2) きじ (1) サンパレス球陽館 (2) ねぎ焼 やまもと (2) ホテルコムズ新千歳空港 (2)