第二節(jié)古代數(shù)學(xué)游戲

1、2021/3/231古代數(shù)學(xué)游戲中的數(shù)學(xué)文化古代數(shù)學(xué)游戲中的數(shù)學(xué)文化2021/3/232客觀世界的許多變化都呈現(xiàn)出前因后果的規(guī)律,即某種現(xiàn)象的變化結(jié)果與緊靠它前面的一個或多個結(jié)果密切相關(guān),這種現(xiàn)象反映到數(shù)學(xué)上,就是遞推關(guān)系。通過建立遞推關(guān)系解決問題的方法，稱之為遞推方法遞推方法是人們從開始認識數(shù)量關(guān)系時就很自然地產(chǎn)生的一種推理思想，這種方法是探索數(shù)學(xué)規(guī)律和解題思路的重要方法之一，它對于幾乎是所有的數(shù)學(xué)分支都有重要的作用.2021/3/233例1 平面上5條直線最多能把圓的內(nèi)部分成幾部分?平面上100條直線最多能把圓的內(nèi)部分成幾部分?假設(shè)用ak表示k條直線最多能把圓的內(nèi)部分成的部分數(shù)。這里k=0

2、,1,2,。如圖可見 2021/3/234歸納出遞推公式an=ann. （）即畫第n1條直線時,最多增加n部分。原因是這樣的:第一條直線最多把圓分成兩部分,故a1=2。當(dāng)畫第二條直線時,要想把圓內(nèi)部分割的部分盡可能多，就應(yīng)和第一條直線在圓內(nèi)相交，交點把第二條直線在圓內(nèi)部分分成兩條線段，而每條線段又把原來的一個區(qū)域劃分成兩個區(qū)域，因而增加的區(qū)域數(shù)是2，正好等于第二條直線的序號。同理，當(dāng)畫第三條直線時，要想把圓內(nèi)部分割的部分數(shù)盡可能多，它就應(yīng)和前兩條直線在圓內(nèi)各有一個交點。兩個交點把第三條直線在圓內(nèi)部分成三條線段。而每條線段又把原來一個區(qū)域劃分成兩個區(qū)域。因而增加的區(qū)域部分數(shù)是3，正好等于第三條直

3、線的序號，。這個道理適用于任意多條直線的情形，所以遞推公式（1）是正確的。 2021/3/235例假設(shè)剛出生的雌雄一對小兔過兩個月就能生下雌雄一對小兔,此后每月生下一對小兔。如果養(yǎng)了初生的一對小兔,問滿一年時共可得多少對兔子? 我們先退到開始的簡單情況來推算,從中歸納出遞推關(guān)系。 第一個月:只有1對小兔;第二個月:一對小兔長成一對大兔,但尚不會生殖,仍只有一對兔子;第三個月:這對大兔生了一對小兔，這時共2對兔子;第四個月：大兔又生了一對小兔，而上月出生的小兔正在長大，這時共3對兔子；第五個月：這時已有兩對大兔可以生殖（原來的大兔和第三個月出生的小兔），于是生了兩對小兔，這時共有5對兔子 .如下

4、圖：2021/3/2362021/3/237 把推算的結(jié)果列成一張表:月份123456789 10 11 12 13 兔子對數(shù)112358 1 3 21 34由表中可見滿一年時可得144對兔子 2021/3/238如果要算的時間長,這種方法就有困難了,現(xiàn)在我們來找遞推關(guān)系用Un表示第n個月時的兔子對數(shù),則: Un :1，1，2，3，5，8，13，21，34，容易發(fā)現(xiàn)遞推公式是: Un = Un-1+Un-2.現(xiàn)在說明這個遞推公式是正確的。因為第n個月時的兔子對分兩類，一類是第n-1個月時的兔子對數(shù)Un-1，另一類是當(dāng)月新生的兔子對，而這些小兔對數(shù)恰好是第n-2個月時的兔子對數(shù)Un-2 2021

