Solve Logic Problem Using Pigeonhole Principle

[chem3]

Hello,

I have this logic problem which I know should be solved by the pigeonhole principle but I was not successful in solving it after many tries and I hope someone here would help me out.

The problem says:
n integer numbers are given. Show that there are at least two numbers among them whose difference is multiple of n-1.

 

[matt grime]

How many pairs are there? How many remainders mod n-1 are there?

 

[chem3]

How many pairs are there? How many remainders mod n-1 are there?

That's all what the question said!
I think it may need some other logic principles used along with the pigeonhole principle to solve it?

 

[chem3]

Ok from counting principles: The numbers of pairs you can choose from a group of n elements (order does not matter here) is:

(n // 2) i.e. n choose 2
and that's = n!/((n-2)!2!) = ... = n(n-1)/2

I got stuck right there!

 

[matt grime]

Have you met modulo, or clock, arithemetic? It is an important piece of mathematics, and one you were introduced to at the very start of your mathematics education: remainder arithmetic. Take one of those pairs. What is the remainder on division by n-1? It is one of 0,1,2,3,4,..,n-2 (e.g. after dividing by 8, you have remainder 0,1,2,3,4,5, or 7). Being divisible by n-1 means having remainder 0.

Suppose I tell you that x-y has remainder r on division by n-1, and that x-z has remainder s, what is the remainder of z-y? Hint z-y = (x-y)-(x-z).