Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Apr 28, 2007 #1
    let [tex]a\in R[/tex] and [tex] Q>=3[/tex] where [tex]Q\in Z[/tex], 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 dont 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.
     
  2. jcsd
  3. Apr 28, 2007 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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

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

    for i = 0, 1, ..., Q-1. Let A = {a, 2a, ..., (Q-1)a}. Now if there an element of A in either C0 or CQ-1, then we're done. Otherwise all Q-1 elements of A reside in the Q-2 classes C1, C2, ... CQ-2. By the pigeonhole principle, at least one of these classes must contain two elements of A. Let Ci be such a class, and let ka and ma be the two elements of A in Ci. 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.
     
  4. Apr 28, 2007 #3
    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.
     
  5. Apr 28, 2007 #4
    i think we need a closed interval here.
     
  6. Apr 28, 2007 #5
    but i understand why it's not correct the way the question was stated first.
     
  7. Apr 28, 2007 #6

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    What's the question?
    Where? What are you talking about?
    Good.
     
  8. Apr 29, 2007 #7
    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.
     
  9. Apr 29, 2007 #8

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    If Ci is a union of closed intervals, then we don't get a partition of [itex]\mathbb{R}[/itex]. The Ci 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 C0 or CQ-1, then we're done. Otherwise all Q-1 elements of A reside in the Q-2 classes C1, C2, ... CQ-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 C0 or CQ-1, that's where we get the possibility of equality. Specifically, since CQ-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.
     
  10. Apr 30, 2007 #9
    C_Q-1 is a union of intervals: [n+1-Q^-1,n+1).
     
  11. Apr 30, 2007 #10

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Yes, that's right.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A question in combinatorics. (perhaps implementation of the pigeon hole principle).
  1. Combinatorics question (Replies: 1)

  2. Combinatorics problem (Replies: 4)

Loading...