(感謝topfirstguy的指正,現已修正為正解)
這裡介紹最麻煩但最容易想到的方法:按"步"就班法
概念就是「先找出一個自己可以贏的情況。如果對方有辦法從某A情況弄成他可以贏的情況,這個A情況就是自己會輸的情況;否則此A情況也為自己可以贏的情況。」
(以下三箱球數會以(x,y,z)表示,例如原本的球數為(3,5,7),所有未知數皆為正整數)
首先從
上次的題目可知,如果你拿剩下兩箱一樣多球
(k,k,0)的情況時,你就相當於贏了。
因此在取球時,不可以取剩三箱之中有至少兩箱一樣多球
(k,k,m),因為對方將另外一箱取走就可以了。
接著討論三箱球數都不一樣的情況:
1.最少球數為1
若你拿成
(1,2,3)的話,你就相當於贏了。因為不管對方怎麼拿你都可以再拿成
(k,k,0)的模式。
相對的,若拿剩下
(a,2,3) (1,b,3) (1,2,c) (a>1,b>2,c>3)時,對方都可以拿成
(1,2,3),因此這些情況是不好的。
下一個是
(1,4,5),拿成這樣你也贏了,因為對方無論怎麼拿都會變成前面紅色字所代表的"會輸的組合"。
相對的
(a,4,5) (1,b,5) (1,4,c) (a>1,b>4,c>5)也都是"會輸的組合"。
因為原本的球數為(3,5,7),所以其他最少球數為1的情況都已經被涵蓋或是不可能出現,因此討論至這。
2.最小球數為2
(2,3,n) (2,4,5)為何是"會輸的組合"前面已經都提過,此處省略。
相對的
(2,4,6)便是"會贏的組合",因為不管怎麼取都會變成前面"會輸的組合"之一。
那麼
(a,4,6) (2,b,6) (2,4,c) (a>2 b>4 c>6)也都是"會輸的組合"。
而
(2,5,7)也是"會贏的組合",理由仿前。
至此討論已經可以結束了,因為只要一開始從(3,5,7)拿成
(2,5,7),後面拿對你就贏了。
而
(3,4,7)和
(3,5,6)也為"會贏的組合",也是可以以相同方法推得的。
這其實是非常經典的
Nim 遊戲。
必勝法以及遊戲的變形可以參考
尤怪之家的介紹,
想瞭解嚴謹的數學證明可以看
這篇文章。