# Math Help - A pigeonhole problem

1. ## A pigeonhole problem

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.

2. Originally Posted by chem3
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.
Maybe you can't do because it is not true as stated.
{1,2,3,4,5} are five integers where are the multiples of 4?

3. Originally Posted by Plato
Maybe you can't do because it is not true as stated.
{1,2,3,4,5} are five integers where are the multiples of 4?
By definition: K is a multiple of n means that => K = a.n for some integer a ~= 0.

so, in your example: n = 5, n-1 = 4
There are two numbers, namely 5,1 whose difference (4) is a nultiple of n-1 (4).
4 = 1.4 (a is 1 here)

4. Consider a set of n integers. Put all of them in the form
$n_i = (n - 1)a_i + k_i$

Represent each element by its corresponding $k _i$ value.

At best we may select n - 1 of these $k_i$ values (and hence $n_i$ values) such that the difference between any two of them is not divisible by n - 1 simply by choosing all values of $k_i$ to be different. (Because if $k_j = k_i$ for some $j \neq i$ then the difference between them would be zero, implying that the difference between the numbers they represent is a multiple of n - 1.)

But we can't find any more than n - 1 different $k_i$ values. (Because only n - 1 different $k_i$ values exist.)

So our list of n integers must include two elements $k_j = k_i$ in which case the difference between them is a multiple of n - 1.

-Dan

5. Thanks ver much, topsquark!

But there are some points I didn't get very well.

1- How did you know that any integer (even or odd, positive or negative) can be written in the form:
$n_i = (n - 1)a_i + k_i$

2- What are $a _i$'s and $k _i$'s? Are they integers...?

6. OK, let's consider the set of 5 (n = 5) integers: {1,2,3,4,5}
We can write the integers in the form $n_i = (n-1)a_i + k_i$ as follows:

1 = (5-1)1 + (-3) = 4 + (-3) = 1
2 = (5-1)1 + (-2) = 4 + (-2) = 2
3 = (5-1)1 + (-1) = 4 + (-1) = 3
4 = (5-1)1 + (0) = 4 + (0) = 4
5 = (5-1)1 + (1) = 4 + (1) = 5

So there are n $k_i$'s and not n-1 in the example above, namely (-3, -2, -1, 0, 1)!

Am I missing something?

7. Originally Posted by chem3
OK, let's consider the set of 5 (n = 5) integers: {1,2,3,4,5}
We can write the integers in the form $n_i = (n-1)a_i + k_i$ as follows:

1 = (5-1)1 + (-3) = 4 + (-3) = 1
2 = (5-1)1 + (-2) = 4 + (-2) = 2
3 = (5-1)1 + (-1) = 4 + (-1) = 3
4 = (5-1)1 + (0) = 4 + (0) = 4
5 = (5-1)1 + (1) = 4 + (1) = 5

So there are n $k_i$'s and not n-1 in the example above, namely (-3, -2, -1, 0, 1)!

Am I missing something?
Yes, the $a_i$ and $k_i$ are integers. Let me put all the $k_i$'s in your list to be positive numbers or 0:
1 = 4*0 + 1
2 = 4*0 + 2
3 = 4*0 + 3
4 = 4*1 + 0
5 = 4*1 + 1

There are only 4 possible k values: 0, 1, 2, and 3.

My apologies for the confusion. This is better done by modular Mathematics and it's hard for me to translate them into something "more normal." Keep the $k_i$ values as positive or zero, then the proof will go through more smoothly.

-Dan

8. This leaves two questions:

1- How do prove that any integer can be written in the form: $n_i = (n-1)a_i + k_i$ such that $a_i$, $k_i$ are integers and $k_i$ >= 0.

2- How do you prove that in the original problem the number of different $k_i$ values required to represent n integers is at most n-1.

Thanks!

9. I clearly misread you posting, sorry.
Do you know the Division Algorithm? If a is an integer and d is a positive integer, then there are unique integers q and r such that $a = qd + r,\quad 0 \le r < d$. Now in your problem because n is assumed to be greater 2, n-1 is a positive integer. So on Dan’s example let the $k_i$ be the pigeonholes. The $k_{n-2} < {n-1}$ so we are putting $n$ pigeons into $n-1$ holes.

10. Thanks Plato!
I got it now.

11. Originally Posted by chem3
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.
Let me state the problem a little differently.
Given $n+1$ positive integers there are two whose difference is multiple of $n$.

The demonstration will be complete if we can show that two numbers have the same remainder upon division by $n$. Since there are $n+1$ integers there must be at least two "pigeons" in two "pigeonholes". Meaning two numbers that leave the same remainder upon division by $n$. Q.E.D.