自然且平凡——抽屜原理

作者：由 Virgooooo 發表于體育時間：2022-04-29

咳咳，好久不見，我又雙叒叕來說些廢話了：筆者高二，近期學習了抽屜原理，深覺其構造之巧妙、自然，故筆者趁五一小長假，結合小藍本和培訓材料對其進行整理與講解。

這一方法最先是由19世紀的德國數學家Dirichlet應用於解決存在性問題，後來人們為了紀念他從這麼平凡的事情中發現規律，故又稱其為Dirichlet原理

［1］

。

如有錯誤，歡迎指正。接下來步入正文。

一、常見形式

1、

第一抽屜原理：如果將 #FormatImgID_1# 個物件放入

個抽屜內，那麼必有一個抽屜內至少有 #FormatImgID_3# 個物件。

證明：用反證法，如果每個抽屜內至多有

$\left[ \frac{m-1}{n} \right]$

個物件，那麼

個抽屜內的物件總數至多為

$n\left[ \frac{m-1}{n} \right]\leq n(\frac{m-1}{n})=m-1\ne m$

，矛盾，故必有一個抽屜內至少有

$\left[ \frac{m-1}{n} \right]+1$

個物件，證畢。

推廣1：如果將 #FormatImgID_8# 個物件放入 #FormatImgID_9# 個抽屜內，那麼存在第 #FormatImgID_10# 個抽屜內至少有 #FormatImgID_11# 個物件。

結論平凡，證略。

第二抽屜原理：如果將 #FormatImgID_12# 個物件放入 #FormatImgID_13# 個抽屜內，那麼必有一個抽屜內至多有 #FormatImgID_14# 個物件。

結論平凡，證略。

推廣2：如果將

$\sum_{i=1}^{n}{m_{i}-1}\ (m_{i}\in Z^{+},i=1,2,……,n)$

個物件放入

個抽屜內，那麼存在第

個抽屜內至多有

$m_{i}-1$

個物件。

結論平凡，證略。

二、簡單應用

1、設空間6個點中任意4點不共面，現將其中任意兩點間的連線染成紅色或藍色之一。求證：此時必存在一個三邊顏色相同的三角形。

此題正是Ramsey定理的通俗表達，其圖論表達為“2色完全圖

$K_{6}$

中必存在同色三角形”，證明不難，我們直接開始。

證明

：由題意知，從一已知點

出發的5條連線被染成紅或藍，由抽屜原理知其中必有

$\left[ \frac{5-1}{2} \right]+1=3$

條連線同色，不妨設

均為紅色。現考慮

$\triangle BCD$

，若它含有至少一條紅邊，則至少存在一個紅色三角形，否則它自身為藍色三角形，證畢。

我們可以從此出發尋找一系列數

$R_{m}$

，一般地，使

色完全圖

$K_{n}$

中存在同色三角形的最小正整數

叫做Ramsey數，現已找出

$R_{2}=6,R_{3}=17,R_{4}=65…$

［2］

2、求證：任一四面體

中，一定可以找到一個頂點，使過該頂點的三條稜可以構成三角形。

顯然，這是一個存在性命題，故考慮應用抽屜原理的思想。

證明

：不妨設

是該四面體中的最長邊，則有

，

，即

，則

和

中至少有一個成立，否則與上述矛盾。不妨設

，由於

是最長邊，故

可構成三角形，證畢。

我們來回顧一下這道題，不難發現，本題關鍵是從三角形最基本的邊長關係和已知條件出發，巧妙地進行“不妨設”起了很大的作用。

在做接下來這題前，我們先接觸一個概念——劃分。

設

$A_{i}$

是集合

的子集，當滿足

$\bigcup_{i=1}^{n}A_{i}=A$

且

$\forall k\ne j,A_{k}\cap A_{j}=\phi$

時，我們稱

$U=\left\{ A_{1},A_{2}…A_{n} \right\}$

是集合

的一個劃分

［3］

。

我們來看第3題。

