Question

Pigeon Hole Principle :

Prove that given any set of n + 1 integers, there must be at least one pair among them whose difference is divisible by n

Answer 1

Answer:

A proof can be as follows:

Step-by-step explanation:

Let $S=\{a_{1},a_{2},...,a_{n},a_{n+1}\}$ be a set of $n+1$ integers. By the division algorithm the possible remainders when we divide by $n$ are $0,1,2,....,n-1$. Then, each integer $a_{i}\in S$ can be written as:

$a_{i}=np_{i}+r_{i},\,\,0\leq r_{i} <n$

Observe that the set of remainders $\{r_{1},r_{2},...,r_{n+1}\}$ has $n+1$ elements and each element has $n$ possible values. By the Pigenhole principle at least two remainders have the same value. Suppose that this two elements are $a_{i}, a_{j}$. Then,

$\begin{array}{c}a_{i}=np_{i}+r\\a_{j}=np_{j}+r\end{array}$

Where $r_{i}=r_{j}=r$. Then,  $a_{i}-a_{j}=np_{i}-np_{i}=n(p_{i}-p_{j})$. Then we have that $n$ divides $a_{i}-a_{j}$.