第二节古代数学游戏.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,古代数学游戏中的数学文化,客观世界的许多变化都呈现出前因后果的规,律，即某种现象的变化结果与紧靠它前面的一个或,多个结果密切相关，这种现象反映到数学上，就是,递推关系通过建立递推关系解决问题的方法，称之为递,推方法,递推方法是人们从开场认识数量关系时就很自然地产生,的一种推理思想，这种方法是探索数学规律和解题思路的重,要方法之一，它对于几乎是所有的数学分支都有重要的作用.,一、与数列有关的数学游戏,例1 平面上5条直线最多能把圆的内局部成几局部？平面上100条直线最多能把圆的内局部成几局部？,假设用ak表示k条直线最多能把圆的内局部成,的局部数这里k=0，1，2，如图可见,归纳出递推公式an=ann.,即画第n1条直线时，最多增加n局部原因是这样的：第,一条直线最多把圆分成两局部，故a1=2当画第二条直线,时，要想把圆内局部割的局部尽可能多，就应和第一条直线,在圆内相交，交点把第二条直线在圆内局部分成两条线段，,而每条线段又把原来的一个区域划分成两个区域，因而增加,的区域数是2，正好等于第二条直线的序号。

同理，当画第,三条直线时，要想把圆内局部割的局部数尽可能多，它就应,和前两条直线在圆内各有一个交点两个交点把第三条直线,在圆内局部成三条线段而每条线段又把原来一个区域划分成,两个区域因而增加的区域局部数是3，正好等于第三条直线,的序号，这个道理适用于任意多条直线的情形，所以递推,公式1是正确的例假设刚出生的雌雄一对小兔过两个月就能生下雌雄一对小兔，此后每月生下一对小兔如果养了初生的一对小兔，问满一年时共可得多少对兔子？,我们先退到开场的简单情况来推算，从中归纳出递推关系第一个月：只有1对小兔；,第二个月：一对小兔长成一对大兔，但尚不会生殖，仍只有,一对兔子；,第三个月：这对大兔生了一对小兔，这时共2对兔子；,第四个月：大兔又生了一对小兔，而上月出生的小兔正在长,大，这时共3对兔子；,第五个月：这时已有两对大兔可以生殖原来的大兔和第三,个月出生的小兔，于是生了两对小兔，这时共有5对兔子.,如以下图：,把推算的结果列成一张表:,月份,1,2,3,4,5,6,7,8,9,10,11,12,13,兔子对数,1,1,2,3,5,8,13,21,34,由表中可见满一年时可得144对兔子,如果要算的时间长，这种方法就有困难,了，现在我们来找递推关系,用Un表示第n个月时的兔子对数，,那么：Un：1，1，2，3，5，8，13，,21，34，,容易发现递推公式是：,Un=Un-1+Un-2.,现在说明这个递推公式是正确的。

因为第n个月,时的兔子对分两类，一类是第n-1个月时的兔子对数,Un-1，另一类是当月新生的兔子对，而这些小兔对数,恰好是第n-2个月时的兔子对数Un-2,数列Un称为斐波那契数列Fibonacci，,11701250，是意大利数学家,由于数列Un,具有许多重要的奇特性质，因而受到数学家们的极,大关注，并把数列Un取名为斐波那契数列,例 传说在印度的佛教圣地贝拿勒斯圣庙里安放,着一个黄铜板，板上插着三根宝石针，在第一根宝石,针上，从下到上穿着由大到小的64片中心有孔的金片,每天都有一个值班僧侣按下面规那么移动金片：,把金片从第一根宝石针移到其余的宝石针上要求,一次只能移动一片，而且小片永远要放在大片的上面.,当时传说当64片金片都按上面的规那么从第一根宝石针,移到另一根宝石针上时，世界将在一声霹雳中消灭,所,以有人戏称这个问题叫“世界末日问题也称为“Hanoi,塔问题当然，移金片和世界消灭并无联系，这只是一个传,说而已，但说明这是一个需要移动很多很屡次才能办,到的事情解这个问题的方法在算法分析中也常用到.,终究按上述规那么移动完这64片金片需要移动多少次呢,设有n片金片，把从第一片金片至第k片金片,按题目要求由第一根宝石针移到另一根宝石针共需,ak次,先对4片金片的简单情形，用以下的几组图来,表示移动过程中的各种状态，并计数，归纳出递归,关系式,我们可以这样来想：为了移动第n片到第,根宝石针上，我们必须先把它上面的n-1片按题,目的规那么采用某种程序移到第根宝石针上，这,需要移动an-1次，然后才能把最下面第n片最大,的，移到第根宝石针上。

