"Use the Pigeonhole Principle to show that among any four numbers one can find two numbers so that their difference is divisible by $3$."
I am struggling with this supposedly basic question on one of our past paper as its only worth $3$ marks.
[Math] Pigeonhole principle to prove that given $4$ numbers the difference between two numbers is divisble by $3$
pigeonhole-principle
Best Answer
Hint : A number can be of the form $3k , 3k+1$ or $3k+2$. Since there are $4$ numbers , at least two of them leave the same remainder when divided by $3.$
What remainder would their difference leave when divided by $3 ?$