组合数学 -幻方,如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。,四色问题,在日常生活中我们常常遇到组合数学的问题。,当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。,在中小学的数学游戏中，有这样一个问题，一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢？这就是一个很典型、很简单的组合数学问题。,我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是组合数学典型例子。,库房和运输的管理也是典型的组合数学问题。怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什么地方最便于存取（如存储时间短的应该放在容易存取的地方）,用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非方型的砖块来铺一个地面，能否铺满呢？这不仅是一个与实际相关的问题，也涉及到很深的组合数学问题。,组合数学又称为离散数学。广义的组合数学就是离散数学，狭义的组合数学是图论、代数结构、数理逻辑等的总称.组合数学是研究离散结构的存在，计数，分析，和优化等问题的一门学科。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化（最佳组合）等.,具体解决以下4个问题：满足一定条件的安排是否存在。在确知解存在的前提下，确定一切可能的安排个数。给出所有可能的安排。当对不同的安排有优劣标准时，求出最好的安排。简称存在、计数、安排、优化问题。起源于数学消遣和游戏。,例1、食堂现有单价分别为1元9元的菜各一种，按照三种菜为一组分配，须保证每组菜的合计价格都为15元，问有多少种分配方案?,如何构作幻方？,幻方也称纵横图、魔方、魔阵，它是科学的结晶与吉祥的象征，发源于我国古代的洛书九宫图。洛书被世界公认为组合数学的鼻祖，它是中华民族对人类的伟大贡献之一。同时，洛书以其高度抽象的内涵，对我国古代政治伦理、数学、天文气象、哲学、医学、宗教等等都产生了重要影响。,2500年前，孔子在他研究易经的著作系词上传中记载了：“河出图，洛出书，圣人则之。”,龙马背上驮了一幅图，上面有黑白点55个，用直线连成10数（如图 )即为“河图”。伏羲依此而演绎成八卦，后为周易来源。,“河图”,河图的排列是一、六在后，二、七在前，三、八在左，四、九在右，五、十背中。河图中的点数是五十五，其中一、三、五、七、九是天数，二、四、六、八、十是地数，天数累加是二十五，地数累加为三十，两数之和为五十五。河图中的天数是奇，是阳；地数是偶，是阴，阴阳相索。据古代哲学家的解释，河图中上、下、左、右、中五组数目分别与火、水、木、金、土五行有关。金、木、水、火、土这几种物质基本形态的生成与转换，甚至万物发育都可以从这图上得到启示。由此定义这十个自然数中一、二、三、四、五为生数，六、七、八、九、十为成数。从而得出五行相生之理，天地生成之道。,黄河支流洛水中，浮现出的神龟，甲上背有9种花点的图案，就是后人称之为的“洛书”。,数起源于远古时代黄河出现的河图与洛水出现的洛书，伏羲依靠河图画出八卦，大禹按照洛书划分九州，并制定治理天下的九类大法，圣人们根据它们演绎出各种治国安邦的良策，对人类社会与自然界的认识也得到步步深化。大禹从洛书中数的相互制约，均衡统一得到启发而制定国家的法律体系，使得天下一统，归于大治。,十三世纪，我国南宋数学家杨辉在世界上首先开展了对幻方的系统研究，欧洲十四世纪也开始了这方面的工作。著名数学家费尔玛、欧拉都进行过幻方研究，如今，幻方仍然是组合数学的研究课题之一，经过一代代数学家与数学爱好者的共同努力，幻方与它的变体所蕴含的各种神奇的科学性质正逐步得到揭示。目前，它已在组合分析、实验设计、图论、数论、群、对策论、纺织、工艺美术、程序设计、人工智能等领域得到广泛应用。,（1）洛书与幻方,把“洛书”用数字表达就是下面的数表，这就是我们今天要讨论的一个“幻方”。,最早有关幻方的文字记载是中国古代数学书数术拾遗，那里记载了上述源自“洛书”的方图，当时称为“九宫图”，我国南宋数学家杨辉称这种图为纵横图，欧洲人称之为魔术方阵或幻方。,长期以来，纵横图被作为一种数字游戏。直到南宋时期，杨辉将她作为一个数学问题而加以深入的研究。 杨辉在他的续古摘奇算法一书中，不仅搜集到了大量的各种类型的纵横图，而且对其中的部分纵横图还给出了如何构造的规则和方法，从而开创了这一组合数学研究的新领域。,一般地，把n2个不同数字依次填入由nn个小方格构成的正方形中，使得横行数字之和、直列数字之和以及对角线数字之和都相等，这样的数图叫做一个（n阶）幻方，各直线上数字之和叫幻和。是否对任意自然数n都存在n阶幻方？对每个n存在多少个n阶幻方？如何构作？这就是组合数学研究的问题之一。,（2）为什么要研究幻方？幻方有多少？,为什么要研究幻方？幻方起源于古老的传说，自古有一种神秘色彩，人们把她当作护身避邪的吉祥物。许多人热衷于研究幻方，起初，只是因为她包含了无尽的神奇之美，而且，研究幻方本身也是对人的智力的开发。喜欢幻方、研究幻方的人不仅限于数学家，还有物理学家、政治家；不仅有成年人，也有孩子。现代科学家研究幻方，已经远远不是为了好玩或驱灾避邪。电子计算机出现以后，幻方在程序设计、组合分析、人工智能、图论等许多方面发现了新用场。,台湾黎凯旋的易数浅谈中有这样的描述：从日本学习飞机知识的台湾驾驶员，第一堂课上的就是幻方知识课，因为幻方的构造原理与飞机上的电子回路设置密切相关。海上漂浮建筑， 首先要解决的问题，就是要将建筑面分割成方阵格，每格的建筑重量的确定，需要象构造幻 方一样巧妙设计，因为只有各线各方向上的重量处处均衡才能是建筑物不致于倾斜。,幻方中各数若是从1到n2的连续自然数，则称之为标准幻方。n阶标准幻方的幻和为 研究幻方，可以分类进行。按照幻方阶数的奇偶性，幻方可以分为奇数阶幻方与偶数阶幻方；偶数阶幻方中，阶数为4的倍数的幻方叫做双偶阶幻方（如4，8，12阶等）;其它的叫单偶阶幻方（如6，10，14阶等）。,还有一些特殊性质的幻方:如果一个幻方中的各数换为它的平方数后得到的数图还是幻方，则这个幻方叫做双重幻方或平方幻方；如果一个幻方的各横行、直列、对角线上各数字之积也分别相等，则称之为乘积幻方。,幻方有多少？ 可以很容易地证明，2阶幻方是不存在的。我国南宋时期数学家杨辉早在1275年就给出了310阶的幻方。目前，国外已经排出了105阶幻方，我国数学家排出了125阶幻方。,同一阶幻方，可以有多种不同的排法，阶数越大，排法越多。如果不包括通过旋转或反射得到的本质上相同的幻方，我们有：,3阶幻方只有1种；4阶幻方有880种；5阶幻方有275305224种（约两亿七千五百万）；7阶幻方有363916800种（约三亿六千四百万） ；8阶幻方超过10亿种。,刚才已经介绍，在阶数大于3时幻方的种类有很多，但能够具体构造出来的却不是很多。下面我们介绍4种构造幻方的通用方法。,（1） 杨辉与奇数阶幻方的构造 我国南宋时期数学家杨辉曾对幻方有过深入系统的研究，他于1275年给出了310阶的幻方。这里我们给出他关于奇数阶幻方的构造方法，这些方法记载于他的续古摘奇算经上。比如，对于3阶幻方，方法是：“九子斜排，上下对易，左右相更，四维挺进。”，具体操作如下图：,九子斜排 上下对易，左右相更 四维挺进,类似的原理可以构造5阶、7阶、9阶等奇数阶幻方。下图给出了5阶幻方的构造过程。,25子斜排,上下对易，左右相更,四维挺进,（2） 奇数阶幻方的构造,30 39 48 1 10 19 2838 47 7 9 18 27 2946 6 8 17 26 35 375 14 16 25 34 36 4513 15 24 33 42 44 421 23 32 41 43 3 1222 31 40 49 2 11 20,17 24 1 8 1523 5 7 14 16 4 6 13 20 2210 12 19 21 311 18 25 2 9,奇数（不妨n=5）阶的情况,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,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,1 居上行正中央,下数依次右上放。 上出格时往下放,右出格时往左放。排重便往自下放,右上出格一个样。,如果给定一个等差数列，我们也可以按照以上方式依次将数列数字填入方格构造出奇数阶幻方。,3. 偶数阶幻方的海尔(Hire)构造偶数阶幻方的构造总的来说要比较困难。下面介绍的是法国人海尔的方法。为此，我们先引入一个概念：,根数在一个n阶幻方的构造过程中，数字 p = 1，2，n的根数为n(p-1)例如，在四阶幻方中，1的根数为0，3的根数为8；在10阶幻方中，3的根数为20，5的根数为40。 下面是海尔构造n阶偶数阶幻方的方法与步骤（以4阶为例具体填数）：,（1）将1到4这4个数字分别从左到右（左小右大）填入方阵的两条对角线中,得方阵A；（2）把A中每一行的空格中填入1到4该行尚没有的剩余数字（左大右小）,使每行每列数字之和均为10,得方阵B；,方阵 A,方阵B,（3）把方阵B转置，即交换行列，此时得到方阵C，C中的数叫原始数； （4）把C中各原始数分别用其相应的根数替换，得方阵D；,方阵C,方阵D,（5）最后将B、D两方阵中对应数分别相加，便得到一个n阶幻方E。,幻方E,三阶幻方的编制和补充,四阶幻方的编制和补充,三阶幻方有技巧,3数斜着先排好,上下左右要交换,然后各自归位了!,数字依次先排好, 上下中间交叉换, 左右中间交叉换, 其他地方不要变!,4. 双偶阶幻方的构造 对于双偶阶幻方，我们有比较简单的构造方法。为此，我们先给出一个概念：,补数在一个n阶幻方的构造过程中，数字p=1，2，n2的补数为n2 + 1 p.例如，在四阶幻方中，1的补数为16，3的补数为14；在8阶幻方中，1的补数为64，5的补数为60, 10的补数为55 。下面我们以8阶幻方为例说明双偶阶幻方的构造方法。,首先将从1到82这82个自然数依次连续填入方阵各方格内（如图）,然后将两条对角线及方阵内与对角线平行间隔为两格的的斜线上的数字分别换为各自的补数，得到的方阵即是一个n阶（双偶阶）幻方。,九宫数图最基本的规律，是其纵横及对角线上三数之和都为15，且九个数相加之和为45，是15的3倍。,1. 九宫图的奥秘,438+951+276 = 834+159+672,香港业余数学家黄志华先生发现了下面有趣的现象：用幻方中的1，3，9，7顺时针构造四个两位数：97，71，13，39，以及逆时针构造四个两位数：31，17，79，93,