三个杯子问题

三个杯子问题(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。

相关条目

参考来源