江苏省高中数学 奥赛辅导 抽屉原理.doc

江苏省金湖县实验中学高中数学奥赛辅导抽屉原理把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个或两个以上的苹果。抽屉原则有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。形式一: 证明: 设把 n+1 个元素分为 n 个集合 A 1,A 2,…,A n,用a 1,a 2,…,a n 表示这 n 个集合里相应的元素个数,需要证明至少存在某个 a i 大于或等于 2 (用反证法) 假设结论不成立, 即对每一个 a i 都有 a i<2, 则因为 a i 是整数, 应有 a i≤1, 于是有: a 1+a 2+…+a n≤1+1+…+1=n<n+1 这与题设矛盾。所以,至少有一个 a i≥2 ,即必有一个集合中含有两个或两个以上的元素。形式二: 设把 n·m+1 个元素分为 n 个集合 A 1,A 2,…,A n ,用 a 1,a 2,…,a n 表示这 n 个集合里相应的元素个数,需要证明至少存在某个 a i 大于或等于 m+1。(用反证法)假设结论不成立,即对每一个 a i 都有 a i<m+1 ,则因为 a i 是整数,应有 a i ≤m ,于是有: a 1+a 2+…+a n≤m+m+…+m=n·mn个m <n·m+1 这与题设相矛盾。所以,至少有存在一个 a i≥m+1 高斯函数: 对任意的实数 x, [x] 表示“不大于 x 的最大整数”. 例如: [] =3, [] =2, [-2 .5] =- 3, [7] =7, ……一般地,我们有: [x] ≤x< [x] +1 形式三: 证明:设把 n 个元素分为 k 个集合 A 1,A 2,…,A k ,用 a 1,a 2,…,a k 表示这 k 个集合里相应的元素个数,需要证明至少存在某个 a i 大于或等于[n/k] 。(用反证法)假设结论不成立,即对每一个 a i 都有 a i< [n/k] ,于是有: a 1+a 2+…+a k< [n/k]+[n/k]+ …+[n/k] k个[n/k] =k· [n/k] ≤k· (n/k) =n∴a 1+a 2+…+a k<n 这与题设相矛盾。所以,必有一个集合中元素个数大于或等于[n/k] 形式四: 证明: 设把 q 1+q 2+…+q n-n+1 个元素分为 n 个集合 A 1,A 2,…,A n,用a 1,a 2,…,a n 表示这 n 个集合里相应的元素个数,需要证明至少存在某个 i ,使得 a i 大于或等于 q i。(用反证法)假设结论不成立,即对每一个 a i 都有 a i<q i ,因为 a i 为整数,应有 a i≤q i -1 ,于是有: a 1+a 2+…+a n≤q 1+q 2+…+q n-n <q 1+q 2+…+q n-n+1 这与题设矛盾。所以,假设不成立,故必有一个 i, 在第 i 个集合中元素个数 a i≥q i 形式五: 证明:( 用反证法) 将无穷多个元素分为有限个集合, 假设这有限个集合中的元素的个数都是有限个,则有限个有限数相加,所得的数必是有限数,这就与题设产生矛盾,所以,假设不成立,故必有一个集合含有无穷多个元素。例题1: 400 人中至少有两个人的生