最后再经过an-1次,才能把第根宝石针上的n-1片金片按上面规那么,采用同样程序移到第根宝石针上因此把n片,金片按题中的规那么全部移到另一根宝石针上共应,移：,an=2an-1+1次 ,这就是递推公式为了求得n=64时a64的值，我们当然不能一次,次地由a1=1,a2=3,a3=7,直到算出a64,现在我们设法把递推公式变形为可以,直接计算a64的形式,a64是一个非常大的数a64=264-1，如果按,照每移动一片需一秒钟算，把64片金片从一根宝,石针移到另一根宝石针上大约需要5800亿年！,推导如下：,a,n,=2a,n-1,+1=2(2a,n-2,+1)+1=a,n-2,+2+1,=2,2,(2a,n-3,+1)+2+1=2,3,a,n-3,+2,2,+2,1,+1,=,=2,n-1,a,1,+2,n-2,+2,n-3,+2+1,=1+2+2,2,+2,n-2,+2,n-1,=2,n,-1,a,64,=2,64,-1.,例九连环游戏,“九连环是中国先人创造的智力游戏.大人,玩,小孩玩,也不知道玩了多少代.它是中国文化的,精粹之一，2000年在北京举办的世界数学家大会期,间,这个古老的游戏引起了与会数学家们的浓厚兴趣.,首先我们要了解九连环的构造：九连环,的设计原理是数学上的拓扑学，它主要有九,个圆环及框架组成，每个圆环都连有一个直,杆，各直杆在后一个圆环内穿过，九个直杆,的另一端用平板或者圆环相对固定，圆环在,框架上可以解下或者套上，玩九连环就是要,把这九个环全部从框架上解下来或者全部套,在框架上如以下图。

九连环的玩法比较复杂，但是不管怎么,玩，无论解下环还是套上环都要遵循一定的,规那么：,每次只能解下或者套上一个环；,第一个环任何情况下,可自由上下(图);,如果某一个环在上,而它前面所有的环都在,下,那么这个环的后一个可上也可下(图),Sn=1/62 n+2-3+(-1)n-1 步,我把游戏规那么改为以下三条：,每次可以解下或者套上一个或者两个环；,第一个环可自由上下以及前两个环可一起,自由上下；,从第二个环开场，如果某一个环在上,而它前面所,有的环都在下,那么这个环的后一个可上也可下实际上在玩九连环的过程中，我发现只有前两个,环可以一起自由上下，其它的环每次只能上下一个,另外还要知道解下个环和套上个环需要的步数是一,样的遵循这样的规那么，我们给出解下全部的个环,需要的步数设解下全部的个环需要的步数为Sn，那么要,解下第一个环只需要一步，即S1，要解,下前两个环也只需要一步，即S2，而当,时，要全部解下这个环，就需要先解下第n个,环，而要解下第个环就只能保存其前面的第个环，也就是要先把前面的个环全部解下，这需要Sn2步，这时再需要一步就可以把第个环解下，这时为了把第个环解下，还需要把前面的个环全部套上又需要Sn2步，这时问题就变成了个环的情形，要全部解下这个环还需要Sn1.,于是我们有,，,有一个农夫带一条狗、一只鸡和一筐米,过河如果没有农夫看管，那么狗要吃鸡，鸡,要吃米但是船很小，只够农夫带一样东西,过河问农夫该如何解此难题？,左岸右岸,二、其它游戏的数学解法,分析：以四维向量人，狗，鸡，米表示状态，其,中每个变元可取0或1，取0表示在左岸出发点,取1,表示在右岸，那么我们有10个允许状态向量：,A11，1，1，1-0，0，0，0 B1,A21，1，1，0-0，0，0，1 B2,A31，1，0，1-0，0，1，0 B3,A41，0，1，1-0，1，0，0 B4,A51，0，1，0-0，1，0，1 B5,初始状态是：0，0，0，0,最终终态是:1，1，1，1,非法中间状态有:0，0，1，1,0，1，1，0,0，1，1，1,1，1，0，0,1，0，0，1,1，0，0，0.,转移向量有四个:1，0，1，0,1，1，0，0,1，0，0，1,1，0，0，0,每一次过河就是一个状态向量与转移向量的加法,且规,定:0+0=0,0+1=1+0=1,1+1=0.,如:,1，1，1，1+1，0，1，0=0，1，0，1,每一次转移只考虑从允许状态到允许状态.本问题就,转化为:找出一个从初始状态1，1，1，1经过奇数,次运算的到最终状态0，0，0，0的转移过程.,方法如下:,第一次过河：,第二次过河：,第三次过河：,第一种方案：,A11，1，1，10，0，0，0 B1,A21，1，1，00，0，0，1 B2,A31，1，0，10，0，1，0 B3,A41，0，1，10，1，0，0 B4,A51，0，1，00，1，0，1 B5,第二种方案：,A11，1，1，10，0，0，0 B1,A21，1，1，00，0，0，1 B2,A31，1，0，10，0，1，0 B3,A41，0，1，10，1，0，0 B4,A51，0，1，00，1，0，1 B5,三个老道士与三个和尚分别在一条河的两岸，,都要到河的对岸去河中只有一条小船，可容两,人。

