奎伯的杯子問題

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è)杯子，我們能否只動(dòng)2個(gè)杯子?

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

　　不尋常的奎伯

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

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

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

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

　　XXXOOO

　　XOOOXX

　　X00XOX

　　OXOXOX

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

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

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

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

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

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

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

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