毛付庆组合学.docVIP

数学游戏漫谈 摘 要：游戏与数学作为两项人类活动具有许多共同的特点，这种共性主要体现在它们的性 质、结构以及实践等三个方面。数学与游戏之间的关系是相互渗透、相互统一的关系。游戏的精 神一直伴随着数学的成长和发展，成为数学发展的主要动力之一；并从以下几个方面影响了数学 的发展：游戏激发了许多重要数学思想的产生，游戏促进了数学知识的传播，游戏是数学人才发 现的有效途径。此外，游戏还在数学教育中起着非常重要的作用。 关键词：数学 游戏 数学发展 数学贡献　 组合数学也称组合学，现代数学根据所研究的对象可分为两类： 连续数学：以微积分为基础，传统主流；离散数学：伴随计算机科学，方兴未艾。组合数学研究的中心问题是按照一定的规划来安排一些与物件有关的问题。 1.存在问题——当符合要求的安排并非显然存在或不存在时，首要的问题是证明或否定它的存在. 2.计算问题或分类问题——当符合要求的安排显然存在，或者已证明它存在时，求出这类安排的各抒己见，或者把它分类. 　　 3.构造问题（组合设计）——把满足某种条件的安排构造出来. 　　 4.优化问题——给出最优标准，找出满足给定条件的最优安排. 游戏对于数学 的作用至多起激发兴趣和调节情绪的作用。然而，事实上情况并非那么简单。考察一下数学与游 戏的关系，我们发现游戏与数学的关系非常密切。无论从数学知识的本身，还是数学活动的过程， 如从事数学活动的人们的动机、方法等方面都可发现游戏的因素。 下面我们来看看一些经典的数学游戏： （一）胃痛问题 阿基米德以恶作剧、迷题及走捷径而闻名。从《阿基米德宝典》里，已发掘出一个会让人人玩到胃痛的14巧板游戏，在计算把14条不规则的纸带拼成正方形有多少种不同的拼法。 答案是 （二）七桥问题 Pregel河横穿K?nigsberg城，河上建有七座桥 ，能否设计散步路线，走过所有七座桥，每座桥恰好经过一次而回到同一地点？ Euler于1736年给以否定： 图有这样的路线当且仅当每个点连接偶数条边。 （三）3x+1问题 3x+1问题：对每一个正整数，如果它是奇数，则对它乘3再加1；如果它是偶数，则对它除以2。如此循环，最终都能够得到1。 例：7→22→11→34→17→52→26→13→40→20→ 10→5→16→8→4→2→1 Tomas Oliveira e Silva用了巧妙的编程验证对所有小于100*2^50=112589990684262400的正整数均正确。 （四）拉丁方阵与正交拉丁问题 每名军官对应一个有序对（军团，军衔） 以9名军官为例： 军团阵列 军衔阵列 并置阵列 （拉丁方阵） （拉丁方阵） （正交拉丁方阵） Euler(1779)：不存在4t+2阶正交拉丁方？ Tarry(1900)：不存在6阶正交拉丁方，存在10阶正交拉丁方。 Bose, Shrikhande和Parker(1960)： 当t2时，存在4t+2阶正交拉丁方！ 首次数学上了The New York Times的头版！ （五）Nim取子游戏 Nim取子游戏是由两个人面对若干堆石子进行的游戏。设有k ≤ 1堆石子， 各堆分别含有n1, n2, …, nk个石子。游戏的目的就是选择最后剩下的硬币。游戏法则如下： (1) 游戏人交替进行游戏 (2) 当轮到每个游戏人取子时，选择这些石子堆中的一堆，并从所选的堆中取走至少一个石子。 想法： 2进制 定义： 平衡态 游戏结论：任何人可以在非平衡态做一次取子，使其变成平衡态。任何人在平衡态下取子一定会打破平衡态。 （1）一局游戏在两个游戏人之间如下交替进行： 游戏从一空堆开始。当轮到一个游戏人时，他可以往该堆中加进1, 2, 3或4枚硬币。往堆中加进第100枚硬币的游戏人为得胜者。确定在这局游戏中是游戏人I还是游戏人II能够确保取胜。取胜的策略是什么？ 此问题是一个更简单的问题，答案很明显，我们发现游戏人II一定是赢家，因为他只需要保持他和游戏人I放硬币的数和为5即可。又由于100可以被5整除，所以游戏人II一定是赢家。 （2）有一棵树，高度为h(≤108)，现在有n(≤105)只猴子分别在树上n个不同的位置，两个游戏人来玩这个游戏，在这种状态下，两个玩家可以命令任何一只猴子往上爬至少一个格子，当没有任何猴子有爬的空间时，这个玩家算为输掉了游戏？请问如果事先告诉你这些状态，你能判断出两个玩家的输赢吗？ 如果有偶数只猴子，则把两两相邻的猴子之间的距离看作一堆石子 如果有奇数只猴子，把最上面一只猴子到树顶的距离看作一堆石子，剩下的猴子同上。 实际上，“加石子”的性质并不影响结果。如果一方面对平衡态时选择加石子，那么另一方可以选择把加上的石子原样拿走，仍把平衡态