A question in combinatorics. (perhaps implementation of the pigeon hole principle).

[MathematicalPhysicist]

let a\in R and Q>=3 where Q\in Z, i need to prove that in the set {a,2a,...,(Q-1)a} there exists a number which its distance from the nearest whole number is smaller than 1/Q.
i got this as an assignment in topic of the pigeon hole, now i don't see how to use it here, what i did so far (havent yet finished) is first for the integers it's trivially correct, so i suppose that a is non integer real number, and first prove it for a between 0 and 1, and afterwards for a>=1, with symmetry we can see that if we prove this then it's trivially valid for the negatives.
so basically my proof is constrcutive, if 0<a<1 then the nearest value is 1 or 0, so either |a|<1/Q or |a-1|<1/Q, if they both arent valid we keep on going to the next number 0<2a<2, because a>=1/Q and 1-a>=1/Q we have that 2a must be between 1 and 2, and so we proceed as before.
my two questions are, is this approach valid, and is there any other proofs which might use the pigeon hole principle?

thanks in advance.

 

[AKG]

First of all, the thing you're asked to prove isn't true. Take a = 1/Q. Then no element of that set has a distance from a whole number smaller than 1/Q. There are two numbers whose distance is equal to 1/Q however, namely a and (Q-1)a. But we can prove in general that under the conditions given, there exists a number from that set whose number is less than or equal to 1/Q.

Partition R into Q classes

C_i = \bigcup _{n \in \mathbb{Z}}\left [n + \frac{i}{Q}, n + \frac{i+1}{Q}\right )

for i = 0, 1, ..., Q-1. Let A = {a, 2a, ..., (Q-1)a}. Now if there an element of A in either C₀ or C_Q-1, then we're done. Otherwise all Q-1 elements of A reside in the Q-2 classes C₁, C₂, ... C_Q-2. By the pigeonhole principle, at least one of these classes must contain two elements of A. Let C_i be such a class, and let ka and ma be the two elements of A in C_i. Without loss of generality, suppose k > m. Then (k-m)a is in A, and naturally it's distance from the nearest whole number is less than or equal to 1/Q.

As for your proof, it doesn't work. First of all, how do you deduce that 2a must be between 1 and 2? Take Q = 10, a = 0.11. Then |0.11| > 1/Q, and |0.11 - 1| > 1/Q, but 2a = 0.22 is not between 1 and 2. Anyways, you go on to say "and so we proceed as before" but this doesn't seem to go anywhere. You haven't said why this process will eventually find you a multiple of a that's at most 1/Q away from some whole number.

 

[MathematicalPhysicist]

thank AKG.
just one question from your assertion we have that n+i/Q<=ka<n+(i+1)/Q
n+i/Q<=ma<n+(i+1)/Q which is -n-(i+1)/Q<-ma<=-n-i/Q
then by combining both inequalities we do get:
|ka-ma|<1/Q, and it's obvious why, cause when combining two inequalities i.e, 1>=1 and 2>1 we get 2+1>1+1, a strict inequality.

 

[MathematicalPhysicist]

i think we need a closed interval here.

 

[MathematicalPhysicist]

but i understand why it's not correct the way the question was stated first.

 

[AKG]

thank AKG.
just one question from your assertion we have that n+i/Q<=ka<n+(i+1)/Q
n+i/Q<=ma<n+(i+1)/Q which is -n-(i+1)/Q<-ma<=-n-i/Q
then by combining both inequalities we do get:
|ka-ma|<1/Q, and it's obvious why, cause when combining two inequalities i.e, 1>=1 and 2>1 we get 2+1>1+1, a strict inequality.

What's the question?

i think we need a closed interval here.

Where? What are you talking about?

but i understand why it's not correct the way the question was stated first.

Good.

 

[MathematicalPhysicist]

i mean that C_i should be a class of closed intervals, cause if it's a union of half open interval than we get a sharp inequality.

 

[AKG]

i mean that C_i should be a class of closed intervals, cause if it's a union of half open interval than we get a sharp inequality.

If C_i is a union of closed intervals, then we don't get a partition of \mathbb{R}. The C_i overlap, so the pigeonhole principle doesn't work. And no, we don't get a sharp inequality. Did you even read my post? The very first thing I did was given an example when we only get equality. Remember, pick a = 1/Q.

Next, note the following part in my proof:

Now if there an element of A in either C₀ or C_Q-1, then we're done. Otherwise all Q-1 elements of A reside in the Q-2 classes C₁, C₂, ... C_Q-2.

From the second sentence, you showed that we get strict inequality. But that's the "otherwise" case. In the first case, where there is some element in either C₀ or C_Q-1, that's where we get the possibility of equality. Specifically, since C_Q-1 is the union of intervals like [n-Q^-1, n), our element of A might be n-Q^-1, which is exactly (not less than) Q^-1 away from the nearest whole.

 

[MathematicalPhysicist]

C_Q-1 is a union of intervals: [n+1-Q^-1,n+1).

 

[AKG]

Yes, that's right.