非同寻常的柯伊伯

尽管柯伊伯教授通过巧妙的论证解决了这个问题,但一般问题并不像这个问题那样普遍。例如,同样的问题,如果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次能解决问题吗?