巧斷金鏈中學趣味數(shù)學教案

時間：2024-06-21 21:03:22

巧斷金鏈中學趣味數(shù)學教案

巧斷金鏈中學趣味數(shù)學教案

巧斷金鏈中學趣味數(shù)學教案

　　巧斷金鏈中學趣味數(shù)學教案

　　一位來自阿肯色州的年輕太太格羅麗亞，正在加利福尼亞州旅行.她想在旅館租用一個房間，租期一周.辦事員此時正心緒不佳。辦事員：房費每天20元，要付現(xiàn)錢.格羅麗亞：很抱歉，先生，我沒帶現(xiàn)錢.但是我有一根金鏈，共7節(jié)，每節(jié)都值20元以上.辦事員：好吧，把金鏈給我.格羅麗亞：現(xiàn)在不能給你.我得請珠寶匠把金鏈割斷，每天給你一節(jié)，等到周末我有了現(xiàn)錢再把金鏈贖回.辦事員終于同意了，但格羅麗亞必須決定如何斷開金鏈的方法.格羅麗亞：我該三思而行，因為珠寶匠是按照他所切割和以后重新連接的節(jié)數(shù)來索價的.格羅麗亞想了一下，悟到她不必把每一節(jié)都割斷，因為她可以把一段段金鏈換進換出，以這種方式來付房費.當她算出需要請珠寶匠割斷的節(jié)數(shù)時，她幾乎不能自信。你想一想需要割開多少節(jié)?

　　只需要割開一節(jié)。這一節(jié)應是從一端數(shù)起的第三節(jié).把金鏈斷開成1節(jié)，2節(jié)，4節(jié)這樣三段后就能以換進換出的方式每天付給辦事員一節(jié)作為房費。

　　啊哈!領(lǐng)悟到下列兩點才能解題.第一，至少需要有1節(jié)，2節(jié)，4節(jié)這樣三段(即其節(jié)數(shù)成二重級數(shù)的一些段)，這樣才能以各種不同的組合方式組成1節(jié)，2節(jié)，3節(jié)，4節(jié)，5節(jié)，6節(jié)和7節(jié).我們在藥品混亂問題中已經(jīng)知道，這就是作為二進制記數(shù)法基礎(chǔ)的冪級數(shù).

　　第二，只需要割開一節(jié)就可以把金鏈分成符合要求的三段.關(guān)于這個問題，若把金鏈的長度增加，則可以想出一些新的問題.例如，假設(shè)格羅麗亞有一根63節(jié)的金鏈，她想把金鏈割開，以上面那種方式來付63天的房費(價格不變).要達到此種目的只需要割開三節(jié).你想出來了嗎?你能否根據(jù)金鏈的不同長度設(shè)計一個通用的解題程序，要求分割開的節(jié)數(shù)為最少?

　　有一個有趣的變相問題：若所經(jīng)手的n節(jié)首尾相連的閉合回路，例如說格羅麗亞有一串金項鏈，由79節(jié)相連而成，若每天房費為一節(jié)，試問最少需要分割開幾節(jié)才能支付79天房費?

　　所有這些問題都跟二進制記數(shù)法有密切的關(guān)系.比如格羅麗亞的63節(jié)金項鏈如何分割?只要將63化成二進制表示：等于111111即63=1+2+4+8+16+32只要將從第二節(jié)開始的兩節(jié)割開，再將從第八節(jié)開始的八節(jié)割下來，和從第32節(jié)開始的32節(jié)割下來即可，這樣就有了從1，2，3，4，5，6，直到63的所有節(jié)數(shù).一般地，若有n節(jié)金鏈，n是形如2k-1類型的數(shù)，將n化成二進制表示，再將所有1的位置所代表的2的冪的數(shù)相間隔地割開即可達到目的.但是對于其他任意類型的數(shù)，卻不能奏效，比如對于格羅麗亞的79節(jié)金項鏈，79的二進制記數(shù)法表示為1001111.即79=1+2+4+8+0+0+64，這樣從1到15都能表示，可是從16到63都沒法表示，我把這個問題做到這里，也一時糊涂起來，但這個問題畢竟不是很復雜，咱們也學一學閔科夫斯基在課堂上口出狂言要解決四色問題的勁頭，摸索著來解決一把.咱們可以這樣：你不是要求節(jié)數(shù)最少嗎?假設(shè)n=a+b其中a是已經(jīng)找到的最大的那一節(jié)數(shù)，b是比n小的已經(jīng)解決了的金鏈問題，由于b已經(jīng)解決，因此b的拆分能夠表示從1，2，3，...b-1，b的所有金鏈節(jié)數(shù)，而再大一些的數(shù)就不能夠表示了，比如b+1，所以必須要a參加進來，如果n是奇數(shù)，可令a=b+1，這樣n=2b+1，所以b=(n-1)/2，a=(n+1)/2，這樣就找到了最大的一節(jié)的節(jié)數(shù)a，然后對b=(n-1)/2繼續(xù)應用如上的辦法，即可解決問題.如果n是偶數(shù)，可令a=b，這樣雖然a本身不能表示出b+1，但是可以從b的拆分中拿出一個1來(這個1是必須存在的，因為要表示從1，2，3，...b-1，b的所有數(shù))與a組成a+1也就是b+1.所以n=a+b=2a=2b，a=b=n/2.這樣也找到了n為偶數(shù)時最大的一節(jié)金鏈的節(jié)數(shù).對于b繼續(xù)如上的過程，就可以找到全部應該斷開的金鏈節(jié)數(shù)，我算出了從1到15的所有拆分如下：

