奎伯教授：为什么要挪4个杯子，我们能否只动2个杯子?

不寻常的奎伯

尽管奎伯教授通过巧辩解决了这个问题，但普遍问题并不像这个问题这么平常。例如，同样的问题，如果是100个满杯和100个空杯需要对调多少次才能使满杯和空杯间隔排列?

用200个杯子做实验不很实际，我们首先分析较小的n值的解决方法，这里n是满杯或空杯数。你可以用两种颜色的记号来解题(或者牌的正反面、硬币的正反面、不同面值的硬币等等)当n=1时无解。n=2时显然只对调一次。n=3时也对调一次。进一步努力，你可以发现简单的公式，n是偶数时，对调数为n/2。n是奇数时，为(n—1)/2。所以，如果是100个满杯和100个空杯，需要对调50次。

这需要移动100个杯子，奎伯的幽默作法把移动杯数减少了一半。

又有一个类似的分隔同题，但比较难解。在同一排中有n个一类物体，相邻的是n个另一类物体(如上面用玻璃杯、记号、牌等来表示)你还是要把这一排列变为互相间隔状态，但我们移动原则不同了。我们必须移动一对记号放到队列中任何空白处，移动中不能改变这两个记号的顺序。例如，这是n=3时的做法：

XXXOOO

XOOOXX

X00 XOX

OXOXOX

一般的解法是什么呢?n=1时无解。你很快也发现，n=2时也无解。对所有大于2的n，最小的移动次数是n。

当n=4时，解决这个同题就很不易，或许你已经解决了，或许当n大于等于3时你能用公式来表示这个问题的解。

这些问题变化一下，可以产生一些其它的难题：

(1)规则同前，只是当你移动一对记号时，如果是不同颜色的，在移动前交换它们的位置。也就是黑红对在移动前变为红黑对，8个记号移动5次可以完成，10个记号移动5次也可以完成。我们还不知道一般的解决方法，或许你能找到。

(2)规则和原题一样，只是一种颜色的记号有n个，另一种颜色的记号有n+1个，并且只有颜色不同的一对才能移动。可以证明：无论n为何值，都需移动n2次，且这是最小的移动次数。

(3)三种不同颜色的记号，移动每对相邻的记号使三种颜色相互间隔，如果n=3(即总共9个记号)需移5次。在以上的变化中，我们都设变化为最后排列时排列中没有空隙，如果允许空隙存住，移动4次就能得到结果。

一些变化的假设迄今还没有提出来，更不必说解决了。比如，在以上的变化中，一次移动3个或更多相邻记号。

还有，如果先移动1个记号，再移动2个相邻的记号，接下来是3个以至4个等等。已知各有n个两种颜色的记号，移动n次能解决问题吗?