组合数学 教材: R. A. Brualdi, 组合数学, 机械工业出版社(影印版, 中译第4版)

Presentation on theme: "组合数学 教材: R. A. Brualdi, 组合数学, 机械工业出版社(影印版, 中译第4版)"— Presentation transcript:

1 组合数学 教材: R. A. Brualdi, 组合数学, 机械工业出版社(影印版, 中译第4版)
参考:1. 卢开澄, 组合数学,清华大学出版社 2. 吴文虎等, 程序设计中的组合数学, 清华大学出版社 网络教室: 组合数学 计算机学院软件所：王贵珍 Tel: Address: 中心教学楼905#

2 Motorola Internal Use Only
课 程 安 排 课程特点及最后成绩 1. 课程特点：技巧性较强。 2. 成绩评定：作业、程序设计占30％，期末为闭卷笔试考试，成绩占70％。  提示： 技巧的应用来自于经验的积累，所以 解决的组合数学问题越多，那么能够解决下 一个组合数学问题的可能性就越大。 预达目标： 高—— 中—— 低—— Motorola Internal Use Only

3 组合数学研究的内容 离散结构的存在、计数、分析 和优化。

4 例:棋盘的完美覆盖 m×n棋盘: m行n列方格, b-牌:1行b个的方格条 m×n棋盘被b-牌的一个完美覆盖是
(1) 每个格子恰好只被一张牌覆盖; (2) 每条b-牌覆盖b个方格. 34棋盘 66棋盘有4-牌的完美覆盖吗? 有2-牌的完美覆盖. 定理: m×n棋盘有b-牌的完美覆盖b|m或b|n.

5 棋盘覆盖及其变化 1 2 3 4 66棋盘用1,2,3,4如图填数，4牌在任何位置都覆盖1,2,3,4，去掉成组的1234, 多余1124。所以66棋盘不能用4牌完美覆盖。

6 完美覆盖 变化: 带禁止方格, 用多米诺牌(2-牌)覆盖 4×4棋盘去掉2格 4×5棋盘去掉4格 用多米诺牌(2-牌)覆盖 用多米诺牌覆盖

7 例:Nim取子游戏 设有k1堆硬币,各堆分别含有n1,n2,…,nk枚硬币. 游戏规则: (1)两游戏人交替取子;
(2)每人在一轮取子时只能取一堆中的硬币, 取至少一枚,至多全堆硬币; (3)所有堆都变成空堆时, 游戏结束, 最后取子的人获胜. 例1. (100, 389) 例2. (7, 8, 15) 游戏人I有必胜策略 游戏人II有必胜策略

8 平衡态 设有游戏(n1,n2,…,nk), 且各数的二进制展开是 ni=aisai(s-1)…ai1, i=1,2,…,k
若 a11+a21+…+ak1 (各数第1位之和), … a1s+a2s+…+aks (各数第s位之和) 都是偶数, 则称游戏处于平衡态. (7,8,15): (100,389): (7,12,13): 平衡态 非平衡态 非平衡态

9 平衡态与非平衡态的转化 n1 = a1s a1(s-1) … a11 n2 = a2s a2(s-1) … a21
nk = aks ak(s-1) … ak1 … … … … … Label = cs c(s-1) … c1 (7,8,15):平衡态 (100,389):非平衡态 (7,8,13):非平衡态 游戏终止时是平衡态 平衡态不能经一轮取子达到平衡态 非平衡态可经一轮取子达到平衡态(?)

10 结论 定理: 若游戏非平衡, 则游戏人I有必胜策略; 若游戏平衡, 则游戏人II有必胜策略.
定义: 若n1,n2,…,nk二进展开第i位的和是奇数, 则称第i位是非平衡位. 命题: 设一游戏最大非平衡位是第j位, 则 游戏人I可以从某堆取币使游戏达到平衡态 当且仅当 该堆币数二进展开第j位是1. 注意比较与习题1.33叙述的差别.

11 拉丁方 定义: 若A是由n个元素构成的n阶方阵, 其中每个元素在每行每列各出现一次, 则称A是拉丁方.
设A=(aij), 每个元素每行(列)只出现一次: aij=aik  j=k ( aji=aki  j=k )

12 36名军官问题 (18世纪)36军官问题: 6个地区, 6种军衔各一名. 将这36名军官排成6×6方阵, 使得
1)每行每列都有任一地区的军官; 2)每行每列都有任一军衔的军官. i :军衔, j :地区, 军官对应数偶(i, j), i, j[0,5] 问题等价于构造数偶(i,j)排成的6阶方阵, 使得 1) 数偶第一个数字构成拉丁方; 2) 数偶第二个数字构成拉丁方; 3) 每个数偶只出现一次. 传说普鲁士皇帝菲特烈喜欢阅兵

13 正交拉丁方 定义:设A=(aij)n×n,B=(bij)n×n是两个n×n拉丁方.
令C=((aij, bij))n×n,若C的n2对数偶互不相同, 则称A与B正交. 36军官问题等价于构造两个正交的6阶拉丁方. 例: 3阶正交拉丁方

14 正交拉丁方的实际意义 正交的拉丁方的一个应用: 药物配合试验 三种治发烧药和三种治感冒药, 对三位病人试验,
要求三天内每人都服这几种药, 比较配合疗效. 这时就可用上面讨论过的3阶正交拉丁方. 行:人, 列:天 (i,j): i,发烧药 j, 感冒药

15 Euler的猜测 令N(n)为两两正交的n阶拉丁方的最大个数. N(1)=2, N(2)=1, N(3)=2
定理2: 若n=pa, p是素数,a>0, 则N(n)=n-1. 定理3: 若n是奇数, 则N(n)2. 定理4: 若N(m)2,N(n)2, 则N(mn)2.(自学) 推论: 若n2且n4k+2, k0, 则N(n)2.(?) Euler(1707~1783)猜测: 对任意n=4k+2, k0, N(n)=1. 这4个结论的证明并不需要太复杂的数学知识.

