Skip to content

5.12 Pigeonhole principle

Problem

  1. There is a group of 1000 students. Prove that there is at least 3 of them who have birthdays on the same day of the year

    Solution

    Let \(A=\{\text{set of students}\}\) where \(\#A=1000\) and \(B=\{\text{set of days in a year}\}\) where \(\#B=366\)

    And \(f:\text{student}\to \text{birthday}\), since \(1000=2\cdot 366+268\), then at least 3 of them have same birthdays by Let A_{1},...,A_{r} be finite sets #(A_{1}\cup...\cup A_{r})>kr, then there is i\in{1,...,r...

  2. Let \(q\) be an odd integer. Prove that \(\exists i\in \N\) such that \(2^{i}-1\) is divisible by \(q\)​

    Solution

    Consider \(i=\{1,...,q\}\) and the sequence \(1,3,7,...,2^q-1\) with size \(q\)

    NTP: some numbers in the sequence is divisible by \(q\)

    Suppose that no element of this sequence is divisible by \(q\)

    Let \(A=\{1,...,q\}\) and \(B=\{0,...,q-1\}\) is possible remainder modulo \(q\)

    Let \(f:A\to B\) where \(i\mapsto (2^i-1)\%q\)

    Since our hypothesis, we can remove \(0\in B\). Then \(|A|=q\) and \(|B|=q-1\)

    Then by pigeonhole principle, there exists at least two number in \(A\) have the same remainder modulo \(q\)

    Then \((2^j-1)\%q=r=(2^i-1)\%q\), then \(2^j-2^i\) is divisible by \(q\)

    Assume \(j> i\), then \(2^{i}(2^{j-i}-1)\) is divisible by \(q\). Since \(q\) is odd, then \(2^{j-1}-1\) is divisible by \(q\)

    Contradiction

Dirichlet's approximation theorem

We say that an approximation of an irrational number \(\alpha\) by a rational number \(\frac{p}{q}\) is good if \(|\alpha -\frac{p}{q}|<\frac{1}{q^2}\)

Theorem

For any irrational number \(\alpha\) we have infinite numbers of good approximations

Proof

Pick a natural number \(N\), for \(k=1,...,N+1\) we write \(k\alpha = m_k+x_k\) where \(m_{k}=\lfloor k\alpha \rfloor\) and \(x_{k}=\{k\alpha\}=k\alpha-\lfloor k\alpha \rfloor\in (0,1)\)

We have \(N+1\) \(x_k\) and \(N\) intervals

image​

Suppose \(x_i<x_j\), we know \(|\underbrace{(j\alpha -m_{j})}_{=x_j}-\underbrace{(i\alpha -m_{i})}_{=x_i}|<\frac{1}{N}\)

Then \(|(j-i)\alpha -(m_{j}-m_{i})|<\frac{1}{N}\Rightarrow \left|\alpha-\frac{m_{j}-m_{i}}{j-i} \right|<\frac{1}{N|j-i|}\leq \frac{1}{(j-i)^2}\) since \(|j-i|\leq N\)

Then let \(m_j-m_i=p,j-i=q\), we reach the result

Suppose that there is a finite set of \(q\)'s that provide a good approximation for \(\alpha\)

Let \(\left\{\frac{p_{i}}{q_{i}}\right\}_{i=1}^k\) be the set of all good approximation. Consider \(\delta=\min\left|\alpha-\frac{p_{i}}{q_{i}}\right|>0\)​

Take \(N>\frac{1}{\delta}\), establish that there exists some \(r,s\in \Z\) s.t. \(|r\alpha -s|<\frac{1}{N}<\delta\)

Notice \(\frac{s}{r}\) is also a good approximation since \(|\alpha-\frac{s}{r}|<\frac{\delta}{\left|r\right|}<\delta\)​

Ramsey Theorem

If the size of a graph is big enough, some structures are unavoidable

Reminder

  • Any graph on \(6\) vertices either has a 3-clique or a 3-anticlique
  • There is a graph on \(5\)​ vertices such that has neither a 3-clique or a 3-anticlique
  • Any graph with \(N\geq 6\) vertices also either has a 3-clique or a 3-anticlique

Choose a random induced subgraph on \(6\) vertices

Theorem(Ramsey)

Let \(p,q\in \N\). Then there exists a certain \(N_{(p,q)}\in \N\) such that any graph on \(N_{(p,q)}\) vertices either a p-clique or a q-anticlique

Remarks
  • If the theorem holds for \(N\) it also holds for \(N+k,(k\geq 1)\)

We denote \(R(p,q)=\min\{N\text{ : the statement of the theorem hold}\}\)

Example: \(R(3,3)=6\) * \(R(p,q)=R(q,p),\forall p,q\in \N\) sinceimage​ * \(R(p,1)=1\), \(\forall p\in \N\)​ * \(R(p,2)=p\), \(\forall p\in \N\)

Important

We are going to show that \(\forall p,q\geq 2\), we have \(R(p,q)\leq R(p-1,q)+R(p,q-1)\)

Proof

Set \(N=R(p-1,q)+R(p,q-1)\). Consider a graph that has \(N\) vertices

Fix one of the vertices of the graph and notice by generalized pigeonhole principle, either this vertex is incident to at least \(R(p-1,q)\) edges, or there are at least \(R(p,q-1)\) other vertices not adjacent to it

image​

Suppose that there are at least \(R(p-1,q)\) other vertices adjacent to the chosen one

In the subgraph induced by adjacent vertices either there is a p-1 clique or a q anticlique

So either there is a p-clique (added chosen one) or a q-anticlique in the original graph

The symmetric case is considered in a similar way

Using induction and the fact that \(R(p,2)=\binom{p}{1}\) we can prove the estimation \(R(p,q)\leq \binom{p+q-2}{p-1},\forall p,q\geq 2\)

Table of known Ramsey numbers

q\p 1 2 3 4 5 6 7 8 9 ...
1 1 1 1 1 1 1 1 1 1 ...
2 2 3 4 5 6 7 8 9 ...
3 6 9 14 18 23 28 36 ...
4 18 25 36-40
5 43-46 (at 43, \(2^{\binom{43}{2}}\) graphs) 55-85
6 102-160

\((1+o(1))\frac{p}{\sqrt{2e}}\cdot2^{\frac{p}{2}}\leq R(p,p)\leq(1+o(1))\frac{{4}^{p-1}}{\sqrt{\pi p}}\)

Then \(101\leq R(10,10)\leq 48620\)​

‍