不尋常的奎伯

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

　　用200個(gè)杯子做實(shí)驗(yàn)不很實(shí)際，我們首先分析較小的n值的解決方法，這里n是滿杯或空杯數(shù)。你可以用兩種顏色的記號(hào)來(lái)解題(或者牌的正反面、硬幣的正反面、不同面值的硬幣等等)當(dāng)n=1時(shí)無(wú)解。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)、牌等來(lái)表示)你還是要把這一排列變?yōu)榛ハ嚅g隔狀態(tài)，但我們移動(dòng)原則不同了。我們必須移動(dòng)一對(duì)記號(hào)放到隊(duì)列中任何空白處，移動(dòng)中不能改變這兩個(gè)記號(hào)的順序。例如，這是n=3時(shí)的做法：

　　XXXOOO

　　XOOOXX

　　X00  XOX

　　OXOXOX

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

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

　　這些問(wèn)題變化一下，可以產(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)。可以證明：無(wú)論n為何值，都需移動(dòng)n2次，且這是最小的移動(dòng)次數(shù)。

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

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

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