ACM组合数学

组合数学主讲人：万涛E-mail:[e-mail]组合数学简介组合数学是一个古老而又年轻的数学分支。组合学问题到处可见，通常分为两类大问题：(1)排列的存在性(2)排列的计数和分类引题棋盘的完美覆盖切割立方体幻方四色问题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!Nim取子游戏变化题目（2）实际上，“加石子”的性质并不影响结果。如果一方面对平衡态时选择加石子，那么另一方可以选择把加上的石子原样拿走，仍把平衡态留给对方。而本题由于猴子的爬行方向有限制，这个过程不可能无限进行下去。游戏总会有一个结束。Nim取子游戏变化题目（3）假设有n个Nim堆，每堆的石子数量为ai，现在把经典的Nim取子的方法改变，设一个集合s，这个集合里有k个数，每个数为si，我们说如果在任何一个堆里取石子的话，你只能拿个数在集合s中的一种情况。再规定，如果说哪个游戏人无法取子，则说明他输。请问如果给你一个这样的状态，你能否确定谁是赢家吗？Nim取子游戏变化题目（3）此问题为有限制的Nim取子问题，希望参考GameTheory论文中的Sprague-GrundyFunction。这种问题可以解决一类Nim取子问题。S-G函数（博弈论）1.如果说在普通的Nim取子的问题上，加一个特殊的限制，就是每个人在选择某一堆后，只能拿2m个石子，请问谁是最后的赢家？2.如果说在普通的Nim取子的问题上，加一个特殊的限制，就是每个人在选择某一堆后，不能拿超过这堆数量一半的石子，请问谁是最后的赢家？一些简单的知识鸽笼原理生成排列数容斥原理错位排列经典问题：在一个聚会上，n位绅士查看他们的帽子。有多少种方式使得这些绅士中没有人能够拿到他们来时所戴的帽子？错位排列定理：对于n≥1,递推表达式:)!1)1(!31!21!111(!nnDnn))(1(12nnnDDnDCatalan数第n个Catalan数为：Catalan序列递推关系式：nnnCn2111)1(12411CnCnnCnnCatalan数的经典问题1.P=a1a2a3...an为n个数a1a2a3...an的乘积,依据乘法的结合率,不改变其顺序,只用括号表示成对的乘积.试问有几种不同的乘法方案?2.n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？3.设在圆上选择2n个（等间隔的）点。请问将这些点成对的连接起来使得所得到的n条线段不相交的方法数是多少？经典的买票问题本次足球比赛的门票为50元，而站排买票的球迷有m个人手里拿着一张面值50元的钞票，有n个人手里拿着一张面值100元的钞票。工作人员事先忘了为售票处准备任何零钱，请问您是否能算出这(m+n)个人共有多少种排队方式买票，使售票处不至于出现找不开钱的尴尬局面？经典的买票问题此问题堪称经典，是因为如果说当m=n时，恰好是个Catalan数问题。并且可以轻松转化成2进制串01限制问题，和方格对角限制走法问题。但是由于题目中并没有说明m一定等于n，所以本问题要再复杂一点？经典的买票问题让我们先来看一个简单的引题请问从图中的左下角到右上角有多少条路径呢？（你只能向上走或者向右走）经典的买票问题A5A2A4A1A3B1B2B3B4如果将这个图的每一小段边进行编号又会怎样呢？？经典的买票问题答案很显然：对于A和B两组边，他们的排列顺序都应该符合1,2,3……,那么最后得出的答案（所谓的路径）也一定一个AiBj的序列，我们很容易的就得出路径的总数应该是：或者nnmCmnmC经典的买票问题假设我们巧妙的在格子上加一条对角线，又会出现什么情况呢？经典的买票问题其实此问题可以用递推的方法来解决：用f(m,n)表示m个50元和n个100元的人站排的方案数，有：othersnmfnmfnnmnmf),1()1,(010),(二分图二分图的构图应该说是一个难点。二分图的最大匹配：匈牙利算法（最大流）二分图的最优匹配：KM算法（最小费用流）二分图经典问题：稳定婚姻延迟认可算法