奎伯的杯子問(wèn)題

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

b．巴尼：這有一排10個(gè)杯子，前5個(gè)杯子裝著(zhù)可樂(lè )，后5個(gè)杯子空著(zhù)，你能挪4個(gè)杯子，使滿(mǎn)杯和空杯間隔排列嗎?

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

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

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

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

　　不尋常的奎伯

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

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

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

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

　　XXXOOO

　　XOOOXX

　　X00XOX

　　OXOXOX

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

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

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

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

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

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

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

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