# 6 - The Pigeonhole Principle

## The Pigeonhole Principle

Let $k \geq 1$ be an integer. If $k + 1$ ($m$) or more objects are placed into $k$ ($n$) holes, then at least one hole contains at least two (ceil($m/n$))objects.


If $A$ and $B$ are sets and $|A| > |B|$, then there is no one-to-one function $f:A \rightarrow B$


## Simon's Drinking Problem
- Simon drinks at least one beer everyday
- In April, which has 30 days, Simon drank exactly 45 beers
- By the pigeonhole principle we can conclude there is at least 1 day where Simon drank ceil(45/30) beers

**Claim**: There is a sequence of consecutive days in April in which Simon drank exactly 14 beers

**Proof**: For each $i \in \{1,2,...,30\}$ let $a_i$ be the number of beers Simon drank of April $i$

- We know that $a_1 + a_2 + ... + a_{30} = 45$, $a_i \geq 1$ for each $i \in \{1,2,...,30\}$
- Let $b_i = a_1 + a_2 + ... + a_i$, $b_{30} = 45$, $b_{i+1} > b_i$ for each $i \in {1,...,29}$
- Consider $b_1, b_2, ..., b_{30}, b_1 + 14, b_2 + 14, ..., b_{30} + 14$
- Total length of sequence is $m = 60$, $b_{30} + 14 = 59 = n$
- Because with have 60 numbers within a range of 59 possible choices, one number must appear twice
- This number can't appear twice in $b_i$ because we know that $b_i < b_{i+1}$ nor can it appear twice in $b_i + 14$ for the same reason
- One of these two similar numbers comes from the first half and the other comes from the second half, $b_i, b_j + 14$ where $i$ is not necesarilly equal to $j$
- $b_i = b_j + 14$, therefore $b_j < b_i$ and $j < i$

$b_i = a_1 + a_2 + ... + a_j + a_{j+1} + ... +a_i$
$b_j = a_1 + a_2 + ... + a_j$
$b_i - b_j = a_{j+1} + ... + a_i = 14$
Therefore the consecutive days when simon drank exactly 14 beers are $a_{j+1}...a_i$

## Sequence problem
Let $a_1,...a_{n+1}$ be a sequence of integers in $\{1,2,3,...,2n\}$
**Theorem**: Then there exists $i \neq j$ such that $a_i$ divides $a_j$ ($a_i / a_j$ is an integer)

**Proof**: Write each $a_i$ as $a_i=2^{k_i}\times q_i$ where $k_i \geq 0$ is an integer and $q_i$ is an odd integer

Ex: $a_i = 40 = 2\times 20 = 2 \times 2 \times 10 = 2 \times 2 \times 2 \times 2 \times 5 = 2^3 \times 5$
$k_i = 3$
$q_i = 5$

We define a function $f(i) = q_i$
$f:\{1,...,n+1\} \rightarrow \{1,3,5,...,2n-1\}$

By the pigeonhole principle $f(i) // f(j) = 0$ for some $i \neq j$.

This means that $a_i = 2^{k_i} \times q$, $a_j = 2^{k_j}\times q$
- Assume without loss of generality that $k_i \geq k_j$. Then we have $\frac{a_i}{a_j} = \frac{2^{k_i}}{2^{k_j}} = 2^{k_i - k_j}$ is an integer because $k_i \geq k_j$

Ex: $a_i = 40, a_j = 10$
$\frac{40}{10} = \frac{2^3 \times 5}{2^1 \times 5}$

## Erdos-Szekeres Theorem
Every sequence of $n^2+1$ distinct numbers contains an increasing subsequence of length $n + 1$ or a decreasing subsequences of length $n + 1$

*Subsequence*: A subpart of a sequence

Ex: 10 9 5 2 1 6 3 7 4 8
$n=3, 3^2+1=10$

**Proof**: Let $a_1,...,a_{n^2+1}$ be a sequences of distinct numbers.
- For each $i \in \{1,...,n^2+1\}$, let $inc_i$ = the length of the longest increasing subsequence that starts with $a_i$.


- If $inc_i \geq n + 1$ for some $i$, then we're done
- Else, $inc_i \in \{1,...,n\}$. There are $n^2 + 1$ things mapping onto $\{1,...,n\}$
- 
- If we can't find a $inc_i \geq n + 1$ then by the PHP, we can conclude that at least one of $inc_i \in \{1,...,n\}$ appears at least $n+1$ times are we're done
- 

###### tags: `COMP2804` `Combinatorics`