1

"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.

Amir Ghafghazi
  • 51
  • 4

2 Answers2

1

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 ?$

The Demonix _ Hermit
  • 3,478
  • 1
    Thank you. So we have 3 holes or possibilities for a number: 3k, 3k+1 and 3k+2. We have 4 numbers, by the pigeonhole principle, there must be one hole which has atleast two elements. So we can always construct a difference between two numbers which are of the same type. If for example two are selected of type 3k. Then their difference will always be divisible by 3. Let there be a1= 3k and a2= 3(k+x). If we subtract a2 from a1 from simple algebra. 3k+3k-3x = 3x. By definition any multiple of 3x where x != 0, implies that it is divisible by 3. Same is true for 2 numbers of (3k+1) or (3k+2) – Amir Ghafghazi Dec 29 '19 at 15:05
  • @AmirGhafgazi Absolutely correct . – The Demonix _ Hermit Dec 29 '19 at 15:34
-2

There are 3 possible remainders when we divide a num by 3.thus by pigeon hole principal we have 4 num.two of them must have same remainder when we divisible by 3.so we can write these n1 And n2 as

$N1=3q1+r,$
$N2=3q2+r,$
$N1-N2=3q1+r-3q2-r =3(q1-q2)$
Which is divisible by 3

amWhy
  • 209,954
karthiklic 1275691
  • 1