组合数学题目及答案.doc

组合数学
例1: 将8个“车”放在8×8的国际象棋棋盘上,如果它们两两均不能互吃,那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态?
解:8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。
用一个排列a1,a2,…,a8 ,对应于一个安全状态,使ai表示第i行的ai列上放置一个“车”。这种对应显然是一对一的。因此,安全状态的总数等于这8个数的全排列总数8!=40320。
例4:n 位客人在晚会上每人与他人握手d次,d 是奇数。证明n 偶数。
证:由于每一次握手均使握手的两人各增加一次与他人握手的次数,因此n位客人与他人握手次数的总和 nd 是偶数—握手次数的2倍。根据奇偶性质,已知d是奇数,那么n必定是偶数。
例4 从1到2n的正整数中任取n+1个,则这n+1个数中,至少有一对数,其中一个是另一个的倍数。
证设n+1个数是a1, a2, ···, an+1。每个数去掉一切2的因子,直至剩下一个奇数为止。组成序列r1, r2,, ···, rn+1。这n+1个数仍在[1 , 2n]中,且都是奇数。而[1, 2n]中只有n个奇数,故必有ri=rj= r, 则ai= 2αi r, aj= 2αj r。若ai>aj,则ai是aj 的倍数。
例5 设a1, a2, ···, am是正整数,则至少存在一对k和l, 0≤k<l≤m,使得和ak+1+ ak+2+ ···+ al是m的倍数。
证设Sh= , Sh≡rh mod m, 0≤rh≤m-1,
h= 1 , 2 , ···, m. 若存在l, Sl≡0 mod ,1≤rh≤m-= 1 , 2 , ···,
鸽巢原理,故存在rk= rl, 即Sk≡Sl mod m,不妨设l>
Sl-Sk= ak+1+ ak+2+…+ al≡0 mod m
例6 设a1, a2, a3是任意三个整数,b1 b2 b3为a1, a2, a3的任一排列,则a1-b1, a2-b2 ,a3-b3中至少有一个是偶数.
证由鸽巢原理:a1, a2, ,不妨设为x; 同样b1, b2, -b1, a2-b2 , a3-b3被2除的余数至少有一个为0.
例7 设a1, a2,…, a100是由数字1和2组成的序列,
ai+ ai+1+…+ ai+9≤16,1≤i≤91。
则存在h 和k ,k > h,使得
ah+1+…+ ak= 39
证令Sj= ,j =1 , 2 , …,100。显然
S1<S2<…<S100,且S100= (a1+ …+a10)+ (a11+ …+a20)+…+ (a91+ …+a100)
根据假定有S100≤10×16 = 160
作序列S1, S2, …, S100, S1+39, …, S100+39.
+39≤160+39
由鸽巢原理,

Sk= Sh+ 39,k>h Þ Sk-Sh=39 即
ah+1+ ah+2+…+ ak= 39
例:1) 求小