当前课程知识点:组合数学 > 漫谈组合数学 > 最精巧的排列——幻方 > 幻方
同学们 你们知道这是什么吗
这就是最早的组合数学幻方
组合数学是一门非常古老的学科
它可以追溯到4000年前
在大禹治水年代
我们都知道大禹最大的贡献就是治理了黄河
有一个传说
当时大禹治水的时候
有一天正在发愁
漫步在黄河边上
这时从黄河里冒出来一只巨大的乌龟
这只乌龟不仅非常大
更加神奇的是
它的后背上有神秘的花纹
仔细看它花纹会发现
它后背被分成了九个格子
每个格子中有若干个点
如果我们把每一行的点数加起来
或者是每一列的点数
甚至是每一条对角线的点数加起来
都是十五
十五实际上在我们中国的日历中是非常重要的
我们每一个节气都是以十五为一个周期的
而大禹正是得到了这个神龟的启示
以十五为周期进行了黄河的治理
不仅仅在古代的文献中有有关幻方的资料
甚至在我们耳熟能详的一些影视作品中
也屡见不鲜
下面我们就看一些《射雕英雄传》的片断
住在黑沼小屋的瑛姑
一直研究三乘三的幻方该如何解决
但是十几年过去了
瑛姑仍然没有答案
直到黄蓉来到了黑沼小屋
你的算法自然精我百倍
可是我问你
将一至九这九个数字分成三列
不论纵横斜角
每三个数字相加都是十五
如何排法
九宫之义 法以灵龟
二四为肩 六八为足
左三右七 戴九履一
五为中间
只道这是我独创的秘诀
没想到却早有歌诀传世
那九宫每宫又可化为一个八卦
八九七十二数
以从一至七十二之数
环绕九宫成圈 每圈八字
交界之处又有四圈
一共一十三圈
圈圈相加 均为二百九十二
这洛书之图之中的神妙
想必你也不会了解
那是不是真的像黄蓉说的不足为奇呢
其实历史上最早研究幻方的
当数南宋的数学家杨辉
我们大家都知道杨辉三角就以他为命名
而除了这个之外呢
他写了一本非常有趣的书叫作《续古摘奇算法》
在里面他就详细地罗列了三乘三 四乘四 五乘五
甚至是十乘十的幻方
所以可以看到幻方除了乌龟上的那个三乘三之外
还有很多很多更大规模的幻方
而在西方呢
他们也发现了幻方的神秘
甚至有一幅非常有名的画
叫做《忧伤》
这幅画里面在它的角落处有一个四乘四的幻方
我们仔细观察一下
我们四乘四的幻方
最后一行中间两格
一个是十五一个是十四
这正是画家的精妙之处
因为这幅画正好是在1514年画的
所以可以看到幻方的排列的神秘
确实是超乎了人类的想象
同时有一些人觉得幻方蕴含了宇宙的秘密
因此在很多的宗教教义中
都把幻方作为护身符
甚至在他们的相关神庙上把幻方刻在了上面
那么我们要研究幻方
就首先要给它一个形式化的定义
一个幻方的重要组成部分
首先我们要有一个N乘N的方格
我们要将1 2 3
一直到N平方个这样的数字
放入到N乘N的方格内
而且要保证在同一行 同一列
以及它的对角线
各个数字相加之和是相等的
那么对于一个任意阶幻方
我们要去研究它
首先想知道他们每一行加起来应该是多少呢
所以来定义每一行
以及每一列
以及每一个对角线数字之和
我们称之为幻和
如果我们用小S来表示的话
对于一个N阶的幻方
我们想知道S等于多少
我们知道所有的数字的和是多少呢
1 2 3
一直加到N平方
我们都会算
1+2+3一直加到n平方
就应该等于n平方乘以n平方加1除以2
而这个数字呢
正好应该等于n倍的小S
所以幻方小S就应该等于n平方
乘以n平方加1除以2
再除以n
自然对于一个n阶的方阵
我们就知道它的幻和就应该等于
n乘以n平方加1除以2
既然对于每一个n
我们都能算出他的幻和
那么是不是所有的从1一直到n平方
这n平方个数字都可以放到n乘n的方格里
构成一个幻方呢
我们拿最简单的例子来看
就看2阶幻方
是不是存在一个2阶幻方呢
我们如何把1 2 3 4这四个数字放到2乘2的格子里
让它横竖和加起来全部都相等呢
我们先假设
是存在2阶幻方的
那么这2阶幻方就相当于
我们用ABCD这四个变量(有口误)来代替
如果存在一个2阶幻方
那么2阶幻方的幻和是多少呢
带入刚才的公式
我们算出来是2乘以2的平方加1再除以2
刚好等于5
那就意味着
我们在这样一个ABCD的组合下面
横着数A+B应该等于5
第二行C+D也等于5
斜着A+D C+B都应该等于5
这个时候我们发现了一个问题
如果我们有两个式子进行相减的话
就会有这样一个式子
B减去D等于0
而我们知道我们选择的这四个数字1 2 3 4
是不能相等的
这是幻方的定义
所以我们的假设是矛盾的
因此2阶幻方是不存在的
但是刚才我们又看到了三阶幻方 四阶幻方 五阶幻方
甚至是十阶幻方
到底存在不存在呢
实际上大约在三十年前
有一位德国的数学家
就已经证明了
对于任何一个大于等于3的数n
我都可以构造一个n阶幻方
既然比2阶大的所有的幻方都是存在的
我们自然而然就想
那该怎么去得到一个幻方呢
其实杨辉在他的书中就介绍了一种方法
如何去构造三阶幻方
他先把123 456 789斜向排列
然后再将他们的对顶角进行互换
构成了一个三乘三的格子
这就是一个三乘三的幻方
但是他这个方法只能适用于三阶的幻方
直到十七世纪的时候
才有一位法国的数学家研究了
如何来构造更大阶的幻方
当然他的方法也有一定的局限性
他只能处理奇数阶的幻方
他的思维是什么样子呢
他实际上想象
我这样一个n乘n的格子
并不是平的
他像一个转的一个轮回
而且同时他在摆放棋子的时候
希望每次都是朝着从左下到右上的方向
那么下面我们来拿三阶的幻方演示一下
下面呢我们用这样一个工具给大家介绍一下
三乘三幻方的构造
首先算法的第一步
我们要将1放在第一行的中间
这个算法的思路是下一个棋子
将沿着从左下角向右上角方向移动
那移动的过程中
肯定有可能会出了边界
这个时候有了这样的理想假设
我们觉得这样一个棋盘实际上是一个循环往复的
这时候如果2从1向右上角移动
将会出去
如果它是循环往复的
实际上它应该到这样一个位置
因此2应该落在这里
接着呢3往下走
如果它在这个方向上也是循环往复的话
那么3的位置应该在这里
根据从左下到右上的规则
我们发现4从3的位置向上移动
会和1重合
这时候出现了一个特殊的情况
如果下一个位置已经被占用的话
我们将这个棋子落在前一个位置的下方
所以4应该放置在这里
接着呢我们沿着从左下到右上摆放5和6
直到7的时候
我们会发现7要出去了
7要出去以后
循环往复它会到这个位置
所以发现这个位置已经被占用了
因此我们要回到前一个位置的下方
接着我们8从7到右上角已经出去
循环往复应该在这个位置上
以及我们最后一个位置归9所有
这样我们来看一下
8+1+6 8+5+2
任何一个形式下进行加的话
我们都可以得到幻和15
既然我们知道了奇数阶幻方应该怎么做
那么大家自然有一个疑问
对于任意阶幻方
是不是都有相应的方法呢
其实我们只要把幻方分成三类
第一类是奇数类幻方
第二类4m阶幻方
第三类是4m+2阶幻方
对于每一类我们都会有相应的算法
所以到目前为止
给你任何一个n
你都可以构造出来相应的n乘n方格的幻方了
但是我们回头看呢
回头看一下杨辉做出来的三阶幻方
和我们刚才用奇数阶做出来的幻方
两个幻方一样吗
咋一看这两个幻方的排列是不一样的
但是我们仔细一看
如果将这个幻方翻转一下
是不是两个幻方就一样了呢
这是三阶幻方
我们再拿四阶幻方来看一看
这边呢是我们当初那幅名画里面的幻方
这个幻方我们看到的是在一个神庙旁边刻画的幻方
同样是四阶幻方
他们的排列无论你怎么转怎么翻
他们都不一样
这就引出了一个问题
给你一个n(n>2)阶幻方
到底能有多少种不同的构造方法呢
其实幻方的计数一直困扰着人们
我们现在知道二阶幻方是没有的
三阶幻方如果认为翻转旋转是一样的话
它只有一个
到了四阶
它的基本形式已经有880个了
如果允许它翻转旋转
那么将有7040个
到了五阶幻方
大家可以想像
有多少个五阶幻方呢
已经有2亿7000多万个五阶幻方了
六阶幻方是多少
大家已经算不出来了
甚至拿计算机也根本无法枚举
数学家经过仔细研究以后
决定了它是在一定的数量集范围内的
也就是1.77乘以10的19次方左右
七阶幻方有多少呢
大家对此一无所知
甚至它落在那个范围内
也是不知道的
可见计数是多么的困难
那幻方的研究是不是就到此为止了呢
其实我们刚才研究的都是普通的幻方
幻方还有更多种的变形
我们可以考虑任意的数列
不需要约定所有的数字都是连续的
同时呢我们不仅仅用普通的数字
甚至我们可以拿若干个素数摆到格子里面
构成一个幻方
有一些人还说了
我是横着加 竖着加
都相等
其实也有一些数学家研究横着乘竖着乘
都是相等的
这同样构成了一种特殊的幻方
幻方如此巧妙精巧
让无数人为之着迷
在1977年的时候
幻方作为人类智慧的象征
被宇宙飞船带上了太空
而同时我也发现幻方这样一个精巧的结构
实际上也是你表达心意的一种特殊的方式
其实在奥运会2008年的时候
有这样一条新闻吸引了我
78岁了农民包中祥设计出了一个非常别致的幻方
它是一个正六面体
它的每一个对角线
甚至是它每一个面上横竖加起来和值都是2008年
展开这样一个正六面体
它就像一颗心形
而这个心形的每一个交点
相加之和减掉中间的一个值
正好是2008
所以包中祥老先生花了三年的时间
设计出了这样一个完美的幻方
献礼奥运会
可以看到幻方它的发展可以是充分发挥你的想象
幻方里面的内容博大精深
在组合数学中有很多类似的精巧结构
那么刚才我们涉及的是有关我们中国
甚至是东方的组合数学发展
大家肯定想知道
那西方呢
在西方世界里面
组合数学是如何起源和发展的呢
我们下节课将会深入的展开
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(1)
--采访武永卫老师
-第一周作业
--作业说明
--H
--U
--G
--作业讨论区说明
-第一周演示程序
--程序讨论区说明
--幻方生成器
--换方计数
--屏幕解锁方案数
--欧拉路计数
--共享程序
-加减乘除来计数
--计数的基本法则
-排列还是组合
--排列还是组合
--小乒乓球的组合之旅--排列还是组合
-各种各样的排列
--圆排列和项链排列
--圆排列和项链排列--习题
--多重排列
--多重排列--练习
-多样的组合
--可重组合
--不相邻组合
--小乒乓球的组合之旅--多样的组合
-钟声里的全排列
--钟声里的全排列
--钟声里的全排列
--字典序法
--SJT算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验