《具體數學》習題1.3的問題？

12-13

河內塔問題的一個擴展 3個柱子 A B C 開始的時候所有盤子從大到小從下往上放置在A 現在規定所有盤子不能在A和C之間直接移動最後把A上的盤子移動到C 求證在移動過程中 B上必定出現過所有盤子正確放置的時刻
書後答案的意思是 3個柱子所有盤子不考慮順序一共有3^n種排法而正確移動完成的最少步數是3^n-1次加上初始狀態正好是3^n次所以必定會出現所有排列的每一種所以求證的情況當然也會出現
我的問題是這個證法難道不是先要確保移動過程中出現的排列沒有重複嗎？我用兩個盤子模擬了一下確實沒有重複那這其中的原理是什麼呢？為什麼按照規則移動過程中不會出現重複現象？

總感覺你證明最小步數的時候就應該已經證出來了，這是個典型的遞歸過程，移動n塊盤子從1到3時，先將n-1塊從1移到3，將最底下移到2，將n-1塊從3移到1，將最底下移到3，再將n-1塊從1移到3，用數學歸納法立即得證。
這種移動方法其實是一種三進位的格雷碼，除了頭和尾以外，任意一個狀態都只有兩種移動方法，一種往前一種往後，形成一條鏈。

如果在移動中出現狀態重複，就意味著這個移動方法不是最優的，矛盾。

提供一種不需要反證法的思路。

考慮移動N塊盤子時，由於將第N塊從A移動至B時，前N-1塊必定在C處；
而將第N塊從B移動至C處時，前N-1塊必定在A處。因此前N-1塊分別在第N塊在B與不在B兩種情況下經過了B，所以只要證問題規模為N-1時，B上出現了N-1塊的所有組合過程。
我們可以反覆遞歸這個過程，直到問題規模為一時顯然成立即可。

如果最少步數中有重複的格局，那麼這兩個格局之間的步驟就是多餘的，那麼就不是最少步數了…所以3^n-1加上初始格局每一個必須不同，最多又只有3^n種格局…

題外話，竟然還有學習具體數學的。。。
想我大二上努力攻讀，還是在第五章崩潰了。。。