1 组合数学 例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必定是偶数
例４ 从 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
