妙想奇思奎伯的杯子問題

1、妙想奇思奎伯的杯子問題a.巴尼在飲店工作，他給他的兩位顧客表演10個杯子游戲。b.巴尼：這有一排10個杯子，前5個杯子裝著可樂，后 5個杯子空著，你能挪4 個杯子，使?jié)M杯和空杯間隔排列嗎 ?c 巴尼：好，只需第2 個杯子和第 7 個杯子交換位置，第4個杯子和第9個杯子交換位置。d.奎伯教授總想一些奇特的方法，碰巧聽到了這個問題?？淌冢簽槭裁匆? 個杯子，我們能否只動2 個杯子 ?e.奎伯教授：很簡單，把第 2個杯中的可樂倒進第 7個杯中，把第 4 個杯中的可樂倒進第 9 個杯中。不尋常的奎伯盡管奎伯教授通過巧辯解決了這個問題，但普遍問題并不像這個問題這么平常。例如，同樣的問題，如果是 1

2、00 個滿杯和 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ù)減少了 一半。又有一個類似的分隔同題，但比較難解

3、。在同一排中有 n 個一類物體，相鄰的是 n 個另一類物體( 如上面用玻璃杯、記號、牌等來表示) 你還是要把這一排列變?yōu)榛ハ嚅g隔狀態(tài)，但我們移動原則不同了。我們必須移動一對記號放到隊列中任何空白處，移動中不能改變這兩個記號的順序。例如，這是 n=3 時的做法：XXXOOOXOOOXXX00 XOXOXOXOX一般的解法是什么呢 ?n=1 時無解。你很快也發(fā)現(xiàn)， n=2 時也無解。對所有大于2的n,最小的移動次數(shù)是no當 n=4 時，解決這個同題就很不易，或許你已經(jīng)解決了，或許當 n 大于等于 3 時你能用公式來表示這個問題的解。這些問題變化一下，可以產(chǎn)生一些其它的難題：(1) 規(guī)則同前，只是當

4、你移動一對記號時，如果是不同顏色的，在移動前交換它們的位置。也就是黑紅對在移動前變?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 個記