前言:
当前你们对“汉密尔顿图一定是欧拉图吗”大概比较重视,各位老铁们都需要剖析一些“汉密尔顿图一定是欧拉图吗”的相关知识。那么小编在网上收集了一些关于“汉密尔顿图一定是欧拉图吗””的相关内容,希望小伙伴们能喜欢,你们一起来学习一下吧!编者按:全文共约8000字,希望读者读完能感受到数学之美,此生不留遗憾。
硬说数学科学无美可言的人是错误的。美的主要形式是秩序、匀称与明确。
——亚里士多德
读大学期间,数理逻辑老师课上讲的一句话让我记忆犹深:人来到这个世界,就是为了欣赏它的美。
世界的美有多种,其中有一种叫数学之美。她不像艺术之美与自然之美那么相类似,但她深深地感染着人们的心灵,激起人们对她的欣赏,与艺术之美是十分相象的。数学之美,是很自然明白地摆着的。遗憾的是,许多人终其一生都没能欣赏她的美。
大学乃至中学学过的数学知识,大部分人过些年也就忘了。许多人最后的数学水平顺利还原到了小学毕业的层次,有些还是拜鸡娃所赐。但即便只具备小学毕业的数学水平,也足够欣赏数学之美。
为了让大家从小就学会欣赏数学的美,而不是陷入题海的彷徨,我精挑细选了12个小学毕业能理解的证明或推导分享给大家。这些问题本身在数学上具有非常重要的价值,可以说是中小学数学的基石,而这些命题本身的表述或证明过程又是如此的优美。
1. 勾股定理
定理表述:直角三角形ABC中,∠A=90°,则AC2+AB2=BC2。
上榜理由:把勾股定理排第一个,是因为它被誉为千年第一定理,在数与形之间架起了一座桥梁。数形结合是重要的数学思想,我国著名数学家华罗庚先生曾说过:数缺形时少直观,形少数时难入微;数形结合百般好,隔离分家万事休。此外,勾股定理的证明方法众多,现存有500多种证法,足以写一本书。
证明:
我这里给出《几何原本》的作者欧几里得的经典证明方法。这种方法虽然不如其它一些方法来得简洁,但却充分体现了平面几何方法的一些精髓:旋转、全等、等积变换等。
如图,分别以两条直角边和斜边往外作三个正方形, 连接FC, AD。
将ΔABD绕B点逆时针旋转90°即得到ΔFBC。因此,ΔABD和ΔFBC的面积相等(更严谨地,到中学可以用全等三角形判别定理。)。
ΔABD的面积=长方形BDLK面积一半。
ΔBCF的面积=正方形ABFG面积的一半。
因此,粉色正方形AGFB的面积和粉色长方形BDLK的面积相等。
同理,蓝色正方形AHIC的面积和蓝色长方形KCEL的面积相等。
由于:正方形BCED的面积=粉色长方形BDLK的面积+蓝色长方形KCEL的面积。
因此AC2+AB2=BC2
衍生话题:
下面这张图蕴含了“勾股定理”的11种证法。
(如果需要11种证明的详细解析,请在公众号xuanbamath菜单栏回复“勾股定理”)
2. 质数有无穷多个
定理表述:存在无穷多个质数。
上榜理由:这则定理本身在数论上有着非凡的意义,包括素数定理、孪生素数猜想、黎曼猜想等都是建立在这一结论的基础之上。无穷本身也是让大家着迷的话题。著名数学家希尔伯特曾说过:无限!再也没有其他问题如此深刻地打动过人类的心灵。此外,定理本身的证明也优美无比,堪称反证法的典范。
证明:用反证法。
假设质数为有限多个,不妨设所有的质数从小到大按顺序排列为:
p1<p2<…<pn
构造P=p1×p2×…×pn+1
那么P不能被p1,p2, …, pn中的任何一个整除,这说明:
要么P本身是质数,但P>pn, 矛盾;
要么P不是质数,从而包含p1,p2,…,pn之外的质因数,也矛盾!
因此,质数不可能是有限多个。
衍生话题:
顺便提一下,希尔伯特旅馆的老板为无穷多辆载着无穷多个客人的大巴安排住宿时,也利用了素数有无穷多这一结论。
3. 圆的面积公式
定理表述:半径为r的圆面积S=πr2
上榜理由:把圆的面积公式摆在第三位,主要是因为这一小学数学课本上就给出的推导过程蕴含着朴素的微积分思想,可以让小学生直观地感知什么叫无穷小,什么叫无限逼近。现在有部分鸡娃家长热衷于让娃娃们小学就开始学微积分,建议可以从圆的面积公式推导开始。
证明:
在解释圆的面积公式时,教科书上给了类似下面的示意图。
其实,这正体现了微分和积分的思想。
把一个圆切成无限多个小扇形,这个过程就是微分的过程,如下图。
当扇形的个数越来越多时,扇形就越来越小,扇形的面积近似于三角形OA1A2的面积。。
把这些小扇形的面积累加起来,得到整个圆的面积,就是积分的过程。
由于每个三角形OA1A2的面积是A1A2×OH÷2,所有三角形的面积之和就等于内接多边形的周长×OH÷2。
当分的扇形无限多时,内接多边形的周长逼近圆的周长,OH逼近圆的半径r,
整个圆的面积就等于圆周长×半径÷2=πr2。
衍生话题:
毕达哥拉斯曾说过:一切平面图形中最美的是圆形。圆周率π也是数学中最重要的两个常数之一。关于圆的更多话题,可以参考文章《圆周率的那点事》。
4. 被9整除的数的特征
定理表述:
一个十进制数能被9整除当且仅当其各位数字之和能被9整除。
如果不能被9整除,那么这个数除以9的余数即为其各位数字之和除以9的余数。
上榜理由:把这个简单的结论放在这里是因为它涉及数的最核心内容,即数的位值表示。在小学阶段,与其花大力气去学各种十进制数的速算技巧,不如把数的位值表示和交换律、结合律以及分配律搞搞清楚。数学越学到后面,越凸显出对基本概念理解的重要性。
证明:
先举个简单的例子。243可以按如下方式图示,即可以表示为:
243=2×100+4×10+3
=2×(99+1)+4×(9+1)+3
=2×99+4×9+(2+4+3)
由于2×99和4×9都能被9整除,因此243能否被9整除等价于2+4+3能否被9整除。
一般化地,
任何一个自然数n,都可以唯一表示成以b(b≥2)为基的位值表示。
n=ak×bk+ak-1×bk-1+…a1b+a0 (0≤ai<b 且ak≠0)
(注:这个本身是一则很重要的定理,即整数的位值表示定理。)
当b=10时,为十进制,可得:
n=ak×10k+ak-1×10k-1+…+a1×10+a0
= ak×(10k-1+1)+ak-1×(10k-1-1+1)+…+a1×(9+1)+a0
= ak×(10k-1)+ak-1×(10k-1-1)+…+a1×9+ak+ak-1+…+a1+a0
由于9|10i-1, 因此9| ak×(10k-1)+ak-1×(10k-1-1)+…+a1×9
从而,9|n当且仅当9|ak+ak-1+…+a1+a0
同时,n除以9的余数也就等于各位数字之和除以9的余数,即:
n mod 9 = (ak+ak-1+…+a1+a0)mod 9
衍生话题:
(1)可以将这一过程扩展到b进制数中,给出能被b-1整除的数的特征。
(2)模9取余可以用于加法和乘法的验算,也就是检查原来的表达式和运算结果除以9以后的余数是否相同,具体可以参考《如何用模9验算提高验算效率》。
5. 平方差公式
公式描述:两个数a, b的平方差等于这两个数的和乘以这两个数的差,即:
a2-b2=(a+b)(a-b)
上榜理由:把这个公式摆在这个地方有四方面的原因。首先,这个结论的代数证明可以帮助孩子训练小学最重要的一个运算律——分配律;其次,灵活运用平方差公式有助于加快计算;再者,这个公式在以后中学的学习中会被频繁使用;最后,它的几何证明方法非常优美,证明的思路也可以直接用于解决一类面积问题。
证明:
下面只给出它的几何证明。
如下图所示,假设大正方形边长为a, 小正方形边长为b。则大正方形面积减去小正方形面积,即为涂绿色部分的面积。我们可以把右上角那块绿色的长方形沿着灰色箭头方向,补到右边黄色阴影部分,从而和下面的绿色阴影部分拼成了一个长为a+b, 宽为a-b的长方形。因此: a2-b2=(a+b)(a-b)
衍生话题:
(1)基于平方差公式可以加快某些计算,比如计算1012-992,可以直接变成(101+99)×(101-99)=400。
(2)利用平方差公式有助于找出所有勾股数。
勾股数的性质是a2+b2=c2,其中a、b、c都是自然数,适当变形后为:
a2=c2-b2=(c+b)(c-b)
由于c+b, c-b的奇偶性相同,因此如果存在满足条件的解,那么a2应能分解为两个不同的数,且这两个数奇偶性相同。
据此可知,a=1, a=2时,都没有满足条件的解,下面列出了3≤a≤10的所有勾股数。
a=3时,a2=9=9×1,此时c=5, b=4
a=4时,a2=16=8×2,此时c=5, b=3
a=5时,a2=25=25×1,此时c=13,b=12
a=6时,a2=36=18×2,此时c=10,b=8
a=7时,a2=49=49×1,此时c=25, b=24
a=8时,a2=64=32×2=16×4,此时c=17, b=15或c=10, b=6
a=9时,a2=81=81×1=27×3,此时c=41, b=40或c=15, b=12
a=10时,a2=100=50×2=,此时c=26, b=24
6. 正方形的对角线和边长不可通约
定理表述:正方形的对角线与边长之比不能表示成有理数。
学完实数后,用最朴素的话来说,这个结论就是根号2不是有理数。如果不学实数,也可以问这个问题,也就是正方形的对角线与边长之比为什么不能表示成有理数?
上榜理由:数系的扩充是中小学数学学习的一条主线。通过这个问题的探讨,可以让孩子去触摸数系扩充的历史,从而对有理数和无理数形成清晰的认识,并做好小学和初中的衔接。这个结论的证明也一样优美,是集反证法、互素和奇偶性于一体的绝佳练习题。
证明:
假设对角线与边长之比c/a=p/q为有理数(其中,p,q互质),那么,根据勾股定理:c2=a2+a2=2a2,将c/a=p/q代入后得:p2=2q2。由此可得p为偶数,不妨设p=2k, 代入后有q2=2k2,从而q也为偶数,与p,q互质矛盾,因此c/a不可能是有理数。
衍生话题:
历史上,毕达哥拉斯曾认为一切数都可以表示为两个整数之比,即分数。但毕达哥拉斯学派的弟子希伯索斯发现的这个结论颠覆了毕达哥拉斯学派的理论基础,与其它几个悖论一起引发了第一次数学危机,最后导致了无理数的诞生。柏拉图曾说,如果不知道正方形的对角线和边长是不可通约的量,那他就不值得人的称号。
最后,不妨可以尝试一下用这个方法去证明根号3不是有理数。
7. 握手定理
定理描述:
在无向图G=<V,E>中,所有节点的度数之和等于边数的2倍。
在有向图G=<V.E>中,所有节点的入度之和等于所有节点的出度之和,所有节点的度数总和等于边数的2倍。
比如在上面这个图中,节点a, b, c, d的度数分别为4,3,5,2,度数之和14为边数7的两倍。
上榜理由:图论是数学的一个重要分支,它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。图论被广泛运用于计算机科学、运筹学等,而这个定理则在图论中起到基础作用。它的证明非常简洁,体现了一种整体思想,这种思想在图论的许多证明中都有所体现。
证明:
我们这里只对无向图给出证明。
考虑一条边,有下面两种情况:
如果它不是自环(即从边的两端是同一个顶点),那么它给相邻的两个顶点的度数都贡献了1,总共贡献2;
如果它是自环,则它给这个顶点的度数贡献了2。
因此无论是否为自环,一条边对度数之和的贡献为2,因此所有节点的度数之和即为边数的2倍。
根据握手定理,还可以推导出下面的推论:
任何无向图中,度数为奇数的节点数目一定是偶数。
衍生话题:
图论起源于一个非常经典的问题——柯尼斯堡(Konigsberg)七桥问题。大数学家欧拉由于解决了七桥问题成为了图论的创始人。欧拉图的证明,也蕴含了类似的思想。
图论中有许多看上去相似,但难度却有着天壤之别的问题,比如欧拉图和哈密尔顿图。
8. 带余除法表示定理
定理表述:设a是一个整数,d是一个正整数,那么存在唯一的q和r(0≤r<d), 使得a=dq+r。
上榜理由:带余除法的一个重要作用是将整数进行了分类。整数有无穷多个,通过带余除法,把无穷多个整数按照相同的特征分为有限多的类,从而使得我们可以进行分类讨论。包括抽屉原理、数论、群论等许多数学理论都建立在带余除法基础之上。
证明:证明需要分别证明存在性和唯一性。
先证明存在性。
将所有a-dq(q为整数)为非负的数构造一个集合,那么这个集合一定非空,因为q可以取任意大的负整数。
在这个集合中,取出最小的元素a-dq0,记其值为r,即a-dq0=r。
下面证明r<d。
假如r≥d, 那么a-d(q0+1)=a-dq0-d=r-d≥0也属于这个集合,并且r-d<r,与r=a-dq0是这个集合中的最小元素矛盾。
所以,q0, r满足要求。
下面证唯一性。
假设存在两组q1,r1,q2,r2同时满足:
a=q1d+r1=q2d+r2 (0≤r1,r2<d)
则有:(q1-q2)d=r2-r1
由于左边是d的倍数,因此d|r2-r1
由于0≤r1,r2<d,有:-d<r2-r1<d
只能是r2-r1=0, 从而q1=q2
唯一性得证。
衍生话题:
带余除法在小学阶段是如此重要,以至于很多人都不把它当成一个定理。实际上,带余除法不仅仅是关于数的,它也是中学时要学的多项式运算的基础,它是贯穿数论和代数的主线,对此可以参考林开亮老师关于“整数与多项式”的讲座。
9. 辗转相除法(欧几里得算法)
定理表述:
给定非负整数a≥b, 那么a, b的最大公约数gcd(a, b) = gcd(b, a mod b)
上榜理由:
辗转相除法是几种求最大公约数中的一种。把它列在这里有三点原因。一是它涉及了数学中重要的概念——带余除法;二是它在数论中的重要作用,除了可以快速地求出两个数的最大公约数之外,还可以用于证明裴蜀定理,在数论研究中被广泛使用;三是辗转相除法体现了递归或迭代的算法思想,而这类思想是解决许多数学与计算机问题的法宝。
证明:
设a=qb+r, 0≤r<b,则上面的等式变为gcd(a, b)=gcd(b, r)
假设d是a, b的公约数,那么d|a, d|b, 因此d|a-qb, 即d|r
所以,d也是b, r的公约数,从而gcd(a, b)≤gcd(b,r)
反之,如果d|b, d|r
那么d|qb+r, 即d|a
所以,d也是a, b的公约数,从而gcd(b,r)≤gcd(a,b)
因此gcd(a, b)=gcd(b, r)
衍生话题:
裴蜀定理表明,两个数a, b的最大公约数gcd(a, b)可以表示成a, b的线性组合,即存在整数s, t使得:sa+tb=gcd(a, b)。特别地,如果a, b互质,那么存在s, t, 使得sa+tb=1。
这一定理在数论中有重要的作用,而辗转相除法可以帮助确定这个线性表示的系数s, t。
10. 等差数列求和
上榜理由:等差数列求和在许多机构的小奥课程里已经被下放到了2、3年级。因此,很多人看到这个公式,已经没什么感觉了。但要知道,这个可是当年让高斯一鸣惊人的问题。我把它放在这里,一方面是因为这个公式在数学里的重要性,另一方面也是因为它在推导过程中所展现出的简洁、对称和整体美。
证明:
我们先看看高斯当年是怎么解决这个问题的。他的思路很简单,就是将和倒过来写一遍,然后上下相加。
S=1 + 2 + 3 + … + 100
S=100 + 99 + 98 + … + 1
2S=101×100
S=101×100÷2=5050
一般化地,对等差数列{ai}(ai =a1 +(i-1)d),做类似于上面的操作:
S=a1+a2 +…+an
S=an+an-1+…+a1
上下相加除以2有:
S=(a1+an)×n/2
=(2a1+(n-1)d)×n/2
=na1+n(n-1)d/2
衍生话题:
等比数列,即从第二项起,后面一项与前面一项之比是一个常数。等比数列求和也体现了类似的整体美,在两边同时乘以一个公比然后相减即可。例如:
S=1+3+9+…+3n-1+3n
3S= 3+9+27+…+3n+3n+1
上面减去上面得:
2S=3n+1-1
所以:S=(3n+1-1)/2
11. C(n,0)+C(n,1)+C(n,2)+…C(n,n)=2n
定理表述:
C(n,0)+C(n,1)+...C(n,n)=2n
其中,C(n,i)为从n个不同的物体中任意选i个的组合数。
上榜理由:
选择这个公式有三方面的原因。一是它与中学里重要的二项式定理相关,在数学上具有重要的意义;二是它和计数里的加法原理和乘法原理密切相关,可以直接看成是加法原理和乘法原理的应用;三是其证明过程正好展现了什么是一题多解。
证明:
我们这里不采用二项式里的证明方法,只使用小学生能明白的加法原理和乘法原理进行证明。
考虑下面的问题:
假设有n个不同的物品,要从中取若干个物品(可以1个不取,也可以全取),一共有多少种不同的取法?
基于加法原理,可以把满足上面要求的取法分为n+1类:
取0个物品:C(n, 0)=1
取1个物品:C(n, 1)
取2个物品:C(n, 2)
...
取n个物品:C(n, n)
所以,一共有:C(n,0)+C(n,1)+...C(n,n)种不同的取法。
换个思考方式,用乘法原理,把任务分成n步,第i步确定是否取物品i, 那每一步有两种选择,一共有2n种。
因此:C(n,0)+C(n,1)+...C(n,n)=2n
12. 多边形的内角和
定理表述:
对于简单n边形(n≥3 ),其内角和为(n-2)×180°。
注:所谓简单n边形是指不存在两条边交叉(比如五角星)的多边形。
上榜理由:把最后一个名额留个它有三个理由。一是小学里讲三角形内角和是180°这个结论时,是将三个角剪下来再拼成一个平角,让孩子直观感受这个结论,而数学需要理性的证明,这个问题正好展现了如何从感性直观上升到理性认知;二是因为小学乃至中学的大部分角度问题都要用到这个结论,特别是三角形的内角和是180°这个结论;三是这个定理涉及的内容广泛用在计算几何学中,为计算机图形学典型了基础。
证明:
首先,我们证明三角形的内角和是180°。
如下图所示,延长BC至CD。在ΔABC中,过C点做BA的平行线至CE。
由于BA//CE,
所以有:
∠DCE=∠B(同位角相等)
∠ECA=∠A(内错角相等)
因此:
∠A+∠B+∠C
=∠ECA+∠DCE+∠ACB
=180°
然后,我们证明n边形的内角和是(n-2)×180°。
由于任何一个n边形都可以分割为n-2个三角形(这个看似直观的结论本身也是一个定理,证明过程也很有意思),而每个三角形的内角和是180°,因此n边形的内角和即为(n-2)×180°。
衍生话题:
我们这里并没有要求多边形一定要是凸多边形,也可以是凹多边形。直观来看,凸和凹很容易理解,但怎么用数学的语言严格定义凸和凹,本身也是很有意思的话题,可以为以后要学习的凸函数和凹函数做铺垫。
当然,我只选了12条。数学里还有许多非常重要而且优美的数学结论,由于篇幅原因,无法一一罗列。我这里再挑三条重要的列在下面,证明大家可以自行搜索。
13. 算术基本定理(质因数分解唯一定理)
任何一个大于1的自然数N可以唯一分解成有限个素数的乘积,表示成:
其中p1,p2,p3,…,pn为素数。
可以说,这则定理的重要性一点都不亚于前面的定理,它奠定了素数作为自然数基本构成单元的重要思想。也因此,对自然数的研究可以转化为对素数的研究。这也是为什么几千年来无数人对素数如此痴迷的原因。关于素数更多的探讨,可以参考我的文章《孤独而高冷的素数》。
14. 容斥原理
容斥原理在计数中具有重要的地位。很多计数问题和离散概率问题的求解都依赖于容斥原理,比如欧拉函数(计算小于n的正整数中与n互质的数的数目)、装错信封问题等,都可以直接用容斥原理解决。
两个集合的容斥关系公式:|A∪B| = |A|+|B| - |A∩B |
三个集合的容斥关系公式:|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C|
两个或三个集合的容斥原理可以通过上面的韦恩图直观地表示,但对于多个集合,韦恩图就难以直观地展示集合之间的关系了。
一般化地,对于m个集合,有:
15. 实数和整数不等势
这则定理是关于无穷的。小学生都知道无穷大很大,但却不知道无穷大也可以分类。数学上,把正整数构成的集合作为可数无穷大。如果两个集合之间的元素能建立一一映射,那么就称这两个集合等势(或者具有相同的基)。
可以证明有理数和正整数集合等势,而实数集和正整数集合不等势。也就是说,有理数集合是可数无穷多,而实数集合不是可数无穷多。关于后者的证明,集合论缔造者康托给了一个小学生也能看懂的漂亮证明,有兴趣的可以自行查阅。
作者简介:昍(xuan)爸,中科院计算机博士,现为211大学计算机专业教授。曾获初中和高中全国数学奥林匹克联赛一等奖,江苏赛区第一名,高考数学满分。平时注重在生活中引导孩子进行数学思考,著有《给孩子的数学思维课》一书,开设有公众号xuanbamath。
本公众号创立四周年
为大家精选了12篇必读文章。
深度好文:小学数学应该学什么,怎么学?一个数学学霸爸爸辅导孩子的心路历程小学数学最重要的能力如何培养?是什么样的教育,竟要让我们的孩子以命相搏?奥数冠军教你如何解题(付费阅读,买一赠一)讲座视频:怎样在生活中引导孩子进行数学思考?为什么飞机的往返飞行时间不同?孤独而高冷的素数原来,毁掉一个孩子的深入思考这么容易!没有葫芦也要会画瓢, 说说我的奥数启蒙经历少儿编程,我这样教
12.李国杰院士作序推荐高考数学满分得主新书《给孩子的数学思维课》
标签: #汉密尔顿图一定是欧拉图吗 #举例说明整数的特征