狄利克雷原則

簡介

狄利克雷原則即抽屜有時也被稱為鴿巢原理，它是德國數學家狄利克雷首先明確的提出來並用以證明一些數論中的問題，因此，也稱為狄利克雷原則。它是組合數學中一個重要的原理。把它推廣到一般情形有以下幾種表現形式。

形式一：

證明：設把n+1個元素分為n個集合A1，A2，…，An，用a1，a2，…，an表示這n個集合里相應的元素個數，需要證明至少存在某個ai大於或等於2

（用反證法）假設結論不成立，即對每一個ai都有ai<2，則因為ai是整數，應有ai≤1，於是有：

a1+a2+…+an≤1+1+…+1=n<n+1

這與題設矛盾。

所以，至少有一個ai≥2，即必有一個集合中含有兩個或兩個以上的元素。

形式二：

設把n·m+1個元素分為n個集合A1，A2，…，An，用a1，a2，…，an表示這n個集合里相應的元素個數，需要證明至少存在某個ai大於或等於m+1。

（用反證法）假設結論不成立，即對每一個ai都有ai<m+1，則因為ai是整數，應有ai≤m，於是有：

a1+a2+…+an≤m+m+…+m=n·m

n個m

<n·m+1

這與題設相矛盾。

所以，至少有存在一個ai≥m+1

高斯函式：

對任意的實數x,

[x]表示“不大於x的最大整數”.

例如：[3.5]=3，[2.9]=2，

[－2.5]=－3，[7]=7，……

一般地，我們有：[x]≤x<[x]+1

形式三：

證明：設把n個元素分為k個集合A1，A2，…，Ak，用a1，a2，…，ak表示這k個集合里相應的元素個數，需要證明至少存在某個ai大於或等於[n/k]。

（用反證法）假設結論不成立，即對每一個ai都有ai<[n/k]，於是有：

a1+a2+…+ak<[n/k]+[n/k]+…+[n/k]

k個[n/k]

=k·[n/k]≤k·(n/k)=n

∴ a1+a2+…+ak<n

這與題設相矛盾。

所以，必有一個集合中元素個數大於或等於[n/k]

形式四：

證明：設把q1+q2+…+qn－n+1個元素分為n個集合A1，A2，…，An，用a1，a2，…，an表示這n個集合里相應的元素個數，需要證明至少存在某個i，使得ai大於或等於qi。

（用反證法）假設結論不成立，即對每一個ai都有ai<qi，因為ai為整數，應有ai≤qi－1，於是有：

a1+a2+…+an≤q1+q2+…+qn－n

<q1+q2+…+qn－n+1

這與題設矛盾。

所以，假設不成立，故必有一個i,在第i個集合中元素個數ai≥qi

形式五：