3、

$z_{1},z_{2},…z_{n}\in C,S=\left\{ 1,2,…,n \right\}$

，求證：

$\exists T\in S$

，使得

$\left| \sum_{z_{k}\in T}^{}{z_{k}} \right|\geq\frac{1}{6}\sum_{k=1}^{n}{z_{k}}$

此題乍一看，十分茫然，不知從何下手，也不知為何會突然冒出

$\frac{1}{6}$

這一數字，但是這題我們只需要證明其存在性，也就是說我們可以任意挑選出自己想要的

$z_{k}$

去構成

，使它們能夠滿足命題。注意到，

$z_{k}$

的疊加具有方向性，所以我們要找的

$z_{k}$

應儘可能分佈在兩條相互垂直的直線的某個直角範圍內（如圖），減少抵消，抱著這種想法，我們來試一試。

圖片簡陋，見諒

證明：設

$z_{k}=x_{k}+iy_{k}$

，接下來考慮一個劃分，其標準為

$\left| x_{k} \right|$

與

$\left| y_{k} \right|$

間的大小關係，如下

$\sum_{k=1}^{n}{\left| z_{k} \right|}=\sum_{\left| x_{k} \right|\geq\left| y_{k} \right|}^{}{\left| z_{k} \right|}+\sum_{\left| x_{k} \right|<\left| y_{k} \right|}^{}{\left| z_{k} \right|}$

，顯然其中至少一部分大於等於

$\frac{1}{2}\sum_{k=1}^{n}{\left| z_{k} \right|}$

，不妨設

$\sum_{\left| x_{k} \right|\geq\left| y_{k} \right|}^{}{\left| z_{k} \right|}\geq\frac{1}{2}\sum_{k=1}^{n}{\left| z_{k} \right|}$

；再考慮一個劃分

$\sum_{\left| x_{k} \right|\geq\left| y_{k} \right|}^{}{\left| z_{k} \right|}=\sum_{\left| x_{k} \right|\geq\left| y_{k} \right|,x_{k}\geq0}^{}{\left| z_{k} \right|}+\sum_{\left| x_{k} \right|\geq\left| y_{k} \right|,x_{k}<0}^{}{\left| z_{k} \right|}$

，顯然其中也有至少一部分大於等於

$\frac{1}{2}\sum_{\left| x_{k} \right|\geq\left| y_{k} \right|}^{}{\left| z_{k} \right|}$

，不妨設

$\sum_{\left| x_{k} \right|\geq\left| y_{k} \right|,x_{k}\geq0}^{}{\left| z_{k} \right|}\geq\frac{1}{4}\sum_{k=1}^{n}{\left| z_{k} \right|}$

。以上兩次劃分可以直觀地用下圖表示，很顯然我們做到了最開始的想法——減少抵消。

也就是說我們已經找到了這樣的一個集合

。由於

是題目給定的表示，方便起見，我們構造另一個集合來表示它。

設

$Q=\left\{ k\in \left\{ 1,2,…,n \right\} |\ \left| x_{k} \right|\geq\left| y_{k} \right|,x_{k}\geq 0\right\}$

，故有

$\left| \sum_{k\in Q}^{}{z_{k}} \right|=\sqrt{(\sum_{k\in Q}^{}{x_{k}})^{2}+(\sum_{k\in Q}^{}{y_{k}})^{2}}\geq \left| \sum_{k\in Q}^{}{x_{k}} \right|=\sum_{k\in Q}^{}{\left| x_{k} \right|}\geq\sum_{k\in Q}^{}{\frac{\sqrt{x_{k}^{2}+y_{k}^2}}{\sqrt{2}}}=\frac{1}{\sqrt{2}}\sum_{k\in Q}^{}{\left| z_{k} \right|}\geq\frac{1}{4\sqrt{2}}\sum_{k=1}^{n}{\left| z_{k} \right|}>\frac{1}{6}\sum_{k=1}^{n}{\left| z_{k} \right|}$