# Pigeonhole Principal and Its Application 鴿籠原理及應用

## 1. Art Gallery Problem

在計算幾何理論 (Computational Geometry) 中，畫廊原理說明現實生活中以安全和成本作為考量，將畫廊平面圖以多邊形呈現，攝影機是邊上的點，計算最少需要擺放幾個攝影機，可以同時間讓能見視角遍及每個角落。

>### Chvátal's art gallery theorem
>
>定義：簡單多邊形有 $n$ 個頂點，則 $\lfloor \frac{n}{3} \rfloor$ 個 360 度攝影機足夠涵蓋多邊形每個地方(每個地方至少有一個攝影機照視)

先以簡單圖形來觀察，假設有一個三角形(三條邊的凸多邊形)，則放置攝影機在任一頂點即可看到每個地方，這是因為任一頂點是兩條邊所組成，而由頂點延伸出去的兩邊會包含整個三角形。

所以接著可以將多邊形問題簡單化，也就是將多邊形切割成多個三角形 (triangulated)，再來使用圖著色問題 (Graph Coloring Problem) 的方法，讓每個三角形都由紅藍綠三色不重複組成。

>picture from Wiki

最後，使用鴿籠原理 (Pigeon Hole Principal)，若 $n$ 隻鴿子放在 $k$ 個鴿籠，則至少一個鴿籠必須不超過 $\frac{n}{k}$ 隻鴿子。在此 $n$ 為多邊形頂點， $k$ 為紅藍綠三色，依據鴿籠原理存在一個顏色出現必須不超過 $\lfloor \frac{n}{3} \rfloor$ 次。故得證。

