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.
Consider a set of n integers. Put all of them in the form
Represent each element by its corresponding value.
At best we may select n - 1 of these values (and hence values) such that the difference between any two of them is not divisible by n - 1 simply by choosing all values of to be different. (Because if for some 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 values. (Because only n - 1 different values exist.)
So our list of n integers must include two elements in which case the difference between them is a multiple of n - 1.
-Dan
OK, let's consider the set of 5 (n = 5) integers: {1,2,3,4,5}
We can write the integers in the form 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 's and not n-1 in the example above, namely (-3, -2, -1, 0, 1)!
Am I missing something?
Yes, the and are integers. Let me put all the '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 values as positive or zero, then the proof will go through more smoothly.
-Dan
This leaves two questions:
1- How do prove that any integer can be written in the form: such that , are integers and >= 0.
2- How do you prove that in the original problem the number of different values required to represent n integers is at most n-1.
Thanks!
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 . 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 be the pigeonholes. The so we are putting pigeons into holes.
Let me state the problem a little differently.
Given positive integers there are two whose difference is multiple of .
The demonstration will be complete if we can show that two numbers have the same remainder upon division by . Since there are integers there must be at least two "pigeons" in two "pigeonholes". Meaning two numbers that leave the same remainder upon division by . Q.E.D.