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

A proof can be as follows:

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)`.