5、/3/239數(shù)列Un稱為斐波那契數(shù)列（Fibonacci,11701250,是意大利數(shù)學(xué)家）,由于數(shù)列Un具有許多重要的奇特性質(zhì),因而受到數(shù)學(xué)家們的極大關(guān)注，并把數(shù)列Un取名為斐波那契數(shù)列 2021/3/2310例 傳說在印度的佛教圣地貝拿勒斯圣廟里安放著一個黃銅板,板上插著三根寶石針,在第一根寶石針上,從下到上穿著由大到小的64片中心有孔的金片,每天都有一個值班僧侶按下面規(guī)則移動金片: 把金片從第一根寶石針移到其余的寶石針上。要求一次只能移動一片，而且小片永遠要放在大片的上面. 當(dāng)時傳說當(dāng)64片金片都按上面的規(guī)則從第一根寶石針移到另一根寶石針上時，世界將在一聲霹靂中毀滅,所以有人戲稱這個問題

6、叫“世界末日”問題（也稱為“Hanoi塔”問題）。 當(dāng)然，移金片和世界毀滅并無聯(lián)系，這只是一個傳說而已，但說明這是一個需要移動很多很多次才能辦到的事情。解這個問題的方法在算法分析中也常用到.究竟按上述規(guī)則移動完這64片金片需要移動多少次呢?2021/3/2311設(shè)有n片金片,把從第一片金片至第k片金片按題目要求由第一根寶石針移到另一根寶石針共需ak次先對4片金片的簡單情形,用下列的幾組圖來表示移動過程中的各種狀態(tài),并計數(shù)，歸納出遞歸關(guān)系式 2021/3/23122021/3/23132021/3/2314我們可以這樣來想:為了移動第n片到第根寶石針上,我們必須先把它上面的n-1片按題目的規(guī)則采

7、用某種程序移到第根寶石針上,這需要移動an-1次,然后才能把最下面第n片（最大的），移到第根寶石針上。最后再經(jīng)過an-1次才能把第根寶石針上的n-1片金片按上面規(guī)則采用同樣程序移到第根寶石針上。因此把n片金片按題中的規(guī)則全部移到另一根寶石針上共應(yīng)移:an=2an-1+1（次） （） 這就是遞推公式。2021/3/2315為了求得n=64時a64的值,我們當(dāng)然不能一次次地由a1=1,a2=3,a3=7,直到算出a64現(xiàn)在我們設(shè)法把遞推公式（）變形為可以直接計算a64的形式 a64是一個非常大的數(shù)（a64=264-1） ,如果按照每移動一片需一秒鐘算,把64片金片從一根寶石針移到另一根寶石針上大約

8、需要5800億年!推導(dǎo)如下:2021/3/2316 an=2an-1+1=2(2an-2+1) +1=an-2+2+1=22(2an-3+1)+2+1=23an-3+22+21+1=2n-1a1+2n-2+2n-3+2+1=1+2+22+2n-2+2n-1=2n-1 a64=264-1.2021/3/2317例九連環(huán)游戲“九連環(huán)”是中國先人創(chuàng)造的智力游戲. 大人玩,小孩玩, 也不知道玩了多少代. 它是中國文化的精粹之一,2000年在北京舉辦的世界數(shù)學(xué)家大會期間,這個古老的游戲引起了與會數(shù)學(xué)家們的濃厚興趣.2021/3/2318首先我們要了解九連環(huán)的構(gòu)造:九連環(huán)的設(shè)計原理是數(shù)學(xué)上的拓撲學(xué),它主要

9、有九個圓環(huán)及框架組成,每個圓環(huán)都連有一個直桿,各直桿在后一個圓環(huán)內(nèi)穿過，九個直桿的另一端用平板或者圓環(huán)相對固定，圓環(huán)在框架上可以解下或者套上，玩九連環(huán)就是要把這九個環(huán)全部從框架上解下來或者全部套在框架上（如下圖）。 2021/3/23192021/3/2320九連環(huán)的玩法比較復(fù)雜,但是不管怎么玩,無論解下環(huán)還是套上環(huán)都要遵循一定的規(guī)則:每次只能解下或者套上一個環(huán);第一個環(huán)任何情況下, 可自由上下(圖);如果某一個環(huán)在上, 而它前面所有的環(huán)都在下,那么這個環(huán)的后一個可上也可下(圖) Sn =1/62 n+2 - 3 + ( - 1) n- 1 步2021/3/23212021/3/2322我把游

