---
# System prepended metadata

title: 鴿籠原理
tags: [數讀]

---

---
tags: 數讀
---
# 鴿籠原理
> [name=W_Ice_Tri] [time=Sun, March 7, 2021] [color=#1f1e33]

[TOC]
## 0. 什麼是鴿籠
鴿籠原理(Pigeon Hole Principle)，又稱抽屜原理，簡稱PHP。PHP其實很好上手，綜合了C,Java等語言的特性，也可嵌入HTML中執行，像是購物車就會使用PHP寫。
#### Example0.1
因為疫情影響，台灣每天生產$2020$個一樣的口罩，政府決定將口罩分成若干堆，現在有$2021$個人排隊在搶口罩，而吳尚昱是第$2021$個人，因為人類是貪心的，每個人都會搶走目前剩下的口罩中最多的那堆......現在記者問了吳尚昱一個問題。

(1). 請問你有拿到口罩嗎？

但是因為吳尚昱詞窮，所以請幫他回答這一個問題。

---
做完這個例題後應該會對鴿籠原理更加的了解，那我們就來看看什麼是鴿籠原理吧
## 1. 正常的鴿籠
### Theorem1.1 (PHP)
:::info
如果有$n$個咖波被放在$m$個抽屜，存在一個抽屜被放至少$\lceil\dfrac{n}{m}\rceil$個咖波，也存在一個抽屜被放至多$\lfloor\dfrac{n}{m}\rfloor$個咖波。
:::
#### Example1.1
在1812序曲中，若樂團只有$4$個加農砲，且在曲子中總共要發$9$次，必存在一個加農砲發射至少$3$次。
#### Problem1.1
$13$人中，存在兩人有相同生肖，且存在兩人有相同星座。
#### Example1.2
一個派對中有$n$個人，他們之中有些人兩兩之間互相認識。試證明存在兩個人，他們兩個認識的人數相同。
#### Example1.3
現在有$n>3$個整數$a_1,a_2,...,a_n$，試證明可以從中取出一些數滿足這 些數的和為$n$的倍數
#### Example1.4
從$1\thicksim 2n-1$取$n$個數，必存在數個數的和為$2n$的倍數。
#### Problem1.2
$\lceil\dfrac{n+3}{2}\rceil$個相異整數中必存在兩數使得它們的和或差是$n$的倍數。 
#### Problem1.3
平面上任意$2021$條直線必存在$2$線夾角$<0.09^{。}$。
### Theorem1.2 (Erdos-Szekeres)
:::info
在一個由$ab+1$個相異的數組成的序列中，必存在長度$a+1$的遞增子序列或長度$b+1$的遞減子序列。
:::
Hint : DP
#### Example1.5
從$1\thicksim2n+1$取$n+1$個數，必有兩數互質。
#### Problem1.4
從$1\thicksim2n$取$n+1$個數，必有兩數使得其中較大的數是較小的數的倍數。
#### Example1.6
對於任意$n$個正整數$a_1,a_2...a_n$滿足$\displaystyle{\sum_{i=1}^{n}a_i<2^n-1}$，必存在兩個子集合$S\neq T\subseteq\{1,2...n\}$使得$\displaystyle{\sum_{i\in S}a_i=\sum_{i\in T}a_i}$。
#### Example1.7
給定$x\in\mathbb{R}$及$n\in\mathbb{Z}^+$，必存在$q\in\mathbb{Z}^+,q\leq n$及$p\in\mathbb{Z}$，使得$$|x−\dfrac{p}{q}|<\dfrac{1}{qn}$$
#### Problem1.5
試證對於任意$13$個實數必存在兩數$x,y$使得$0<\dfrac{x-y}{1+xy}\le 2-\sqrt{3}$
#### Example1.8
平面上$9$個整點中必存在$3$個點它們的重心(座標平均)也是整點。
#### Problem1.6
平面上$2n^2−2n+1$個整點中必存在$n$個點它們的重心也是整點。

其實有個更緊的界，不過我不會證明(能競可以用)>w<
#### Remark. (Kemnitz)
:::success
平面上$4n-3$個整點中必存在$n$個點它們的重心也是整點。
:::
#### Example1.9
從$1$到$2020$中取出一些數，滿足對於其中任兩個相異的數$a,b$都有$ab$不在其中。試求取出的數個數的最大值。
#### Problem1.7
令$p$為一質數，試證$x^2+y^2+1\equiv 0\pmod{p}$有一組解$(x_0, y_0)$ 其中$0 \leq x_0 \leq \dfrac{p-1}{2}$
且$0 \leq y_0 \leq \dfrac{p-1}{2}$.
#### Example1.10
將$1\sim 2020$排成一圈，試證必存在連續的三個數之和不小於$3031$。
#### Example1.11
將一個$4\times m$的棋盤三染色，必可出現兩行兩列它們的四個交點是同個顏色，試找出$m$的最小值。
#### Problem1.8
$a_i,b_i,c_i\in\mathbb{Z}$，$\forall 1\leq i\leq n$,$a_i,b_i,c_i$中至少有一個是奇數，試證:存在$x,y,z\in\mathbb{Z}$使得$\{xa_i+yb_i+zc_i|1\leq i\leq n\}$中至少有$\dfrac{4n}{7}$個數是奇數。
## 2. 圖論的鴿籠
#### Example2.1
把${1,2, ...,16}$分割成三個集合，必存在兩個相異元素$a,b$在同一集合中使得$b-a$也在那個集合中。

我把其他的內容放到圖論了，就不拿來佔版面了，呵呵
## 3. 幾何的鴿籠
#### Example3.1
若以三個矩形完整覆蓋一三角形的三邊，試證這些矩形蓋滿整個三角形。
#### Problem3.1
將歐式平面上的格子點三圖色(每色都要用)，試證必存在三頂點皆異色的直角三角形。
(04 Russia)
#### Example3.2
邊長$1$的正三角形中任取$n^2 + 1$個點，必存在兩個點相距$\leq\dfrac{1}{n}$。
#### Problem3.2
邊長$1$的正方形中任取$n^2 + 1$個點，必存在兩個點相距$\leq\dfrac{\sqrt{2}}{n}$ 。
#### Example3.3
邊長$1$的正方形中任取$2n + 1$個點，必存在三個點所圍成的面積$\leq\dfrac{1}{2n}$ 。
#### Problem3.3
將平面上每個點$2021$塗色，試證存在兩個相似的$2021$邊形，且它們的相似比為$2021$，且每個$2021$邊形的$2021$個頂點同色。\\
Hint : 8253749601
#### Example3.4
在面積$1$的平面圖形內任意放入$9$個面積為$\dfrac{1}{5}$的小正方形，試證其中必有兩個小正方形他們重疊部分的面積不小於$\dfrac{1}{45}$。
## 4. 難點的鴿籠
#### Example4.1
一個圓被$18$個點等分成$18$個弧，其中有$6$點塗成藍色、$6$點塗成紅色、$6$點塗成黃色，則可以從每個顏色中各選出兩個點連成一線段，使得這三條線段等長。
#### Example4.2
集合$M$包括$1537$個相異正整數，且所有$M$中的元素其最大質因數皆不超過$23$。試證：$M$中必有四個相異元素$a,b,c,d$使得$abcd$相乘為某一正整數的四次方
#### Problem4.1
設$a_0,a_1,...,a_n$是$n+1$個正整數$(n>3)$，滿足：$a_0<a_1<...<a_n\leq 2n-3$，證明：存在不同的正整數$i,j,k,l,m\in \{1,2,...,n\}$使得$a_i+a_j=a_k+a_l=a_m$
#### Problem4.2
$49$ students solve a set of $3$ problems. The score for each problem is a whole number of points from $0$ to $7$. Prove that there exist two students $ A$ and $ B$ such that, for each problem, $ A$ will score at least as many points as $B$.
#### Problem4.3
有兩個周長$420$的圓，第一個圓的圓周上有$420$個相異的點，第二個圓的圓周上有 一些弧被塗成紅色，這些弧的總長小於一。試證存在一種將兩圓圓心重合的方式，使得第一個圓上的每個點都不在第二個圓的紅色弧上。
#### Example4.3
在歐式平面上若有一個凸$4n$邊形面積$>4$且點對稱於$(0,0)$，則此凸集必包含非零格子點。

其實有個更廣義的定理(多看些英文啦)：
### Theorem4.1(Minkowski)
:::info
Let $S$ be a closed convex body in $\mathbb{R}^n$, symmetric with respect to the origin 0 and having volume $vol(S)$. Then every lattice $L$ of determinant $det(L)$ such that $vol(S)>2^n|det(L)|$ contains a non-zero integer point.
:::
:::spoiler Proof.
Let $P$ denote fundamental parallelepiped spanned by the basis of lattice $L$.
Denote $2P\triangleq\{2x:x\in P\}$, and define $f:S\rightarrow2P$ as a "modulo-2P operator".
For every $x\in S,\ f(x)=x+2v\in 2P$ for some lattice vector $v\in L$.
$f$ isn't inj., since $vol(S)>2^n|det(L)|=vol(2P)$ and $f$ is locally area-preserving.
There exist two distint points $p$ and $q$ in $S$ where $f(p)=f(q)$, and There exists a lattice point $w\neq0$ s.t. $q=p+2w$ by the definition of $f$.
$\because -p\in  S$
$\therefore w=\dfrac{q-p}{2}\in S\cap L$ since $S$ is convex.
Q.E.D.
:::
這個定理可以拿來解數論：

### Theorem4.2
:::info
$p$為一質數，則$p\equiv 1\pmod4$若且唯若$p$為二平方數之和。
:::
:::spoiler Proof.
由歐拉判別法可知$x^2\equiv-1\pmod{p}$有解，隨便取一個為$t$
考慮以兩向量$(1,t),(0,p)$合出的格子點$L$\\$\because B=\left[ \begin{array}{cc}1 & t \ 0 & p\end{array} \right]=p$
由Minkowski Thm.可知存在$x=(x_1,x_2)\in\mathbb{Z}^2$ s.t. $0<||Bx||^2_2<2p$
又$||Bx||^2=x_1^2+(tx_1+px_2)^2$，令$a=x_1\in\mathbb{Z},b=tx_1+px_2\in\mathbb{Z}$
可得$a^2+b^2=x_1^2+(tx_1+px_2)^2\equiv 0\pmod{p}\Rightarrow a^2+b^2=p$
Q.E.D.
:::
#### Problem4.4
設$x_1,x_2,...,x_n\in\mathbb{R}$，滿足$\displaystyle{\sum_{i=1}^n x^2_i=1}$，求證：對於每個整數$k\geq2$，存在不全為零的整數$a_1,a_2,...,a_n$使得$|a|\leq k−1(i=1,2,...,n)$且$\displaystyle{|\sum^n_{i=1} a_ix_i|\leq \frac{(k−1)\sqrt{n}}{k^n-1}}$。
#### Problem4.5
在$100\times 100$的棋盤上，每個$1\times1$的格子塗上有朋的大紅色、士朋的粉紅色、帽T的暗紅色、夕陽的橘紅色四種顏色之一，使得每行與每列每種顏色都恰25個，試證明可以找到兩行兩列，它們的4個交點是4個不同的顏色。
#### Problem4.6
$a_i\in\mathbb{R}$，在$a_1,\dfrac{a_1+a_2}{2},\dfrac{a_1+a_2+a_3}{3},...,\dfrac{a_1+a_2+...+a_{2020}}{2020}$中至少有$1011$個數相等，試證:$a_1,a_2,...,a_{2020}$中有兩個數相等。
#### Problem4.7
邊長為$n$的正六邊形，可分割成$6n^2$個邊長為$1$的正三角形，在全部$3n^2+3n+1$個交點處寫上相異的正整數，試問最多有多少個邊長為$1$的正三角形，它們頂點上的三個數是按照順時針方向增加的？
#### Problem4.8
Let $a_1,a_2,...,a_9$ be nine real numbers, not necessarily distinct, with average $m$. Let $A$ denote the number of triples $1 \le i < j < k \le 9$ for which $a_i + a_j + a_k \ge 3m$. What is the minimum possible value of $A$?
(14 ELMO C3)
#### Problem4.9
Let $n \ge 2$ be an integer. Consider an $n \times n$ chessboard consisting of $n^2$ unit squares. A configuration of $n$ rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that, for each peaceful configuration of $n$ rooks, there is a $k \times k$ square which does not contain a rook on any of its $k^2$ unit squares.
(14 P2)
#### Remark.
以下的$p$皆為質數
### Definition (A+B)
:::warning
$A+B:=\{a+b|a\in A,b\in B\}$
:::
### Definition (Zp)
:::warning
$\mathbb{Z}/p\mathbb{Z}=\{0,1,...,p−1\}$
:::
### Lemma4.1 (polynomial)
:::success
若多項式$f(x, y)$的最高次項是$cx^ay^b$，集合$A, B$滿足$|A|\geq a+1,|B|\geq b+1$，則存在$(x,y)\in A\times B$，使得$f(x, y)\neq0$。
:::
### Theorem4.3 (Cauchy-Davenport)
:::info
$A,B \subset\mathbb{Z}/p\mathbb{Z}$,$A,B\neq\{\phi\}$，則$$|A+B|\geq\min\{p,|A|+|B|−1\}$$
:::
:::spoiler Proof.
如果$|A|+|B|>p$，則$\forall c\in\mathbb{Z}/p\mathbb{Z}, |A|+|c−B|>p\Rightarrow A\cap(c−B)\neq\phi$
所以存在$(a,b)\in A\times B$ s.t. $a=c−b\Rightarrow a+b=c, \therefore A+B=\mathbb{Z}/p\mathbb{Z}$。
如果$|A| + |B| \leq p$，利用反證法假設$|A + B| \leq |A| + |B| − 2$
設$C \subset \mathbb{Z}/p\mathbb{Z}$滿足$|C| = |A| + |B| − 2$且$A + B \subset C$\\設一個多項式$f(x,y)=\displaystyle{\prod_{c\in C}}(x + y − c)$
顯然$f(a, b) = 0, \forall(a, b) \in A \times B...(1)$
另外，$x^{|A|−1}y^{|B|−1}$項係數是$\displaystyle{\binom{|A|+|B|-2}{|A|-1}}$，在$\mathbb{Z}/p\mathbb{Z}$中不為$0$
因為$|A| + |B| − 2 < p$
根據\bf{Lemma \ref{lemma1}}，存在$(a, b) \in A \times B$使得$f(a, b)\neq 0$，與$(1)$矛盾
所以$|A + B|\geq |A| + |B| − 1$。
Q.E.D.
:::
### Theorem4.4 (2n-1)
:::info
對於任意$2n−1$個整數組成的序列$a_1,a_2, ...,a_{2n−1}$(不一定要全相異)，必存在$A\subset\{1,2,...,2n−1\}$滿足$|A|=n$使得$$\displaystyle{\sum_{i\in A}a_i\equiv 0\pmod n}$$
:::
:::spoiler Proof.
首先證明對於任意的$n = p \in\mathbb{ P}$，這個定理成立
WLOG設$a_1 \leq a_2 \leq\dots\leq a_{2p−1}$。如果存在$i$使得$a_i = a_{i+p−1}$
那麼$a_i = a_{i+1} = \dots = a_{i+p−1} \Rightarrow\displaystyle{\sum^{i+p−1}_{k=i}} a_k = pa_i \equiv 0\pmod{p}$，成立。
如果不存在$i$使得$a_i = a_{i+p−1}$，定義集合$A_i = \{a_i, a_{i+p−1}\}$
根據**Theorem4.3**，$|A_1 +A_2 +...+A_{p−1}|\geq |A_1|+|A_2|+...+|A_{p−1}|−(p-2)=p$
所以$\forall j\in \mathbb{Z}/p\mathbb{Z}$，都可以寫成$p − 1$個$A_i$中的元素的和
令$j = −a_{2p−1}$，這個定理成立。
接著使用數學歸納法，設對於正整數$l, m$這個定理成立。
令互不相交的集合$A_1,A_2,\dots,A_{2m−1} \subset\{1,2,\dots,2lm−1\}$使得$|A_i|=l$且$\displaystyle{\sum_{j\in A_i} a_j \equiv0\pmod{l}}$
因為根據假設任意$2l− 1$個數都可以找到$l$個數相加被$l$整除，而這些集合取完時還剩$l − 1$個數，也就是取最後一個集合時有$2l − 1$個數，因此這種取法必定可行。 
設$a^\prime_i = \displaystyle{\sum_{j\in A_i}\frac{a_i}{p}}$，根據假設$\{a^\prime_1, a^\prime_2,\dots,a^\prime_{2m−1}\}$可以找到$m$個數相加被$m$整除
取這$m$個集合中共$lm$個元素，即對於$lm$這個定理亦成立
當$n = 1$時，定理顯然成立，而$\forall n\geq2\in {Z}$都是多個質數相乘的結果
所以$\forall n \in\mathbb{Z}^+$，這個定理成立。
:::
#### Problem4.10
Prove that any complete graph with $1000p$ vertices, whose edges are labelled with integers, has a cycle whose sum of labels is divisible by $p$.
(13 TSTST)
## Remark.
Interesting fact about $2021$:
:::danger
$2021=\displaystyle{\sum_{i=2}^{25}(p_i+p_{i-1})}$, $p_i=i^{th}$ prime number.
:::