　　1=1

　　2=1+1

　　3=1+2

　　4=1+1+2

　　5=1+1+3

　　6=1+2+3

　　7=1+2+4

　　8=1+1+2+4

　　9=1+1+2+5

　　10=1+1+3+5

　　11=1+1+3+6

　　12=1+2+3+6

　　13=1+2+3+7

　　14=1+2+4+7

　　15=1+2+4+8

　　對于上面的格羅麗亞太太的79節(jié)金項鏈，79+1=80，80/2=40，所以最大的一節(jié)就是40節(jié)，79-40=39，39+1=40，40/2=20，所以第二大的一節(jié)就是20節(jié)，39-20=19，19+1=20，20/2=10，第三大的一節(jié)是10節(jié)，19-10=9，9+1=10，10/2=5，又找到了一節(jié)是5，9-5=4，4的表示法如上已經(jīng)列出來了：4=1+1+2.最后得到79節(jié)的金項鏈的分割法：1，1，2，5，10，20，40.過去我也碰到過一道類似的題，是23節(jié)金項鏈，也能夠很容易地解決：23+1=24，24/2=12;23-12=11，11=1+1+3+6;所以23的分割法為：1，1，3，6，12.顯然，對于2k-1類型的數(shù)，用這里的辦法與用二進制記數(shù)法得出的結(jié)果是一致的.

　　從上面所列出的拆分法可以看出，如果2k=2k+1，那么n一定要用k+1個數(shù)來表示，即：n=a0+a1+a2+...+ak.

　　可以用數(shù)學歸納法很容易地證明這是正確的.那么還有沒有比這更少的分割法呢?可以證明沒有了.從我們的分析方法中可以看出，這是一個構(gòu)造性的推理過程，假如還有比這更少的分割法，那么相當于在表達式n=a0+a1+a2+...+ak.中進行了某些組合，比如將a1+a2合并成新的a1，那么原來的有些組合就表示不出來了，例如a0+a2，就沒有辦法組合了.當然，一個數(shù)的拆分不是唯一的，前面的23節(jié)金鏈還可以分成1，2，3，6，11.你可以試試，這種分割法照樣能滿足要求.前面的分析中也可以把(n-1)/2留下來作為最大的節(jié)數(shù)，但是這樣分出來的節(jié)數(shù)就不一定都是最少的了，例如把15這樣分割，會得到：1，1，2，4，7.雖然能夠滿足付房費的要求，但是就不是最優(yōu)解了.最后總結(jié)一下，把前面的算法過程公式化可以得到：

　　k-1r-1k-1

　　n=(n+c0)/2+{[n-cs2s+cr2r]/2r+1}+[n-cr2r]/2k

　　r=1s=0r=0

　　其中c0，c1，...ck-1等等是1或是0取決于每一步得出的數(shù)的奇偶性.其實最后一項等于1，這樣可以得出：

　　k-1

　　n-2k=cr2r

　　r=0

　　a0=(n+c0)/2

　　i-1

　　ai=[n-cs2s+ci2i]/2i+11(i=1，2，3，...k-1)

　　s=0

　　ak=1