《啊哈!灵机一动》－奎伯的杯子问题

非同寻常的柯伊伯

尽管柯伊伯教授通过巧妙的论证解决了这个问题，但一般问题并不像这个问题那样普遍。例如，同样的问题，如果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个或更多个相邻符号。

此外，如果首先移动一个标记，则移动两个相邻的标记，然后移动三个甚至四个标记，等等。众所周知，每种颜色有n个标记。移动n次能解决问题吗？