12
110940_4c5b5f78d053934.jpg
740)this.width=740" border=undefined>
111020_4c5b5f78d3be134.jpg
740)this.width=740" border=undefined>
不寻常的奎伯
尽管奎伯教授通过巧辩解决了这个问题，但普遍问题并不像这个问题这么平常。例如，同样的问题，如果是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次能解决问题吗？
| 
发表于 2016-8-13 14:36:10