奎伯的杯子問題

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

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

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

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

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

e．奎伯教授：很簡單，把第2個(gè)杯中的可樂倒進(jìn)第7個(gè)杯中，把第4個(gè)杯中的可樂倒進(jìn)第9個(gè)杯中。

　　不尋常的奎伯

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

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

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

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

　　XXXOOO

　　XOOOXX

　　X00XOX

　　OXOXOX

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

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

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

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

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

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

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

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