只有一个道士和一个和尚会划船而且无论在,船上或在岸上，道士的数量都不能超过和尚的数,量如何过河？,两对夫妻要过河，河中只有一条小船，可容两,人两个丈夫都不愿让自己的妻子和另一个男人在,一起，除非自己也在场如何过河？,二、其它游戏的数学解法,有三对夫妇过河，妻子不准在老公不在的情况下与其他,的男人相处，只有一条船，一次最多只准坐两个人，问这三,对夫妇怎样才能都过河？,三对骗子夫妇过河：,三对夫妇过河,男的都是骗子,河中只有一艘船,船最多只,能坐二人,如果妻子离开丈夫,就会被其他骗子骗走,他们应该,如何平安过河,二、其它游戏的数学解法,用向量H，W表示左岸的男子数为H，,女子数为W那么根据题意可取,的状态向量有以下个：,，,，,，,，,转移向量为：,第一次过河为：,习 题 十 四,1请你根据以下各个数之间的关系，在括号里,填上恰当的数：,11，5，9，13，17，,20.625,1.25,2.5,5,3,4198，297，396，495，,2将自然数1，2，3，按图排列，在“2,处转第一个弯，“3处转第二个弯，“5处转第三个,弯，问哪个数处转第二十个弯？,一般规律：,答案：111,3上一段12级楼梯，规定每一步只能上,一级或两级，问要登上第12级楼梯共有多少,种不同走法？,4,n,个连续自然数按规律排成右表:,0 3 4 7 8 11,1 2 5 6 9 10,根据规律,从2002到2004,箭头的方向依次应为,(A)(B)(C)(D),5,观察:1234+1=25,2345+1=121,3456+1=361,(1)请写出一个具有普遍性的结论,并给出证明;,(2)根据(1),计算2000200120022003+1的结果(用一个最简式子表示).,第n行是从开场的连续个整数的乘积与的和也就是：,6将自然数按以下三角形规律排列,那么第,15行的各数之和是.,1,2 3 4,5 6 7 8 9,10 11 12 13 14 15 16,17 18 19 20 21 22 23 24 25,(1)请写出一个具有普遍性的结论,并给出证明;,(2)计算第15行的各数之和是多少,第n行是如下的2n-1个正整数：,第n行的2n-1个正整数的和为：,第行的各数之和为：,。