奇妙的组合之奎伯的杯子问题

a．巴尼在饮店工作，他给他的两位顾客表演10个杯子游戏。
　　
　　b．巴尼：这有一排10个杯子，前5个杯子装着可乐，后5个杯子空着，你能挪4个杯子，使满杯和空杯间隔排列吗?
　　
　　c．巴尼：好，只需第2个杯子和第7个杯子交换位置，第4个杯子和第9个杯子交换位置。
　　
　　d．奎伯教授总想一些奇特的方法，碰巧听到了这个问题。
　　
　　奎伯教授：为什么要挪4个杯子，我们能否只动2个杯子?
　　
　　e．奎伯教授：很简单，把第2个杯中的可乐倒进第7个杯中，把第4个杯中的可乐倒进第9个杯中。
　　
　　不寻常的奎伯
　　
　　尽管奎伯教授通过巧辩解决了这个问题，但普遍问题并不像这个问题这么平常。例如，同样的问题，如果是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
　　
　　X00XOX
　　
　　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次能解决问题吗?
　　