鴿籠原理 - HackMD

--- 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. :::