数学欣赏2006D

深圳大学数学与计算科学学院[e-mail]主讲：张文俊SZUSZUInthisChapter数学归纳法原理1抽屉原理与聚会认友2七桥问题与图论3数学与密码4SZU名人语录数学的生命力的源泉在于它的概念和结论尽管极为抽象，但却像我们所坚信的那样，它们是从现实中来的，并且在其他科学中，在技术中，在全部生活实践中都有广泛的应用；这一点对于了解数学是最重要的。——A.D.ALEKSANDROV《数学，它的内容、方法和意义》SZU名人语录从十分清楚明白、根本无法怀疑的东西、最简单最容易认识的对象开始，一点一点逐步上升到对复杂对象的认识。——R.DESCARTESSZU名人语录“数学是什么？大致说来，数学和其它科学一样，它的发展基于两个原因：（一）奇怪的现象；（二）数学结果的应用。”“结果把奥妙变为常识，复杂变为简单，数学便成为科学的有力而不可缺少的工具。”——陈省身SZU第一节数学归纳法原理[e-mail]@szu.edu.cn数学归纳法原理理论：基础、基本形式与变形MainPoints应用：有效应用与不当应用[e-mail]万丈高楼平地起南北朝时，一位印度法师将一部名为《百喻经》的寓言式图书带到中国并翻译成汉语。其中有一篇题为《三重楼寓》的寓言……数学欣赏[e-mail]数学归纳法及其理论基础[e-mail]理论基础自然数公理：设S是自然数集合N的子集，即SN，如果S满足（1）1∈S；（2）若n∈S，则n+1∈S；那么，必有S=[e-mail]【数学归纳法原理】设Pn是与自然数相关的一种命题，如果（1）当n=1时命题P1是成立的；（2）假设当n=k时命题Pk是成立的，可以证明当n=k+1时命题Pk+1也是成立的。那么命题Pn对所有自然数n都是成立的。[e-mail]【数学归纳法原理变形1】设Pn是与自然数相关的一种命题，如果1)当n=k0时命题Pk0是成立的；2)假设当n=k(k≥k0)时命题Pk是成立的，可以证明当n=k+1时命题Pk+1也是成立的。那么命题Pn对所有自然数n≥k0都是成立的。例如：n边形内角和问题。[e-mail]【数学归纳法原理变形2】设Pn是与自然数相关的一种命题，如果1)当n=1时命题P1是成立的；2)假设当1≤n≤k时命题Pn是成立的，可以证明当n=k+1时命题Pk+1也是成立的。那么命题Pn对所有自然数n都是成立的[e-mail]例如：有两堆棋子，数目相等。两人玩耍，每人每次可以从其中一堆中取任意多颗棋子，但不能同时从两堆中提取，规定取得最后一颗棋子者为胜。求证：后取者可以必胜。[e-mail]【数学归纳法原理变形3】设Pn是与自然数相关的一种命题，如果1)当n=1，2，…,k0时命题Pn是成立的；2)假设当n=k时命题Pk是成立的，可以证明当n=k+k0时命题Pk+k0也是成立的。那么命题Pn对所有自然数n都是成立的。[e-mail]例如:求证：方程x+2y=n的非负整数解的组数为；一般地，方程x+my=n的非负整数解的组数为其中表示商的整数部分。])1(1[41)1(21nn.1][mn][[e-mail]【数学归纳法原理变形4——跷跷板归纳法】设An，Bn是与自然数相关的两种命题，如果1)当n=1时命题A1是成立的；2)假设当n=k时命题Ak是成立的，可以证明命题Bk也是成立的；3)假设当n=k时命题Bk是成立的，可以证明当n=k+1时命题Ak+1也是成立的。那么命题An，Bn对所有自然数n都是成立的。[e-mail]例如:假设数列{an}满足：a2n=3n2,a2n-1=3n(n-1)+1,n=1,2,3,…。Sm=a1+a2+…+am.求证：)134(21)134(2122212[e-mail]【数学归纳法原理变形5——逆向归纳法】设Pn是与自然数相关的一种命题，如果1)存在一个递增的无限自然数序列{nk},使命题Pnk成立；2)假设当n=m时命题Pm是成立的，可以证明当n=m-10时命题Pm-1也是成立的。那么命题Pn对所有自然数n都是成立的.例如:算术平均与几何平均不等式数学欣赏[e-mail]归纳法在几何上的一个应用——两色定理的证明[e-mail]两色定理：在一张纸上随意画一些直线，这些直线把这张纸分割成若干个区域。把这假想成一个世界地图，要对其进行图色以便区分各个不同的国家，只需要两种颜色（比如红色与黄色）就够了。[e-mail]两色定理的证明：我们考虑画出这幅地图所用直线的条数：（1）如果只用一条直线，那么只能分出两个国家，两种颜色足够了；（2）现在假设对所有用n条直线画出的地图，都只需要两种颜色，我们考虑一个由n+1条直线画出的地图M。[e-mail]对于这个地图，从中抹去一条直线，此时剩下的地图是由n条直线画出的，自然可以由两种颜色着色。再把刚刚抹去的直线添上去，这条直线把整张纸分成两部分，刚才图好颜色的国家中，有些也给分开了，有些则没有被分开。[e-mail]在这条直线分成的两部分中，一半保留原来的着色，另一半中各个国家的颜色全部换掉：红换黄，黄换红。于是，这个由n+1条直线画出的地图M也只需要两种颜色就能区分各个国家了。根据数学归纳法原理，任何由若干条直线画出的地图都只需要两种颜色就够了。数学欣赏[e-mail]归纳法的妙用——数不尽的骆驼[e-mail]下面的故事是巧妙运用归纳法的一个例子。一位画家招收三个弟子，为了测试徒弟们对绘画奥妙掌握的程度，画家出了一道题目：要求三个弟子各自用最经济的笔墨，在给定大小的纸上画出最多的骆驼。[e-mail]第一个弟子为了多画一些，他把骆驼画得很小、很密，纸上显示出密密麻麻的一群骆驼；第二个弟子为了节省笔墨，他只画骆驼头，从纸上可以看到许多骆驼；第三个弟子在纸上用笔勾画出两座山峰，再从山谷中走出一只骆驼，后面还有一只骆驼只露出半截身子。[e-mail]三张画稿交上去，第三个弟子的画因构思巧妙、笔墨经济、以少含多而被认定为最佳作品。原因何在？数学欣赏[e-mail]归纳法的不当使用——秃子世界[e-mail](1)只长1根头发的人是秃子。(2)如果长n根头发的人是秃子，那么长n+1根头发的人也是秃子。于是根据数学归纳法原理，不论长多少根头发的人都是秃子，这个世界是个秃子世界。SZU第二节抽屉原理与聚会认友[e-mail]@szu.edu.cn抽屉原理与聚会认友抽屉原理的形式与意义MainPoints抽屉原理的应用与推广[e-mail]二桃杀三士晏婴（？~前500年）是古代历史上齐国富有经验的政治家，他足智多谋，在有些事情的处理上用到了一些数学原理。在《晏子春秋》里记载了一个叫“二桃杀三士”的故事：[e-mail]齐景公有三名勇士，田开疆、公孙接和古治子。这三名勇士都力大无比，英勇善战，为齐景公立下过许多功劳。但是他们也因此而目空一切，甚至连齐国宰相晏婴都不放在眼里。晏婴对此极为恼火，便劝齐景公杀掉他们。齐景公对晏婴言听计从，但却心存疑虑，担心万一武力制服不了他们反被他们联合反抗。晏婴于是献计于齐景公：以齐景公的名义奖赏三名勇士两个桃子，请他们自己评功，按功劳大小分吃桃子。[e-mail]三名勇士都认为自己功劳很大，应该单独吃一个桃子。于是，公孙接讲了自己的打虎功，拿了一只桃子；田开疆讲了自己的杀敌功，也拿了一只桃子。两人正要吃桃时，古治子讲了自己更大的功劳。田开疆、公孙接觉得古治子功劳确实大过自己而羞愧不已，拔剑自刎。古治子见了，后悔不迭。心想：“如果放弃桃子隐瞒功劳，则有失勇士威严；但若争功请赏羞辱同伴，又有损哥们义气。如今两位兄弟都为此绝命，我独自活着还有何意义？”于是，古治子一声长叹，拔剑结束了自己的生命。[e-mail]晏婴采用借“桃”杀人的办法轻易地除去了心腹之患。这里，他利用了数学中的一个简单而有用的原理：抽屉原理。数学欣赏[e-mail]抽屉原理的简单形式[e-mail]所谓抽屉原理，又叫鸽笼原理，它是组合数学中一个最基本的原理，可以用来解决许多涉及存在性的组合问题。其基本内容为：把m个物体放到n个抽屉中，如果物体数比抽屉数多（即mn），那么，必然有至少一个抽屉里放入两个或两个以上的物体。[e-mail]这个原理有两个简单变形：1.把多于m×n个的物体放到n个抽屉中，那么，必然有至少一个抽屉里放入m+1个或m+1个以上的物体。2.把无穷多个的物体放到n个抽屉中，那么，必然有至少一个抽屉里放入无穷多个物体。[e-mail]抽屉原理I把m个物体放到n个抽屉中，那么，必然有（至少）一个抽屉里放入至少k个物体。这里时不整除当时整除当mn1mn,[e-mail]例如：1)在任意给定的3个整数中，必定有2个整数，其和是2的倍数（其算术平均值还是整数）。2)在任意给定的5个整数中，必定有3个整数，其和是3的倍数（其算术平均值还是整数）。3)在坐标平面上任意取5个整点（纵横坐标都是整数），则必定存在其中两个整点，其连线的中点仍是整点。[e-mail]4)在n维空间中，任意取2n+1个整点（纵横坐标都是整数），则必定存在其中两个整点，其连线的中点仍是整点。5)在3×4的长方形中，任意放置6个点，必有两个点的距离不超过。56)边长为1的正方形中任意放入9个点，在以这些点为顶点的各个三角形中，必有一个三角形，它的面积不大于1/8。数学欣赏[e-mail]聚会认友[e-mail]我们可能经常会遇到这样的情况：在一桌酒席上，十来个本来不相识的人坐在一起，经过不太久的交流，马上会有人找到自己的“知音”，他们可能是校友、同行、同乡、同姓、同年龄、同属相或者是朋友的朋友、朋友的同乡、同乡的朋友等。这种情况几乎在每次酒席中都会发生，以致让人感觉到这世界真是太小。难道这都是巧合吗？数学欣赏[e-mail]聚会的朋友[e-mail]我们经常会参加各种聚会。如果我说：在任何一种聚会中，一定有两个人，他们在场的朋友数是一样多的。你一定会很吃惊。但是，我们可以用抽屉原理来说明，这是千真万确的。数学欣赏[e-mail]六个人的聚会[e-mail]在任何6个人中，一定可以找到3个人，他们或者互相都认识，或者互相都不认识。数学欣赏[e-mail]抽屉原理的推广形式[e-mail]抽屉原理II把m个物体放到n个抽屉中，那么，必然有（至少）一个抽屉里放入至多个物体。[e-mail]例如设为区间(0,1)内的任意n+1个实数，那么，其中必有两个数，其差的绝对值小于1/n.121...nnxxxxSZU第三节七桥问题与图论数学欣赏[e-mail]背景[e-mail]七桥问题18世纪，位于现立陶宛内的哥尼斯堡镇，有一条河流叫普雷格尔河。河中有两个相邻的小岛，岛与岛、岛与陆地之间建有七座桥[e-mail]问题：一个人能否一次无重复地走遍所有的七座桥，最后回到出发点？这就是著名的“七桥问题”。1736年，一位小学教师写信给当时的著名数学家欧拉（Euler），请教对七桥问题的解答。欧拉用数学方法对七桥问题进行了深入的研究。数学欣赏[e-mail]欧拉的解答——七桥问题的数学模型[e-mail]@szu.edu.cn欧拉研究后发现：(1)这不是一个代数问题（代数问题研究量的大小、关系）;(2)这也不是一个平面几何问题（平面几何问题研究角度的大小、