10、戲規(guī)則改為以下三條:每次可以解下或者套上一個或者兩個環(huán);第一個環(huán)可自由上下以及前兩個環(huán)可一起自由上下;從第二個環(huán)開始,如果某一個環(huán)在上, 而它前面所有的環(huán)都在下,那么這個環(huán)的后一個可上也可下。 實際上在玩九連環(huán)的過程中,我發(fā)現(xiàn)只有前兩個環(huán)可以一起自由上下,其它的環(huán)每次只能上下一個,另外還要知道解下個環(huán)和套上個環(huán)需要的步數(shù)是一樣的。遵循這樣的規(guī)則，我們給出解下全部的個環(huán)需要的步數(shù)。 2021/3/2323設(shè)解下全部的個環(huán)需要的步數(shù)為Sn,那么要解下第一個環(huán)只需要一步,即S1,要解下前兩個環(huán)也只需要一步，即S2，而當(dāng)時，要全部解下這個環(huán)，就需要先解下第n個環(huán)，而要解下第個環(huán)就只能保留其前面的第個環(huán)

11、，也就是要先把前面的個環(huán)全部解下，這需要Sn2步，這時再需要一步就可以把第個環(huán)解下，這時為了把第個環(huán)解下，還需要把前面的個環(huán)全部套上又需要Sn2步，這時問題就變成了個環(huán)的情形，要全部解下這個環(huán)還需要Sn1 .2021/3/2324 于是我們有 2211nnnnSSSS 11S 21S 1221nnnSSS3n ,11221,nnnnSn， 為奇數(shù),為偶數(shù).2021/3/2325有一個農(nóng)夫帶一條狗、一只雞和一筐米過河如果沒有農(nóng)夫看管,則狗要吃雞,雞要吃米但是船很小,只夠農(nóng)夫帶一樣?xùn)|西過河問農(nóng)夫該如何解此難題? 左岸右岸2021/3/2326分析:以四維向量（人,狗,雞,米）表示狀態(tài)，其中每個變元

12、可取0或1，取0表示在左岸（出發(fā)點）,取1表示在右岸，則我們有10個允許狀態(tài)向量:A1（1，1，1，1）-（0，0，0，0） B1A2（1，1，1，0）-（0，0，0，1） B2A3（1，1，0，1）-（0，0，1，0） B3A4（1，0，1，1）-（0，1，0，0） B4A5（1，0，1，0）-（0，1，0，1） B52021/3/2327初始狀態(tài)是:（0,0,0,0）,最終終態(tài)是: （1，1，1，1）, 非法中間狀態(tài)有:（0，0，1，1）,（0，1，1，0）,（0，1，1，1）, （1，1，0，0）,（1，0，0，1）,（1，0，0，0）.轉(zhuǎn)移向量有四個: （1，0，1，0）, （1，1，

13、0，0）,（1，0，0，1）, （1，0，0，0）每一次過河就是一個狀態(tài)向量與轉(zhuǎn)移向量的加法,且規(guī)定:0+0=0,0+1=1+0=1,1+1=0.如: （1，1，1，1）+ （1，0，1，0）=（0，1，0，1） 2021/3/2328每一次轉(zhuǎn)移只考慮從允許狀態(tài)到允許狀態(tài).本問題就轉(zhuǎn)化為:找出一個從初始狀態(tài)（1,1,1,1）經(jīng)過奇數(shù)次運算的到最終狀態(tài)（0，0，0，0）的轉(zhuǎn)移過程. 方法如下:第一次過河:(1,1,0,0)(0,0,1,1)(1,0,1,0)(0,1,0,1)(1,1,1,1)+(1,0,0,1)(0,1,1,0)(1,0,0,0)(0,1,1,1) 2021/3/2329第二次

