第一章引言 所以,a1+3a5=60,3a4=15,a5=5,即数字5一定在中间位置 最后,我们再介绍一种非常有意思的幻方—素数幻方是指添入幻方中的数均为素数 895929 715101 自从素数幻方的概念提出之后,就有许多的学者对此展开了研究.其中较有意思的一种想法是利用最 前面的n2的奇素数来构造n阶素数幻方但是最后证明:当n≤11时,这是不可能的 2、费波那契数列 费波那契( Leonarde fibonacci)出生于1175年,是意大利的数学家.他在一本书中提出了一个很有 名的“兔子生兔子的数学问题”,即有一个人把一对小兔子放在四面都围着的地方,他想知道一年以后总共 会有多少对兔子?在这里我们假定一对小兔子一个月后就能长成大兔子,而一对大兔子一个月后就能生出 对小兔子,并且这些兔子都不会有死亡现象发生.显然,这是一个算术问题,但是却不容易使用普通的算 术公式进行计算 下面让我们先观察一下,看看有什么规律没有,为此我们用空心点表示一对小兔子,实心点表示一对大 兔子,则可以使用下面的图形来表示在6个月之中饲养的兔子的繁殖情况 用Fn表示在第n个月时,此人总共拥有的兔子数,Fm表示在第n个月时,此人总共拥有的大兔子 数,F表示在第n个月时,此人总共拥有的小兔子数 我们把上面图形中的点的个数计算成下面的表格,并且观察一下规律 F F
第一章 引言 所以, + ∑ =60, =15, ,即数字 5 一定在中间位置. = 9 i 1 ai 3a5 3a5 a5 = 5 最后,我们再介绍一种非常有意思的幻方---素数幻方是指添入幻方中的数均为素数. 17 113 47 89 59 29 71 5 101 自从素数幻方的概念提出之后,就有许多的学者对此展开了研究.其中较有意思的一种想法是利用最 前面的 的奇素数来构造 阶素数幻方.但是最后证明:当 2 n n n ≤11时,这是不可能的. 2、 费波那契数列 费波那契（Leonarde Fibonacci）出生于 1175 年,是意大利的数学家.他在一本书中提出了一个很有 名的“兔子生兔子的数学问题”,即有一个人把一对小兔子放在四面都围着的地方,他想知道一年以后总共 会有多少对兔子？在这里我们假定一对小兔子一个月后就能长成大兔子,而一对大兔子一个月后就能生出 一对小兔子,并且这些兔子都不会有死亡现象发生.显然,这是一个算术问题,但是却不容易使用普通的算 术公式进行计算. 下面让我们先观察一下,看看有什么规律没有,为此我们用空心点表示一对小兔子,实心点表示一对大 兔子,则可以使用下面的图形来表示在 6 个月之中饲养的兔子的繁殖情况： 用 表示在第 个月时,此人总共拥有的兔子数, 表示在第 n 个月时,此人总共拥有的大兔子 数, 表示在第 个月时,此人总共拥有的小兔子数. Fn n Fnd Fns n 我们把上面图形中的点的个数计算成下面的表格,并且观察一下规律： n 1 2 3 4 5 6 Fnd 0 1 1 2 3 5 Fns 1 0 1 1 2 3 Fn 1 1 2 3 5 8 - - 8
第一章引言 当n≥1时,由Fn,Fn,Fn的定义有 Fn=Fnd +Ens, Fns=fald, end= Falt 所以当n≥3时,我们得到递推关系式 F=Fd+F= F-l+ F-ld=f-l+F 其中F1=F2=1 经过计算我们知道F2=23,F42=267914296,即如果你有一对小兔子,则一年后你有233对兔子,三年 半后你会有两亿多对兔子.当然我们知道兔子不会以这样的速率生育,所以这只不过是一个假设的问题. 设F=F2=1,而当n≥3时,令F=F=1+F=2,则我们为纪念费波那契( Leonarde fibonacci),把 此数列{E}={1,1,2,3,5,8,13,21,34,55,89,144,233,377,…}称为费波那契数列.另外,法国数学家 E. Lucas在研究数论问题时,发现素数的分布问题与费波那契数列有密切的关系,他发现的数列为,当n≥3 时 其中L1=1,L2 Lucas数列与 Fibonacci数列有一个共同的性质,即从第二项以后的项由前面两项的和组成 个很有意思的问题是问:在 Fibonacci数列中是否具有有限个素数?数学家 Grahan构造了一个初始 项F,F使得以此为初始项的 Fibonacci数列之中根本就没有素数出现!对 Fibonacci数列和素数之间的关 系我们不想做更深入的讨论,感兴趣的读者可以参看其他有关的书籍 Fibonacci数列在组合数学问题的研究中是经常出现的把 Fibonacci数列表示为二项式系数之和是 种很有意思的表示法 定理2.1当n≥0时,第n个 Fibonacci数 F 其中k=/+1 证明令Cn=C01+C2+Cn3+…+Cn,则我们只需指出数列C满足 Fibonacci i条件,即 C=C1+C,C1=C,=1即可 首先,C1=C0=1,C2=C 其次,因为,当>t时有C1=0,所以Cn=∑C故
第一章 引言 当 n ≥ 1时,由 , , 的定义有 Fn Fnd Fns FF F n nd = + ns Fns , = Fn d −1 , F F nd n = −1 , 所以当 n ≥ 3 时,我们得到递推关系式： FF F F F F F n nd ns n n d n n =+= + = + −11 1 − − −2 2 其中 . 1 2 F F = =1 经过计算我们知道 =233, =267914296,即如果你有一对小兔子,则一年后你有 233 对兔子,三年 半后你会有两亿多对兔子.当然我们知道兔子不会以这样的速率生育,所以这只不过是一个假设的问题. F12 F42 设 F F 1 2 = =1,而当 时,令 n ≥ 3 FF F nn n = + −1 − ,则我们为纪念费波那契（Leonarde Fibonacci）,把 此数列{ }={1,1,2,3,5,8,13,21,34,55,89,144,233, 377,…}称为费波那契数列.另外,法国数学家 E.Lucas 在研究数论问题时,发现素数的分布问题与费波那契数列有密切的关系,他发现的数列为,当 时 Fn n ≥ 3 LL L nn n = −1 2 + − 其中 , . 1 L =1 2 L = 3 Lucas 数列与 Fibonacci 数列有一个共同的性质,即从第二项以后的项由前面两项的和组成. 一个很有意思的问题是问:在 Fibonacci数列中是否具有有限个素数?数学家Graham构造了一个初始 项 使得以此为初始项的 Fibonacci数列之中根本就没有素数出现!对 Fibonacci数列和素数之间的关 系我们不想做更深入的讨论,感兴趣的读者可以参看其他有关的书籍. 0 1 F F, Fibonacci数列在组合数学问题的研究中是经常出现的.把 Fibonacci数列表示为二项式系数之和是一 种很有意思的表示法. 定理 2.1 当 n ≥ 0时,第 n 个 Fibonacci 数 01 2 123 k FC C C C nn n n n 1 k − = + + ++ − − − " − , 其中 1 [ ] 2 n k + = . 证明 令 01 2 123 k CC C C C nn n n n 1 k − = + + ++ −− − " − k ,则我们只需指出数列 满足 Fibonacci 条件 ,即 , 即可. Cn CC C nn n = + − − 1 2 1 2 C C= =1 首先, ; 0 0 10 21 CC CC == == 1, 1 其次,因为,当 s t > 时有 0 ,所以 s Ct = 1 1 0 n k n n k C C − − − = = ∑ .故 - - 9
第一章引言 C.,+C 刀-3-k 2-k -2-k+Ck-1 n-1-k C 如果我们仔细验算一下 Fibonacci数列中相邻两项的商,就会发现一个非常有意思的现象,即它们的值 与黄金分割数0.618…有非常密切的联系(提示:相邻两项的商构成的数列的极限) 另外,很有意思的一个现象是在我们的日常生活中,有许多植物花朵的排列是符合 Fibonacci数列的 如向日葵种子的排列方式就是按 Fibonacci i数列的如果你仔细观察向日葵的花盘,就会发现种子组是按顺 时针和逆时针交错排列,彼此咬合的,并且顺时针和逆时针的组数往往是34和55,55和89,89和144;再如 菠萝果实的鳞片也有类似的 Fibonacci数列规律,即8行向左倾斜,13行向右倾斜;另如我们常见的落叶松 的果实—松塔的果片,向两个方向的排列也是按5行和8行排的……这似乎表明植物的生长是受数学规 律约束的,即植物离不开 Fibonacci数列! 3、有趣的走路问题 七桥问题伟大的数学家欧拉(L. Euler1707-1783)在被请到俄国做研究工作期间,他的一位德国朋 友,向他求教了一个令许多哥尼斯堡(德国的一个小城镇 Konigsberg)人感到困惑的问题:原来在这座城 中有一条河横贯市中心,河中心有两个小岛.在当时有七座桥把这两个小岛和对岸联结起来.见下面的图 当时有人曾想办法从家里出发走过所有的桥回到家里,他们想是否能够从某座桥出发使得所走过的桥 都只过一次呢?许多人都尝试过,但都没有获得成功,那么现在是否有一种办法,能把所有的桥都走过一次 呢?欧拉的朋友将这个“哥尼斯堡七桥问题”告诉了欧拉,并且要他想法子解决 欧拉并没有真的去哥尼斯堡,而是把这个问题进行了数学处理:把两岸和两个小岛缩成一点,把桥化为 边,两个顶点有边线联结.欧拉得到了下面的图: 欧拉考虑这个图能否用一笔画成,如果能够一笔画成的话,则对应的七桥问题也就解决了.为此,欧拉 先研究了一般的能一笔画出的图形应该具有什么样的性质?他发现其中的点可以分为两种,全部点都是偶 点或者有两个点是奇点(进出点的边数是偶数的点称为偶点;进出点的边数是奇数的点叫奇点) 我们知道,如果一个图能够用一笔画出,那么在这个图上一定有一个点是始点(起笔点),一个点是终 点(收笔点),其它的点为过路点 首先,我们看过路点具有的性质在这种点一定是有进有出的,不可能有进无出或者有出无进,即这类
第一章 引言 23 22 0 1 12 2 3 2 2 2 00 11 2 2 0 1 0 2 22 2 1 1 1 2 0 1 1 10 1 1 ( ) nn nn kk kk n n nk nk n nk n kk kk n n k k k n nk nk n n k k k n kn k n nk nk k k CC C C C C C C CC C C C CC C −− −− − − − −− −− − −− − == == − − − − − − − −− − − = = − − − − − − − = = += + =+ + =+ + =+ =+ += ∑∑ ∑∑ ∑ ∑ ∑ 1 0 . n Cn − ∑ = −k 如果我们仔细验算一下 Fibonacci 数列中相邻两项的商,就会发现一个非常有意思的现象,即它们的值 与黄金分割数 0.618…有非常密切的联系(提示:相邻两项的商构成的数列的极限). 另外,很有意思的一个现象是在我们的日常生活中,有许多植物花朵的排列是符合 Fibonacci 数列的. 如向日葵种子的排列方式就是按 Fibonacci 数列的.如果你仔细观察向日葵的花盘,就会发现种子组是按顺 时针和逆时针交错排列,彼此咬合的,并且顺时针和逆时针的组数往往是 34 和 55,55 和 89,89 和 144;再如 菠萝果实的鳞片也有类似的 Fibonacci 数列规律,即 8 行向左倾斜,13 行向右倾斜;另如我们常见的落叶松 的果实---松塔的果片,向两个方向的排列也是按 5 行和 8 行排的…….这似乎表明植物的生长是受数学规 律约束的,即植物离不开 Fibonacci 数列! 3、 有趣的走路问题 七桥问题 伟大的数学家欧拉（L.Euler 1707-1783）在被请到俄国做研究工作期间,他的一位德国朋 友,向他求教了一个令许多哥尼斯堡（德国的一个小城镇 Konigsberg）人感到困惑的问题：原来在这座城 中有一条河横贯市中心,河中心有两个小岛.在当时有七座桥把这两个小岛和对岸联结起来.见下面的图 示： 当时有人曾想办法从家里出发走过所有的桥回到家里,他们想是否能够从某座桥出发使得所走过的桥 都只过一次呢？许多人都尝试过,但都没有获得成功,那么现在是否有一种办法,能把所有的桥都走过一次 呢？欧拉的朋友将这个“哥尼斯堡七桥问题”告诉了欧拉,并且要他想法子解决. 欧拉并没有真的去哥尼斯堡,而是把这个问题进行了数学处理：把两岸和两个小岛缩成一点,把桥化为 边,两个顶点有边线联结.欧拉得到了下面的图： 欧拉考虑这个图能否用一笔画成,如果能够一笔画成的话,则对应的七桥问题也就解决了.为此,欧拉 先研究了一般的能一笔画出的图形应该具有什么样的性质？他发现其中的点可以分为两种,全部点都是偶 点或者有两个点是奇点（进出点的边数是偶数的点称为偶点；进出点的边数是奇数的点叫奇点）. 我们知道,如果一个图能够用一笔画出,那么在这个图上一定有一个点是始点（起笔点）,一个点是终 点（收笔点）,其它的点为过路点. 首先,我们看过路点具有的性质.在这种点一定是有进有出的,不可能有进无出或者有出无进,即这类 - - 10
第一章引言 点为偶点;其次,考虑始点与终点,并且这两个点不重合的情况,此时它们一定是奇点;再有,始点与终点重 合的情况,此时它们也是属于有进有出的点,即为偶点.综上,一个图要是能够一笔画出的话,则其中的点应 该有两个奇点,其余的点全部为偶点;或者其中的点都是偶数点 由于七桥问题中的点(4个)都是奇点,所以七桥问题不可能一笔画出.这就是说,一个人要想没有重复 地走过7座桥是不可能的 七桥问题是Eler在1736年解决的.一般地,该结论被视为图论历史上的第一个定理 Hamilton问题在1862年爱尔兰著名数学家 Hamilton提出了图论中一个著名的、至今还没有解决的 一个游戏问题:在有n个结点的图上,找出一个回路,使每个结点只能经过一次 自从 Hamilton提出这个问题以来,吸引了无数了学者对此问题展开了研究,但是到目前为止,还没有找 到一个判断一个图是否存在 Hamilton回路的充分必要条件 在这里我们仅就这个问题的特殊情形—“棋盘上的马步问题”予以简单介绍.我们知道国际象棋有 8×8=64个方格,而马的走法是“一步一斜角”.那么是否存在这样的一种走法,使得马走过棋盘上的每个 方格,而且每个方格只走一次 如下的解法是由法国著名数学家 De montmort和 De moivre给出的 344922113639241 2110355023123740 9|201|515463604126 324758615653‖143 198555259642742 7|1845305164328 注记把64个方格分为内外两部分,先从外层按同一方向走,除非不得已不要进入内层.外层添满后再 走入里层 4、有限射影平面 我们先看一个有趣的问题:有一位好客的女主人打算邀请7位朋友来家里聚会,每次聚会她只想邀请3 位宾客,但是她希望其中的任何两位朋友都恰好在一次聚会上见面,那么她应该怎样安排呢?这样的安排 是否存在? 我们简单试一下就会发现,任何两次聚会中必须有一位相同的朋友被邀请到.换句话说,如果第一次邀 请A、B、C,第二次邀请D、E、F,这样安排是行不通的.下面我们给出一种可行的安排方案: 第一次邀请A、B、C;第二次,邀请A、D、E:;第三次,邀请A、F、G;第四次,邀请B、D、F;第五次, 邀请B、E、G;第六次,邀请C、D、G;第七次,邀请C、E、F.我们可以用下面的一个图形来表示这个邀请 方案
第一章 引言 点为偶点；其次,考虑始点与终点,并且这两个点不重合的情况,此时它们一定是奇点；再有,始点与终点重 合的情况,此时它们也是属于有进有出的点,即为偶点.综上,一个图要是能够一笔画出的话,则其中的点应 该有两个奇点,其余的点全部为偶点；或者其中的点都是偶数点. 由于七桥问题中的点（4 个）都是奇点,所以七桥问题不可能一笔画出.这就是说,一个人要想没有重复 地走过 7 座桥是不可能的. 七桥问题是 Euler 在 1736 年解决的.一般地,该结论被视为图论历史上的第一个定理. Hamilton 问题 在 1862 年爱尔兰著名数学家 Hamilton 提出了图论中一个著名的、至今还没有解决的 一个游戏问题:在有 个结点的图上,找出一个回路,使每个结点只能经过一次. n 自从 Hamilton 提出这个问题以来,吸引了无数了学者对此问题展开了研究,但是到目前为止,还没有找 到一个判断一个图是否存在 Hamilton 回路的充分必要条件. 在这里我们仅就这个问题的特殊情形---“棋盘上的马步问题”予以简单介绍.我们知道国际象棋有 个方格,而马的走法是“一步一斜角”.那么是否存在这样的一种走法,使得马走过棋盘上的每个 方格,而且每个方格只走一次. 8 8 64 × = 如下的解法是由法国著名数学家 De Montmort 和 De Moivre 给出的. 34 49 22 11 36 39 24 1 21 10 35 50 23 12 37 40 48 33 62 57 38 25 2 13 9 20 51 54 63 60 41 26 32 47 58 61 56 53 14 3 19 8 55 52 59 64 27 42 46 31 6 17 44 29 4 15 7 18 45 30 5 16 43 28 注记 把 64 个方格分为内外两部分,先从外层按同一方向走,除非不得已不要进入内层.外层添满后再 走入里层. 4、 有限射影平面 我们先看一个有趣的问题：有一位好客的女主人打算邀请 7 位朋友来家里聚会,每次聚会她只想邀请 3 位宾客,但是她希望其中的任何两位朋友都恰好在一次聚会上见面,那么她应该怎样安排呢？这样的安排 是否存在? 我们简单试一下就会发现,任何两次聚会中必须有一位相同的朋友被邀请到.换句话说,如果第一次邀 请 A、B、C,第二次邀请 D、E、F,这样安排是行不通的.下面我们给出一种可行的安排方案： 第一次邀请 A、B、C；第二次,邀请 A、D、E；第三次,邀请 A、F、G；第四次,邀请 B、D、F；第五次, 邀请 B、E、G；第六次,邀请 C、D、G；第七次,邀请 C、E、F.我们可以用下面的一个图形来表示这个邀请 方案: - - 11
第一章引言 上面的图形是非常有名的!它是由数学家G.Fano在1892年提出的,实际上,它就是定义在二元域上的 二阶射影平面PG(2,2) 射影几何的研究始自法国数学家G. Desargues的1639年的著作,但是在当时并没有引起人们的重视 直到两个世纪后,由于法国著名数学家J.V. Poncelet著作(1822)的发表,射影几何才开始受到数学界的 重视,更使其成为19世纪几何学研究的重点.射影几何学在古典几何学中是最基础的、最广泛的而且是最 自由的它是公理化数学的典型范例之一,也可以说它是现代数学的先驱 定义射影平面(P,L)是由点集合P和线集合L构成的,并且是满足下面条件的平面 1、任意两个点决定一条直线,每条直线上至少有两个点; 2、任意两条直线都相交 3、存在4点集,使其中的任意三个点不在一条直线上 注意,定义中的条件3是为了排除射影平面只有一条直线的平凡情形的 定理4.1设(P,L)为射影平面,其中点集合P含v个点,线集合L有b条线,则存在一整数k≥2,使 v=b=k2+k+1,而且每条直线上有k+1个点过每个点有k+1条线 证明设任意的两条直线为1,l2,且1∩2=A,即直线1,2的交点为A.因为每条直线上至少有两个 点,所以通过点B可以建立从直线l至直线l2的单射故团s2同理有2≤1,所以阳=2于是我们 不妨假设每条直线上点的个数为k+1 B A 2 另外,我们可以将点集合P和线集合L互换,即将点看作线,而将线视为点,则显然这仍构成一个射影 平面所以过每个点的直线个数是k+1.进一步,我们可以再一次将点线集合互换,则有k=k 所以,"=b=k(k+1)+1=k2+k+1 米米
第一章 引言 上面的图形是非常有名的！它是由数学家 G.Fano 在 1892 年提出的,实际上,它就是定义在二元域上的 二阶射影平面 PG（2,2）. 射影几何的研究始自法国数学家 G.Desargues 的 1639 年的著作,但是在当时并没有引起人们的重视. 一直到两个世纪后,由于法国著名数学家 J.V.Poncelet 著作(1822)的发表,射影几何才开始受到数学界的 重视,更使其成为 19 世纪几何学研究的重点.射影几何学在古典几何学中是最基础的、最广泛的而且是最 自由的.它是公理化数学的典型范例之一,也可以说它是现代数学的先驱. 定义 射影平面( , P L) 是由点集合 和线集合 P L 构成的,并且是满足下面条件的平面 1、任意两个点决定一条直线,每条直线上至少有两个点； 2、任意两条直线都相交； 3、存在 4 点集,使其中的任意三个点不在一条直线上. 注意,定义中的条件 3 是为了排除射影平面只有一条直线的平凡情形的. 定理 4.1 设( , 为射影平面,其中点集合 含 个点,线集合 有 条线,则存在一整数 ,使 ,而且每条直线上有 个点,过每个点有 P L) P v L b k ≥ 2 1 2 kkbv ++== k +1 k +1条线. 证明 设任意的两条直线为l l 1 2 , ,且 1 2 ll A ∩ = ,即直线 的交点为 .因为每条直线上至少有两个 点,所以通过点 1 2 l l, A B 可以建立从直线 至直线 l 1 l2 的单射,故 1 2 l l ≤ .同理有 2 1 l l ≤ .所以 1 2 l l = .于是我们 不妨假设每条直线上点的个数为 k +1. 另外,我们可以将点集合 和线集合 互换,即将点看作线,而将线视为点,则显然这仍构成一个射影 平面.所以过每个点的直线个数是 .进一步,我们可以再一次将点线集合互换,则有 . P L k′ +1 k k = ′ 所以, . 2 v b kk k k = = + += + + ( 1) 1 1 - - 12