组合数学43574.ppt

组合数学 主讲人：万涛E-mail: wtommy84@ 组合数学简介 组合数学是一个古老而又年轻的数学分支。 组合学问题到处可见，通常分为两类大问题： 排列的存在性 排列的计数和分类 引题 棋盘的完美覆盖 切割立方体 幻方 四色问题 36军官问题 最短路径问题 Nim取子游戏 Nim取子游戏 Nim取子游戏是由两个人面对若干堆石子进行的游戏。设有k ≤ 1堆石子， 各堆分别含有n1, n2, …, nk个石子。游戏的目的就是选择最后剩下的硬币。游戏法则如下： (1) 游戏人交替进行游戏 (2) 当轮到每个游戏人取子时，选择这些石子堆中的一堆，并从所选的堆中取走至少一个石子 Nim取子游戏 想法： 2进制 定义： 平衡态 游戏结论：任何人可以在非平衡态做一次取子，使其变成平衡态。任何人在平衡态下取子一定会打破平衡态。 Nim取子游戏变化题目（1）一局游戏在两个游戏人之间如下交替进行： 游戏从一空堆开始。当轮到一个游戏人时，他可以往该堆中加进1, 2, 3或4枚硬币。往堆中加进第100枚硬币的游戏人为得胜者。确定在这局游戏中是游戏人I还是游戏人II能够确保取胜。取胜的策略是什么？ Nim取子游戏变化题目（1）此问题是一个更简单的问题，答案很明显，我们发现游戏人II一定是赢家，因为他只需要保持他和游戏人I放硬币的数和为5即可。又由于100可以被5整除，所以游戏人II一定是赢家。 Nim取子游戏变化题目（2） 有一棵树，高度为h(≤108)，现在有n(≤105)只猴子分别在树上n个不同的位置，两个游戏人来玩这个游戏，在这种状态下，两个玩家可以命令任何一只猴子往上爬至少一个格子，当没有任何猴子有爬的空间时，这个玩家算为输掉了游戏？请问如果事先告诉你这些状态，你能判断出两个玩家的输赢吗？ Nim取子游戏变化题目（2） 仔细考虑这个Nim建模的问题，通过把Nim取子的问题转化成，又可取子，又可放子问题。 这样完全可以把n分为奇数、偶数两个情况，把每两个相临猴子的距离差作为Nim取子每堆石子的数量。 Nim取子游戏变化题目（2） 如果有偶数只猴子，则把两两相邻的猴子之间的距离看作一堆石子 如果有奇数只猴子，把最上面一只猴子到树顶的距离看作一堆石子，剩下的猴子同上。 Nim取子游戏变化题目（2） 实际上，“加石子”的性质并不影响结果。如果一方面对平衡态时选择加石子，那么另一方可以选择把加上的石子原样拿走，仍把平衡态留给对方。 而本题由于猴子的爬行方向有限制，这个过程不可能无限进行下去。游戏总会有一个结束。 Nim取子游戏变化题目（3） 假设有n个Nim堆，每堆的石子数量为ai，现在把经典的Nim取子的方法改变，设一个集合s，这个集合里有k个数，每个数为si，我们说如果在任何一个堆里取石子的话，你只能拿个数在集合s中的一种情况。再规定，如果说哪个游戏人无法取子，则说明他输。请问如果给你一个这样的状态，你能否确定谁是赢家吗？ Nim取子游戏变化题目（3）此问题为有限制的Nim取子问题，希望参考Game Theory论文中的Sprague-Grundy Function。 这种问题可以解决一类Nim取子问题。 S-G函数（博弈论） 1. 如果说在普通的Nim取子的问题上，加一个特殊的限制，就是每个人在选择某一堆后，只能拿2m个石子，请问谁是最后的赢家？ 2.如果说在普通的Nim取子的问题上，加一个特殊的限制，就是每个人在选择某一堆后，不能拿超过这堆数量一半的石子，请问谁是最后的赢家？ 一些简单的知识 鸽笼原理 生成排列数 容斥原理 错位排列 经典问题： 在一个聚会上，n位绅士查看他们的帽子。有多少种方式使得这些绅士中没有人能够拿到他们来时所戴的帽子？ 错位排列 定理：对于n ≥ 1, 递推表达式:Catalan数 第n个Catalan数为： Catalan序列递推关系式：Catalan数的经典问题 P=a1a2a3...an为n个数a1a2a3...an的乘积,依据乘法的结合率,不改变其顺序,只用括号表示成对的乘积.试问有几种不同的乘法方案?? n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？ 设在圆上选择2n个（等间隔的）点。请问将这些点成对的连接起来使得所得到的n条线段不相交的方法数是多少？ 经典的买票问题 本次足球比赛的门票为50元，而站排买票的球迷有m个人手里拿着一张面值50元的钞票，有n个人手里拿着一张面值100元的钞票。工作人员事先忘了为售票处准备任何零钱，请问您是否能算出这(m+n)个人共有多少种排队方式买票，使售票处不至于出现找不开钱的尴尬局面？ 经典的买票问题此问题堪称经典，是因为如果说当