14、過河:(1,1,0,0)(1,0,0,1) (1,0,1,0) (1,1,1,1)(0,1,0,1)+(1,0,0,1)(1,1,0,0) (1,0,0,0)(1,1,0,1) 循環(huán)不可取2021/3/2330第三次過河:(1,1,0,0)(0,0,0,1) (1,0,1,0)(0,1,1,1) (1,1,0,1)+(1,0,0,1)(0,1,0,1) (1,0,0,0) (0,1,0,1) 循環(huán)2021/3/2331第一種方案:A1（1,1,1,1）（0，0，0，0） B1A2（1，1，1，0）（0，0，0，1） B2A3（1，1，0，1）（0，0，1，0） B3A4（1，0，1，1）（0，

15、1，0，0） B4A5（1，0，1，0）（0，1，0，1） B52021/3/2332第二種方案:A1（1,1,1,1）（0，0，0，0） B1A2（1，1，1，0）（0，0，0，1） B2A3（1，1，0，1）（0，0，1，0） B3A4（1，0，1，1）（0，1，0，0） B4A5（1，0，1，0）（0，1，0，1） B52021/3/2333三個老道士與三個和尚分別在一條河的兩岸,都要到河的對岸去河中只有一條小船,可容兩人。只有一個道士和一個和尚會劃船而且無論在船上或在岸上,道士的數(shù)量都不能超過和尚的數(shù)量如何過河?兩對夫妻要過河，河中只有一條小船，可容兩人兩個丈夫都不愿讓自己的妻子和另一

16、個男人在一起，除非自己也在場。如何過河?2021/3/2334有三對夫婦過河,妻子不準(zhǔn)在老公不在的情況下與其他的男人相處,只有一條船,一次最多只準(zhǔn)坐兩個人，問這三對夫婦怎樣才能都過河?三對騙子夫婦過河:三對夫婦過河,男的都是騙子,河中只有一艘船,船最多只能坐二人,如果妻子離開丈夫,就會被其他騙子騙走,他們應(yīng)該如何安全過河?2021/3/2335用向量（H,W）表示左岸的男子數(shù)為H,女子數(shù)為W則根據(jù)題意可取的狀態(tài)向量有以下個:（,），（，），（，），（，），（，），（，），（，），（，），（，），（，）轉(zhuǎn)移向量為:(-1),(-1) ,0,1,2, 12 , 1,2,3,.iimnm nmnii

17、i其中當(dāng) 為奇數(shù)時表示過河 為偶數(shù)時表示返回運算按通常數(shù)的加法2021/3/23361111111111(-1) 0,(-1) 1(3,2)(-1) 0,(-1) 2(3,1)(3,3)+(-1) 1,(-1) 1(2,2)(2,3)(-1) 1,(-1) 0(1,3)(-1) 2,(-1) 0 第一次過河為:2021/3/23372021/3/23382021/3/2339習(xí) 題 十 四1請你根據(jù)下列各個數(shù)之間的關(guān)系,在括號里填上恰當(dāng)?shù)臄?shù): （1）1,5,9，13，17，（） （2）0.625, 1.25, 2.5, 5, （） （3） （4）198，297，396，495，（ ），（ ）

18、2345,()10 16 22 28 2021/3/23402將自然數(shù)1,2,3,，按圖排列，在“2”處轉(zhuǎn)第一個彎，“3”處轉(zhuǎn)第二個彎，“5”處轉(zhuǎn)第三個彎，。問哪個數(shù)處轉(zhuǎn)第二十個彎? 2211kak221kakk一般規(guī)律:答案:1112021/3/23413上一段12級樓梯,規(guī)定每一步只能上一級或兩級,問要登上第12級樓梯共有多少種不同走法? 4n個連續(xù)自然數(shù)按規(guī)律排成右表:0 3 4 7 8 11 1 2 5 6 9 10根據(jù)規(guī)律, 從2002到2004, 箭頭的方向依次應(yīng)為(A) (B) (C) (D) 2021/3/23425觀察: 1234+1=25,2345+1=121,3456+1=361, (1)請寫出一個具有普遍性的結(jié)論,并給出證明;(2)根據(jù)(1),計算2000200120022003+1的結(jié)果(用一個最簡式子表示).2(1)(2)(3) 1(31)n nnnnn 第n行是從開始的連續(xù)個整數(shù)