一、方法與例題
1.抽屜原理。
例1 設(shè)整數(shù)n≥4,a1,a2,…,an是區(qū)間(0,2n)內(nèi)n個(gè)不同的整數(shù),證明:存在集合{a1,a2,…,an}的一個(gè)子集,它的所有元素之和能被2n整除。
[證明] (1)若n {a1,a2,…,an},則n個(gè)不同的數(shù)屬于n-1個(gè)集合{1,2n-1},{2,2n-2},…,{n-1,n+1}。由抽屜原理知其中必存在兩個(gè)數(shù)ai,aj(i≠j)屬于同一集合,從而ai+aj=2n被2n整除;
(
2)若n∈{a1,a2,…,an},不妨設(shè)a
n=n,從a
1,a
2,…
,an-1(n-1≥
3)中任意取3個(gè)數(shù)a
i, a
j, a
k(a
i,
j< ak),則aj-ai與ak-ai中至少有一個(gè)不被n整除,否則ak-ai=(ak-aj)+(aj-ai)≥2n,這與ak∈(0,2n)矛盾,故a1,a2,…,an-1中必有兩個(gè)數(shù)之差不被n整除;不妨設(shè)a1與a2之差(a2-a1>0)不被n整除,考慮n個(gè)數(shù)a1,a2,a1+a2,a1+a2+a3,…,a1+a2+…+an-1。
ⅰ)若這n個(gè)數(shù)中有一個(gè)被n整除,設(shè)此數(shù)等于kn,若k為偶數(shù),則結(jié)論成立;若k為奇數(shù),則加上an=n知結(jié)論成立。
ⅱ)若這n個(gè)數(shù)中沒有一個(gè)被n整除,則它們除以n的余數(shù)只能取1,2,…,n-1這n-1個(gè)值,由抽屜原理知其中必有兩個(gè)數(shù)除以n的余數(shù)相同,它們之差被n整除,而a2-a1不被n整除,故這個(gè)差必為ai, aj, ak-1中若干個(gè)數(shù)之和,同ⅰ)可知結(jié)論成立。
2.極端原理。