參考資料：
- [Proofs from THE BOOK by Martin Aigner, Günter M. Ziegler](https://www.amazon.com/Proofs-BOOK-Martin-Aigner/dp/3642008550)
- [Wiki - Art gallery problem](https://en.wikipedia.org/wiki/Art_gallery_problem)
- [Wiki - Graph coloring](https://en.wikipedia.org/wiki/Graph_coloring)
---

## 2. Kolmogorov Complexity - Incompressiblity

演算法資訊理論 (Algorithmic Information Theory) 領域中，柯氏複雜性是用來衡量物件或演算法在最佳規格下的長度，也可以被解釋為演算法熵 (Algorithmic Entropy) 代表一個物件所擁有的訊息量。

舉例來說，下面字串可以用 Haskell 以『重複 16 個 01』表示

01010101010101010101010101010101

// Haskell Language
take 16 $ cycle "01"

而下面字串則無法再用更簡短的表達式去說明

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

所以可以解釋為第二個字串複雜度較高。接著，探討一個字串 $s$ 是否能被壓縮，同樣可以利用鴿籠原理推導，$d(s)$ 是 $s$ 字串的最短詮釋，$K(s)$ 是 $d(s)$ 的長度，若 $s$ 無法被壓縮，則代表 $K(s) ≥ s$。也就是對於所有 $n$ 位元字串，存在不可壓縮的字串 (長度大於等於 $n$)。根據鴿巢原理，有 $2^{n}$ 個長度為 $n$ 位元的字串，但是只存在 $2^{n} - 1$ 個長度小於 $n$ 位元的詮釋後字串，因為

$$\sum_{n=0}^{n-1} 2^{i} = 2^{n} - 1$$

說明每一個壓縮後的字串對應唯一的壓縮前的字串，所以不可壓縮的字串一定存在，且很可能大部分的字串無法被壓縮。

參考資料：
- [Wiki - Kolmogorov complexity](https://en.wikipedia.org/wiki/Kolmogorov_complexity)
- [Wiki - Lossless compression](https://en.wikipedia.org/wiki/Lossless_compression#Limitations)
- [一杯咖啡的「表觀複雜性」](https://www.gvm.com.tw/article/40880)
---

## 3. Erdős Szekeres Theorem

鴿籠原理也可以來證明此定理

>### Erdős Szekeres theorem
>定義：由不同數字組成 $n^2 + 1$ 長度的串列，則一定有一段遞增或遞減子串列，長度為 $n + 1$

首先，假設串列中每個元素為 $a_i$，其中 $1 \le i \le n^2 + 1$，$u(i)$ 代表最長遞增子字串結束在 $a_i$ 的長度，$d(i)$ 代表最長遞減子字串結束在 $a_i$ 的長度。若反假設子字串長度不到 $n + 1$ 則 $1 \le u(i) \le n$ 和 $1 \le d(i) \le n$，那 $(u(i), d(i))$ 會有 $n^2$ 種不同數字排序組合。因此根據鴿籠原理，在 $n^2 + 1$ 個元素裡面會有兩個相同，$i < j$ ， $a_i = a_j$ 即 $u(i)=u(j)$ 和 $d(i)=d(j)$，可是發現由於串列一定是不同的數字組成，所以經由反證得 $u(j) = u(i) + 1$ 或 $d(j) = d(i) + 1$。確認能找到一段長度為 $n + 1$ 的遞增或遞減的子串列。

參考資料：
- [Wiki - Erdős–Szekeres theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem)
- [EECS at UC Berkeley - Pigeonhole principle](https://people.eecs.berkeley.edu/~oholtz/191/pigeonhole.pdf)
- [CS at Purdue - Pigeonhole principle](https://www.cs.purdue.edu/homes/hmaji/teaching/Spring%202016/lectures/01.pdf)
---

## 4. Chinese Remainder Theorem

數論 (Number Theory) 中，著名的中國剩餘定理提供必要條件，使多重等式有共同正整數解，可參考

>### Chinese Remainder Theorem
>定義：若 $m$ 和 $n$ 為互值的正整數，則存在 $x$ 使得 $x=a(mod \space m)$ 和 $x=b(mod \space n)$

首先考慮 $n$ 個正整數 $a, m + a, 2m + a, \ldots,(n-1)m + a$ 除以 $m$ 的餘數都是 $a$，假設其中兩數 $im + a,$ $jm + a$ $(0 ≤ i < j ≤ n - 1)$ 除以 $n$ 有相同餘數 $r$，則有兩個整數 $p, q$ 使得 $im + a = pn + r$ 和 $jm + a = qn + r$，相減得 $(j - i) m = (p - q) n$ 且 $\gcd(m, n) = 1$，故得 $n$ 是 $j - i$ 的因子。然而 $0 ≤ j - i ≤ n - 1$ 有矛盾，所以假設不成立。
即上述 $n$ 個整數除以 $n$ 都有不同的餘數，依據鴿籠原理 $0, 1, 2, \ldots , (n-1)$ 都會出現，且 $0 ≤ b ≤ n - 1$ ，所以 $b$ 會是餘數。使 $k$ 為整數，$0 ≤ k ≤ n - 1$，$km + a$ 除以 $n$ 的餘數是 $b$，則有 $f$ 使以下成立：

$$x = km + a = fn + b$$

有此 $x$ 除以 $m$ 餘 $a$，除以 $n$ 餘 $b$。

參考資料：
- [Wiki - Chinese remainder theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem)
- [Cut the knot - Chinese Remainder Theorem](https://www.cut-the-knot.org/blue/chinese.shtml)
---

## 5. Birthday problem

參考生日問題的計算公式：

$$1-\frac{365×364×⋯×(366−n)}{365^n} = 1 - \frac{365!}{(365-n)!365^n}$$

會發現在不超過 $365$ 人的情況下，兩人生日為相同的機率違反直覺地高，如 $23$ 人則機率超過 $50\%$，而 $70$ 人機率就高達 $99\%$，此現象稱作生日悖論 (birthday paradox)。另透過鴿籠原理，可以很直觀的知道若人數超過 $365$ 人，則其中兩人生日相同的機率為 $100\%$。

在密碼學 (Cryptography) 中利用雜揍程式 (hash function) 處理訊息，攻擊者可以透過碰撞 (collision) 獲取訊息，生日攻擊 (birthday attack) 就是在計算雜湊程式的防碰撞能力。

$$p_M(n) = 1 - \frac{M!}{(M - n)!M^n}$$

攻擊者在碰撞機率超過 $p_M(n) = 0.5$ 之前需要計算多少數值，雜湊範圍在 $32$ 位元時 $(M = 2^{32})$ 約 $4 \times 10^9$，而 $64$ 位元時約 $10^{19}$。實際應用上，更大的雜湊範圍可降低弱點。

參考資料：
- [Wiki - Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem)
- [Wiki - Cryptography](https://en.wikipedia.org/wiki/Cryptography)
---