Question

如圖所示，有三根針和套在一根針上的若干金屬片．按下規(guī)則，把金屬片從一根針上全部移到另一根針上．

1．每次只能移動1個金屬片；

2．較大的金屬片不能放在較小的金屬片上面．

試推測：把n個金屬片從1號針移到3號針，最少需要移動多少次？

Answer 1

答案：
解析：

導(dǎo)思：我們從移動1，2，3，4個金屬片的情形入手，探究其中的規(guī)律性，進(jìn)而歸納出移動n個金屬片所需的次數(shù)． 　　探究：當(dāng)n＝1時，只需把金屬片從1號針移到3號針，用符號(13)表示，共移動了1次． 　　當(dāng)n＝2時，為了避免將較大的金屬片放在較小的金屬片上面，我們利用2號針作為“中間針”，移動的順序是： 　　(1)把第1個金屬片從1號針移到2號針； 　　(2)把第2個金屬片從1號針移到3號針； 　　(3)把第1個金屬片從2號針移到3號針． 　　用符號表示為 　　(12)(13)(23)， 　　共移動了3次． 　　當(dāng)n＝3時，把上面兩個金屬片作為一個整體，則歸結(jié)為n＝2的情形，移動的順序是： 　　(1)把上面兩個金屬片從1號針移到2號針； 　　(2)把第3個金屬片從1號針移到3號針； 　　(3)把上面3個金屬片從1號針移到3號針． 　　其中(1)和(3)都需要借助中間針，用符號表示為 　　(13)(12)(32)(13)(21)(23)(13)， 　　共移動了7次． 　　當(dāng)n＝4時，把上面3個金屬片作為一個整體，移動的順序是： 　　(1)把上面3個金屬片從1號針移到2號針； 　　(2)把第4個金屬片從1號針移到3號針； 　　(3)把上面3個金屬片從2號針移到3號針． 　　用符號表示為 　　(12)(13)(23)(12)(31)(32)(12)(13)　(23)(21)(31)(23)(12)(13)(23)． 　　共移動了15次． 　　至此，我們得到依次移動1，2，3，4個金屬片所需次數(shù)構(gòu)成的數(shù)列 　　1，3，7，15． 　　觀察這個數(shù)列，可以發(fā)現(xiàn)其中蘊(yùn)含著如下規(guī)律： 　　1＝21－1，3＝22－1，7＝23－1，15＝24－1． 　　由此我們猜想：若把n個金屬片從1號針移到3號 　　針，最少需要移動an次，則數(shù)列{an}的通項(xiàng)公式為 　　an＝2n－1(n∈N*)． 　　通過探究上述n＝1，2，3，4時的移動方法，我們可以 　　歸納出對n個金屬片都適用的移動方法．當(dāng)移動n個金屬片時，可分為下列3個步驟： 　　(1)將上面(n－1)個金屬片從1號針移到2號針； 　　(2)將第n個金屬片從1號針移到3號針； 　　(3)將上面(n－1)個金屬片從2號針移到3號針． 　　這樣就把移動n個金屬片的任務(wù)．轉(zhuǎn)化為移動兩次(n－1)個金屬片和移動一次第n個金屬片的任務(wù)．而移動(n－1)個金屬片需要移動兩次(n－2)個金屬片和移動一次第(n－1)個金屬片，移動(n－2)個金屬片需要移動兩次(n－3)個金屬片和移動一次第(n－2)個金屬片……如此繼續(xù)，直到轉(zhuǎn)化為移動1個金屬片的情形．根據(jù)這個過程，可得遞推公式 　　 　　從這個遞推公式出發(fā)，可以證明上述通項(xiàng)公式是正確的．