《毛付庆组合数学》由会员分享，可在线阅读，更多相关《毛付庆组合数学（8页珍藏版）》请在金锄头文库上搜索。
1、数学游戏漫谈摘 要：游戏与数学作为两项人类活动具有许多共同的特点,这种共性主要体现在它们的性 质、结构以及实践等三个方面.数学与游戏之间的关系是相互渗透、相互统一的关系.游戏的精 神一直伴随着数学的成长和发展，成为数学发展的主要动力之一；并从以下几个方面影响了数学 的发展：游戏激发了许多重要数学思想的产生,游戏促进了数学知识的传播，游戏是数学人才发 现的有效途径.此外,游戏还在数学教育中起着非常重要的作用.关键词：数学 游戏数学发展 数学贡献组合数学也称组合学,现代数学根据所研究的对象可分为两类： 连续数学：以微积分为基础，传统主流；离散数学：伴随计算机科学，方兴未艾.组合数学研究的中心问题是
2、按照一定的规划来安排一些与物件有关的问题。存在问题-当符合要求的安排并非显然存在或不存在时,首要的问题是证明或否定它的存在. 2计算问题或分类问题当符合要求的安排显然存在，或者已证明它存在时，求出这类安排的各抒己见,或者把它分类。3.构造问题（组合设计）把满足某种条件的安排构造出来. 4优化问题给出最优标准，找出满足给定条件的最优安排.游戏对于数学的作用至多起激发兴趣和调节情绪的作用。然而，事实上情况并非那么简单。考察一下数学与游 戏的关系,我们发现游戏与数学的关系非常密切。无论从数学知识的本身,还是数学活动的过程, 如从事数学活动的人们的动机、方法等方面都可发现游戏的因素。下面我们来看看一些
3、经典的数学游戏:（一）胃痛问题阿基米德以恶作剧、迷题及走捷径而闻名。从阿基米德宝典里，已发掘出一个会让人人玩到胃痛的14巧板游戏,在计算把14条不规则的纸带拼成正方形有多少种不同的拼法。答案是（二）七桥问题Pegel河横穿Kngsber城,河上建有七座桥 ，能否设计散步路线，走过所有七座桥,每座桥恰好经过一次而回到同一地点?Eulr于16年给以否定：图有这样的路线当且仅当每个点连接偶数条边。（三)3x+1问题x+1问题：对每一个正整数,如果它是奇数，则对它乘再加1;如果它是偶数，则对它除以2。如此循环，最终都能够得到1.例：72211412213420 15162 Tmas Olveira e
4、Silv用了巧妙的编程验证对所有小于100*250=15899908424的正整数均正确。(四)拉丁方阵与正交拉丁问题每名军官对应一个有序对(军团,军衔） 以9名军官为例: 军团阵列 军衔阵列 并置阵列 （拉丁方阵) （拉丁方阵） （正交拉丁方阵）Euler(1)：不存在4+阶正交拉丁方?Tarr（1900)：不存在6阶正交拉丁方，存在10阶正交拉丁方。Boe， hrihand和Parker（9)：当2时，存在t+2阶正交拉丁方!首次数学上了The NwYrkime的头版！（五）Nim取子游戏Nm取子游戏是由两个人面对若干堆石子进行的游戏。设有 1堆石子， 各堆分别含有n，2， ， 个石子。游
5、戏的目的就是选择最后剩下的硬币。游戏法则如下：（1) 游戏人交替进行游戏（2) 当轮到每个游戏人取子时，选择这些石子堆中的一堆，并从所选的堆中取走至少一个石子。想法: 2进制定义: 平衡态游戏结论:任何人可以在非平衡态做一次取子,使其变成平衡态。任何人在平衡态下取子一定会打破平衡态。（1）一局游戏在两个游戏人之间如下交替进行：游戏从一空堆开始。当轮到一个游戏人时，他可以往该堆中加进1, 2, 3或4枚硬币。往堆中加进第0枚硬币的游戏人为得胜者.确定在这局游戏中是游戏人还是游戏人I能够确保取胜.取胜的策略是什么？此问题是一个更简单的问题，答案很明显，我们发现游戏人I一定是赢家，因为他只需要保持他
6、和游戏人放硬币的数和为即可.又由于100可以被5整除,所以游戏人I一定是赢家.(）有一棵树，高度为h（10)，现在有（15）只猴子分别在树上个不同的位置，两个游戏人来玩这个游戏,在这种状态下，两个玩家可以命令任何一只猴子往上爬至少一个格子，当没有任何猴子有爬的空间时，这个玩家算为输掉了游戏?请问如果事先告诉你这些状态，你能判断出两个玩家的输赢吗？如果有偶数只猴子，则把两两相邻的猴子之间的距离看作一堆石子如果有奇数只猴子，把最上面一只猴子到树顶的距离看作一堆石子，剩下的猴子同上。实际上,“加石子的性质并不影响结果。如果一方面对平衡态时选择加石子,那么另一方可以选择把加上的石子原样拿走，仍把平衡态
7、留给对方。而本题由于猴子的爬行方向有限制,这个过程不可能无限进行下去。游戏总会有一个结束。（3）假设有n个Nm堆,每堆的石子数量为ai,现在把经典的Nim取子的方法改变，设一个集合s，这个集合里有个数,每个数为s，我们说如果在任何一个堆里取石子的话，你只能拿个数在集合中的一种情况。再规定，如果说哪个游戏人无法取子，则说明他输。请问如果给你一个这样的状态，你能否确定谁是赢家吗？此问题为有限制的m取子问题，希望参考Game heory论文中的Spage-rundy Function。这种问题可以解决一类Nm取子问题。（六)Kirkman女生问题有个女生,她们每天要做三人行的散步，要使每个女生在一周
8、内的每天做三人行散步时,与其她同学在组成三人小组同行时,彼此只有一次相遇在同一小组，应怎样安排？irman三元系：把v个女学生分成/3组，使得在每(v-1）/2天内任意两个女生在同一组内只相遇一次。RayChaudi和Wlson （197）：irkman三元系存在的充要条件是v=6k+3相类似的问题还有:任何六人中必有三人彼此相识或互不相识。以点表人，连实线表相识,虚线表不相识。那么六个点的完全图里或有实三角形或有虚三角形。五个点的则不然。 Ramsy(9031930)：给定任意正整数p和q，总存在一个最小正整数R(，q)，使得(p，q）个人中或者有p 个人互相认识，或者有 q 个人互不相识。
9、R（p,q) 称为Rmey数，只要人数足够多，则互相认识的人会越来越多，或互不相识的人会越来越多.amsy数的计算是对人类智力的挑战!例如R(4，5）=25（199年计算机1年的计算量）Ed用如下比喻说明其困难程度：一伙外星人入侵地球，要求一年内求得R(，5)，否则将灭绝人类！那么也许人类能集中所有计算机和专家来求出它以自保；但如果外星人问的是R（6，6） ,那么人类将别无选择，只能拼死一战了。“Kirkman女生问题”引出组合数学的一个重要分支组合设计.对这些数学游戏，一旦当人们认识到它们在数学和其他科学上的深刻含义后,便又促使人们对它进行更深入的研究，从而丰富了数学学科的内容和知识.该问题
10、就是最典型的组合设计问题.其本质就是如何将一个集合中的元素组合成一定的子集系以满足一定的要求。表面上看来,Kirkan女生问题是纯粹的数学游戏，然而它的解却在医药试验设计上有很广泛的运用。德国组合数学家利用组合设计的方法研究药物结构,为制药公司节省了大量的费用。在美国也有专门的公司用组合设计的方法开发软件,来解决工业界中的试验设计问题。（七)三十六军官问题普鲁士腓特烈大帝在一次检阅中要求:从不同的6个军团各选6种不同军衔的名军官共36人，排成一个行列的方队,使得各行各列的6名军官恰好来自不同的军团而且军衔各不相同。 36个军官问题这个纯粹来自智力游戏的题目孕育着艰深的数学问题 .Euler猜想
11、直到二十世纪中叶才获得解决，有两个原因：一是理论上的准备。这类问题用初等方法很难解决，二十世纪代数和几何的发展为解决问题提供了必要工具(如Galos域上的射影几何即有限几何等）;二是生产实际的推动。数理统计学家Fishr将正交拉丁方用于试验设计，例如，用二种原料合成某染料，每种原料有3个水平,怎样安排试验能使每种原料的各种水平各碰一次？这正好是3阶的正交拉丁方阵问题。 iher的试验设计是一股巨大的推动力量，把一种数学游戏变成了节约人力物力的具有重大价值的科学方法。（八）错位排列问题在一个聚会上，位绅士查看他们的帽子.有多少种方式使得这些绅士中没有人能够拿到他们来时所戴的帽子？定理:对于n 1
12、,递推表达式：第n个atalan数为：atalan序列递推关系式：经典的买票问题本次足球比赛的门票为5元，而站排买票的球迷有m个人手里拿着一张面值5元的钞票,有n个人手里拿着一张面值100元的钞票。工作人员事先忘了为售票处准备任何零钱，请问您是否能算出这（m+)个人共有多少种排队方式买票,使售票处不至于出现找不开钱的尴尬局面？此问题堪称经典,是因为如果说当mn时，恰好是个Cataln数问题。并且可以轻松转化成2进制串01限制问题,和方格对角限制走法问题。但是由于题目中并没有说明一定等于n，所以本问题要再复杂一点？ 4B3B1B2A5A2A4A1A3 如果将这个图的每一小段边进行编号又会怎样呢?
13、答案很显然:对于A和两组边，他们的排列顺序都应该符合,2,3，那么最后得出的答案(所谓的路径）也一定一个AiB的序列，我们很容易的就得出路径的总数应该是： 或者除了这些有趣的游戏外在我们的身边也常常遇到有关组合数学的问题。我国古代的河洛图上记载了三阶幻方,即把从一到九这九个数按三行三列的队行排列,使得每行，每列，以及两条对角线上的三个数之和都是一十五。组合数学中有许多象幻方这样精巧的结构。97年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。 在中小学的数学游戏中，有这样一个问题，一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时,狼要吃羊，羊要吃白菜，而他的船每趟只
14、能运其中的一个。他怎样才能把三者都运过河呢?这就是一个很典型、很简单的组合数学问题。航空调度和航班的设定也是组合数学的问题.怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，怎样作最合理的调整,这些都是 组合数学的问题。 对于城市的交通管理,交通规划，哪些地方可能是阻塞要地，哪些地方应该设单行道，立交桥建在哪里最合适,红绿灯怎样设定最合理， 如此等等，全是组合数学的问题. 一个邮递员从邮局出发，要走完他所管辖的街道,他应该怎样选择什么样的路径，这就是著名的中国邮递员问题，由中国组合数学家管梅谷教授提出，著名组合数学家, Edmnds和他的合作者给出了一个解答。 我们知道，用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状,而又非方型的砖块来铺一个地面，能否铺满呢？这不仅是一个与实际相关的问题,也涉及到很深的组合数学问题。 既然数学与游戏是如此紧密的联系在一起,因此在某种程度上可以说，游戏精神是数学发展 的主要动力之一。人们从事数学活动,就是在进行某种趣味四溢的游戏，数学中的游戏因素给数 学带来了无穷的魅力,从而吸引了一代又一代人的目光,大大加速了数学的发展.因而，不论是 数学家还是一般的游戏者都促进了数学事业的发展。此外,游戏对数学的发展还表现在另外三个 方
