奎伯的杯子問題

a．巴尼在飲店工作，他給他的兩位顧客表演10個杯子游戲。

b．巴尼：這有一排10個杯子，前5個杯子裝著可樂，后5個杯子空著，你能挪4個杯子，使?jié)M杯和空杯間隔排列嗎?

c．巴尼：好，只需第2個杯子和第7個杯子交換位置，第4個杯子和第9個杯子交換位置。

d．奎伯教授總想一些奇特的方法，碰巧聽到了這個問題。

奎伯教授：為什么要挪4個杯子，我們能否只動2個杯子?

e．奎伯教授：很簡單，把第2個杯中的可樂倒進第7個杯中，把第4個杯中的可樂倒進第9個杯中。

　　不尋常的奎伯

　　盡管奎伯教授通過巧辯解決了這個問題，但普遍問題并不像這個問題這么平常。例如，同樣的問題，如果是100個滿杯和100個空杯需要對調(diào)多少次才能使?jié)M杯和空杯間隔排列?

　　用200個杯子做實驗不很實際，我們首先分析較小的n值的解決方法，這里n是滿杯或空杯數(shù)。你可以用兩種顏色的記號來解題(或者牌的正反面、硬幣的正反面、不同面值的硬幣等等)當n=1時無解。n=2時顯然只對調(diào)一次。n=3時也對調(diào)一次。進一步努力，你可以發(fā)現(xiàn)簡單的公式，n是偶數(shù)時，對調(diào)數(shù)為n/2。n是奇數(shù)時，為(n—1)/2。所以，如果是100個滿杯和100個空杯，需要對調(diào)50次。

　　這需要移動100個杯子，奎伯的幽默作法把移動杯數(shù)減少了一半。

　　又有一個類似的分隔同題，但比較難解。在同一排中有n個一類物體，相鄰的是n個另一類物體(如上面用玻璃杯、記號、牌等來表示)你還是要把這一排列變?yōu)榛ハ嚅g隔狀態(tài)，但我們移動原則不同了。我們必須移動一對記號放到隊列中任何空白處，移動中不能改變這兩個記號的順序。例如，這是n=3時的做法：

　　XXXOOO

　　XOOOXX

　　X00XOX

　　OXOXOX

　　一般的解法是什么呢?n=1時無解。你很快也發(fā)現(xiàn)，n=2時也無解。對所有大于2的n，最小的移動次數(shù)是n。

　　當n=4時，解決這個同題就很不易，或許你已經(jīng)解決了，或許當n大于等于3時你能用公式來表示這個問題的解。

　　這些問題變化一下，可以產(chǎn)生一些其它的難題：

　　(1)規(guī)則同前，只是當你移動一對記號時，如果是不同顏色的，在移動前交換它們的位置。也就是黑紅對在移動前變?yōu)榧t黑對，8個記號移動5次可以完成，10個記號移動5次也可以完成。我們還不知道一般的解決方法，或許你能找到。

　　(2)規(guī)則和原題一樣，只是一種顏色的記號有n個，另一種顏色的記號有n+1個，并且只有顏色不同的一對才能移動�？梢宰C明：無論n為何值，都需移動n2次，且這是最小的移動次數(shù)。

　　(3)三種不同顏色的記號，移動每對相鄰的記號使三種顏色相互間隔，如果n=3(即總共9個記號)需移5次。在以上的變化中，我們都設(shè)變化為最后排列時排列中沒有空隙，如果允許空隙存住，移動4次就能得到結(jié)果。

　　一些變化的假設(shè)迄今還沒有提出來，更不必說解決了。比如，在以上的變化中，一次移動3個或更多相鄰記號。

　　還有，如果先移動1個記號，再移動2個相鄰的記號，接下來是3個以至4個等等。已知各有n個兩種顏色的記號，移動n次能解決問題嗎?