朱全民组合数学.pptVIP

组合数学 长沙市雅礼中学 朱 全 民 什么是组合数学 生活中常见的组合问题 计算赛制下的总的比赛次数 幻方 笔画网络图 扑克牌游戏 组合数学问题常呈现的形式 能否排列…… 存在一个……..吗 能用多少种方法 计算……的数目 研究一个已知的排列 构造一个最优的排列 组合数学是研究离散结构的存在、计数、分析和优化等问题的一门科学 棋盘的完美覆盖 考虑一张普通的国际象棋棋盘，他被分成8*8的64个正方形。设有形状一样的多米诺骨牌，每张牌恰好覆盖棋盘上相邻的两个方格。那么，是否能够把32张多米诺牌放到棋盘上，使得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且所有的方格都被覆盖住？ 我们把这样一种排列称为棋盘被多米诺牌完美覆盖。 Fischer在1961年发现，它24*(901)2种 如果将棋盘换成m*n的呢，还存在完美覆盖吗？ 不难看出，m*n为偶数时，存在完美匹配。 如果用一把剪刀剪去8*8的棋盘一幅对角上的两个方格，剩下62方格，能否用31个多米诺牌进行完美覆盖吗？ 一块被切割过的棋盘具有完美匹配的必要和充分条件是什么？ B牌完美覆盖 对于m*n棋盘被多米诺覆盖的问题，还存在另外一种一般化的方法。设b是一个1*1的方格并排连接成1*b的方格条来代替多米诺牌。我们称这些方格条为b-牌。因此，一张b牌可以盖住一行上或者一列上的b个连续的方格。 那么，何时m*n的棋盘具有一个b牌的完美覆盖？ 结论： 一张m行n列棋盘有一个b牌的完美覆盖，当且仅当b是m的一个因子或b是n的一个因子。 怎样证明？ 切割立方体 考虑一个边长3英尺的立方体木块。我们希望把它切割成27个边长1英尺的小立方体。完成这项工作所需最小切割次数是多少？ 一种方法是依序切割6次，每个方向上切割2次并在切割时保持该立方体不变 如果在每次切割后重新排放所切得的各块，则是否能用更少的切割次数完成这项工作呢？ 考察一个4*4棋盘，它有一个8张多米诺牌的完美覆盖。 证明总能把棋盘横向或者纵向切成两块且不使这些多米诺牌被切断。 切割的水平或竖直的直线叫做完美覆盖断层线。 幻方 一个n阶幻方是由整数1,2,…,n2,组成，其每行、每列和两条对角线的和都等于同一个数s。 这个整数s叫幻方的幻和。 一个n阶幻方的所有整数和 s=1+2+…+n2= n2(n2+1)/2 怎样构造幻方？ 幻方在3为情况下的情况呢？ 四色问题 考虑一张平面图或在一个球面上的地图，地图上的国家都是连通区域，为了能够很快分出国家，需要对这些国家着色，以使得具有共同边界的国家被涂成不同颜色(角点处不算着共同的边界)，能够保证如此着色每一张地图所需的最少的颜色是多少？ 答案：4种颜色即可 证明？ 36军官问题 设有分别来自6各军团共有6种不同军衔的36名军官，他们能否排成6*6(6行6列的编队使得每行每列都有各种军衔的军官1名)，并且每行每列上的不同军衔的6名军官分别来自不同的军团？ 问题是，使36个序偶(i,j)，能否排成6*6的阵列，使得每行每列，这6个整数都能以某种顺序出现在序偶第一个元素的位置上。 看n=3的情况 1 2 3 1 2 3 (1,1) (2,2) (3,3) 3 1 2 2 3 1 (3,2) (1,3) (2,1) 2 3 1 3 1 2 (2,3) (3,1) (1,2) 是否存在6阶正交拉丁方？如何构造？ 最短路经问题 考虑一个由道路和路口组成的子系统。一人想从一个路口A行进到另一路口B。现在问题是要确定一条通路，沿此通路从A到B的距离最小——一条最短路径。 这是一个关于图的问题，图是组合数学中已经研究而且还将广泛研究的离散结构的一个例子。 怎样求最短路径？ Nim取子游戏 Nim取子游戏是由两个面对若干堆硬币（或石子,豆粒,…）进行的游戏。设有k=1堆硬币，各堆含有n1,n2,…,nk枚硬币。游戏的目的就是选择最后剩下的硬币。 规则如下： 游戏人交替进行游戏 当轮到每个游戏人取子时，选择这些硬币堆中的一堆，并从所选堆中取走至少1枚硬币。 所有的堆都变为空时，游戏结束，最后取子的人赢得所有的硬币。 如何取子？有何依据？ 组合数学基本理论 [ 加法法则 ] 设事件A有m种产生方式， 事件B有n种产生方式，则事件A或B之一 有m+n种产生方式。 集合论语言： 若 |A| = m , |B| = n , A?B = ? , 则 |A?B| = m + n 。 [ 乘法法则 ] 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m · n种产生方式。 集合论语言： 集合论语言： 若 |A| = m , |B| = n , A?B = {(a,