三個杯子問題
 | 此條目沒有列出任何參考或來源。 (2017年9月) |
三個杯子問題（three cups problem）是（最常見版本下）無法解的智力遊戲。
在問題一開始，一個杯子是倒著放，二個杯子正放。目標是在六步以內將所有的杯子變成正放，而且每一步都只能將二個杯子反放（從正放變倒放，或從倒放變正放）。
可以解的版本
[編輯]
可以解（而且顯然可解）的版本是有二個杯子是倒著放，一個杯子正放。只要將二個杯子從倒放改為正放，三個杯子就都正放了，因此只需一步就可達到目標了。
不可解的證明
[編輯]在一開始只有一個杯子倒放的版本中，若要看為何此問題不可解，需要先專注在倒著放的杯子個數，先假設為W。 問題一開始的狀態是將W=1，最後要讓W=0，也就是讓W減一，因此接下來要證明的是所有移動方式都會在每一步造成W有偶數的變化。 因此每一步都會反放二個杯子，每反放一個杯子，W可能會+1（杯子從正放變成倒放）或是-1（杯子從倒放變成正放）。 因此每一步W的變化是二個奇數的和，可能是2、0或-2，這三個數字都是偶數，因此得證。
另一個思考的方式是從有二個「正確」的杯子及一個「錯誤」的杯子開始，若反放一個「正確」的杯子及一個「錯誤」的杯子，情形不變。若將二個「正確」的杯子反放，結果會是三個「錯誤」的杯子。下一步會變成二個「正確」的杯子及一個「錯誤」的杯子。因此不論如何移動，「錯誤」的杯子只會有一個或是三個，不會是零個。
更廣義的說法，不論有幾個杯子，只要W一開始是奇數，就無法用此方式讓W減到0，相反的，只要W一開始是偶數，每次讓W減2，數次之後就可以讓W減到0。