16 Euler猜测的解决 1900年 Tarry(法) 验证了N(6)=1. 1959年 Parker(美) 证明 N(10)2.
1959年 Bose(印), Parker, Shrikhande(印) 证明 N(4k+2)2, 任意k>1.

17 N(n)  n-1 定理1: n>1, N(n)  n-1. 即若A1,A2,…,Ak是MOLS
(两两正交拉丁方), 则必有 kn-1. 置换的定义与表示: 置换: 有限集(例如{1,2,…,n})上的一一对应. 表示: p(1)=a1, p(2)=a2,…, p(n)=an, 注: a1a2…an是1,2,…,n的一个排列 则以 来表示该置换

18 置换 设 p是{1,2,…,n}上一置换, A=(aij)nn是矩阵, aij {1,2,…,n}
定义 p(A)= ( p(aij) )nn , 例: 2 3 1

19 p(A)性质讨论 若A是拉丁方, p是置换, p(A)是拉丁方吗? p(i)在每行每列只出现一次.
2. 若A是拉丁方, 则A与p(A)是否正交? A与p(A)组成的数偶只有: (i, p(i)), i=1,…,n 3. 若A与B正交, 则p(A)与B是否正交? 由于p是一一映射,所以 ( p(i1), j1)=( p(i2), j2)  ( i1, j1)=( i2, j2) p(A)与B不正交  A与B不正交

20 N(n)  n-1的证明 定理: 两两正交的n阶拉丁方不超过n-1个. 证明: 取k个n阶MOLS: A1, A2, … , Ak
取置换 pi ,使得pi(Ai)的第一行为1,2,…,n: … 则 p1(A1),…, pk(Ak)两两正交,且第二行第一个元素 满足: ) 不等于1; ) 互不相等. 所以 kn-1.

21 观察 p=5,k=1 p=5,k=2 p=5,k=3 p=5,k=4 每行分别左移1,2,3,4格 p阶方阵A1,A2,…,Ap-1:
Ak=(aij(k))p×p, k=1,2,…,p-1. aij(k)=k·i+j mod p, i, j[0,p-1] 定理: 设p为素数, 则N(p)=p-1. p=4, k=2

22 定理: 设p为素数, 则N(p)=p-1. 证明:Ak=(aij(k))p×p, k=1,2,…,p aij(k)=k·i+j mod p, i,j= 0,1,…,p-1 先证Ak是拉丁方: aij(k) = ait(k)jt mod pj=t aij(k) = asj(k)k(i-s)0 mod pi=s 再证Ag,Ah正交: 若(aij(g),aij(h))=(ars(g),ars(h)) 则 g(i-r)+(j-s)0 mod p, h(i-r)+(j-s)0 mod p 得 (g-h)(i-r)0 mod pi=r j=s 得证. key: a·b=0 mod p  a=0或b=0mod p. ( p=4? )

23 定理2: n=pa, p素数,a>0  N(n)=n-1
定义: 设集合F对可交换运算+和封闭, 满足 (1) <F,+>是群(记其么元为0), (2) 乘法分配律: a(b+c)=ab+ac (3) <F,>是半群, (4) 消去律: ab=0  a=0或b=0. 则称<F,+,>是一个域. F有限:有限域(Galois域GF) 注: (3)+(4)等价于<F\{0},>是群. 命题: 若n阶有限域存在, 则N(n)=n-1. 定理: p素数,a正, pa阶GF存在. GF的阶是素数幂. 这里的两个定理不用证明.

24 GF的构造方法 以GF(n)记n阶有限域. 对素数p, GF(p)=<{0,1,…,p-1}, + mod p,  mod p> 对a>0, 取a阶多项式xa+c1xa-1+…+ca, 满足: 各次项系数取值于GF(p) 没有根在GF(p)上 记其任一个根为, 令 F={b0+b1+…+ba-1a-1 : b0,b1,…,ba-1[0,p-1]} 则GF(pa)=<F, + mod p,  mod p >.

25 举例:阶为22的有限域 p=2，a=2 GF(p)= GF(2)=Z2=<{0,1}, + mod 2,  mod 2>,
取a阶多项式为x2+x+1， 令为方程x2+x+1 =0的根, F(pa)=F(4)={b0+b1 |b0,b1 {0,1}} ={0,1, , 1+} 所以<{0, 1, , 1+}, + mod 2,  mod 2>是域.

26 举例:阶为22的有限域 GF(4)=<{0, 1, , 1+}, + mod 2,  mod 2>是域.
其中为方程x2+x+1 =0的根 加法表： 乘法表：  1+ 1  1+  1+ 1  1+  1+   1+ 1+  1 1  1+  1+ 1 1+  1  1+ 1  1

27 举例:阶为33的有限域 GF(3)=Z3={0,1,2},令为x3+2x+1=0的根,令
F={a + b  + c 2 : a,b,cZ3} <F, + mod 3,  mod 3>是27阶有限域. 例: (1+ 22) =  + 23=  + 2 + 4 = 1. (2 +  + 22)(1 + 2)=1.

28 利用有限域构造MOLS举例 回顾 Ak=(aij(k))n×n, aij(k)=k·i+j mod p,
设有n阶有限域< F={0, b1, … , bn-1} , +, >, 则Ak=(aij(k))n×n, k=1,…,n-1, aij(k)=bkbi+bj , 其中b0=0, i, j[0,n-1] A1= A2= A3=

29 作业 第一章P13：2, 4，30, 36. 第十章P387：17, 46. 编程题:nim和nim2 每章都交作业