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
