first tier second tier third tier fourth tier

past issues

2004 2003 2002 2001 2000 1999 1998 1997 1996 Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec

Welcome to NRICH.

Pigeon-hole problem

---

---

By Arun Iyer on Friday, December 06, 2002 - 08:55 am:

Problem:
Show that among n+1 arbitrarily chosen integers,there are two whose difference is divisible by n.

Please help!!

love arun

---

By David Loeffler on Friday, December 06, 2002 - 09:16 am:

Consider the residues mod n of all the elements. How many possible residues are there? How many elements are in your set? That's it.

David

---

By Arun Iyer on Friday, December 06, 2002 - 09:42 am:

David,
i am not able to grasp the idea...
Could you elaborate please!!

love arun

---

By Demetres Christofides on Friday, December 06, 2002 - 09:50 am:

Arun, what David is saying is the following:
Suppose you have the numbers a₁,...,a_n+1.
Divide them by n to get remainders r₁,...,r_n+1 where each r_i sattisfies 0<=r_i<n.
The statement is clearly true for the r_i's (pigeonhole principle). Why is it true for the a_i's ?

Demetres

---

By Arun Iyer on Friday, December 06, 2002 - 10:17 am:

Hmmm,
i think i understood...

Proof:
Let A be the set of n+1 arbitrary chosen integers.
Let B be the set of residues(mod n)

#A>(1)#B ..(#A = n+1 and #B = n)

therefore there must be atleast two numbers in A which give the same residue.

Suppose r_i = r_j
Now,
a_i = pn + r_i .. and ..
a_j = qn + r_j

subtracting the two above we get,
a_i - a_j = (p-q)n

Therefore there are atleast two numbers in A which are divisible by n...

love arun

---