三個杯子問題

三個杯子問題(three cups problem)是(最常見版本下)無法解的智力遊戲

在問題一開始,一個杯子是倒著放,二個杯子正放。目標是在六步以內將所有的杯子變成正放,而且每一步都只能將二個杯子反放(從正放變倒放,或從倒放變正放)。

可以解的版本

 
可以解的三個杯子問題,若圖中的A杯及C杯正放,只有B杯倒放,就是不可解的三個杯子問題

可以解(而且顯然可解)的版本是有二個杯子是倒著放,一個杯子正放。只要將二個杯子從倒放改為正放,三個杯子就都正放了,因此只需一步就可達到目標了。

不可解的證明

在一開始只有一個杯子倒放的版本中,若要看為何此問題不可解,需要先專注在倒著放的杯子個數,先假設為W。 問題一開始的狀態是將W=1,最後要讓W=0,也就是讓W減一,因此接下來要證明的是所有移動方式都會在每一步造成W有偶數的變化。 因此每一步都會反放二個杯子,每反放一個杯子,W可能會+1(杯子從正放變成倒放)或是-1(杯子從倒放變成正放)。 因此每一步W的變化是二個奇數的和,可能是2、0或-2,這三個數字都是偶數,因此得證。

另一個思考的方式是從有二個「正確」的杯子及一個「錯誤」的杯子開始,若反放一個「正確」的杯子及一個「錯誤」的杯子,情形不變。若將二個「正確」的杯子反放,結果會是三個「錯誤」的杯子。下一步會變成二個「正確」的杯子及一個「錯誤」的杯子。因此不論如何移動,「錯誤」的杯子只會有一個或是三個,不會是零個。

更廣義的說法,不論有幾個杯子,只要W一開始是奇數,就無法用此方式讓W減到0,相反的,只要W一開始是偶數,每次讓W減2,數次之後就可以讓W減到0。

相關條目

參考來源