Question

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

1．每次只能移動(dòng)1個(gè)金屬片；

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

試推測(cè)：把n個(gè)金屬片從1號(hào)針移到3號(hào)針，最少需要移動(dòng)多少次？

Answer 1

答案：
解析：

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