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

Cool theorem!

  1. Dec 2, 2003 #1
    I just learned something really cool.

    Choose 13 real numbers [tex]x_1,x_2,\ldots,x_{13}\in\mathbbb{R}[/tex] with [tex]x_i\neq x_j[/tex] if [tex]i\neq j[/tex]. For these 13 numbers there exist at least two numbers amongst them such that

    [tex]0 \; < \; \frac{x_i-x_j}{1+x_ix_j} \; \leq \; 2-\sqrt{3}[/tex]

    Isn't that cool?!

    (I think I have a proof, but feel free to give it a go and post something ).
  2. jcsd
  3. Dec 2, 2003 #2
    why 13? This doesn't seem like a very easy thing to prove, but 13 numbers are a lot of numbers. That gives 78 i,j pairs.
    Take the two closest numbers, call the positive difference between them C. Take the two farthest numbers, call the positive difference between them R. If [tex] x_i < x_j [/tex], then [tex]C \leq x_j-x_i \leq R [/tex].

    Hmm... Well I thought if I could bound the differences and products I could come up with some bound for the quotient of the difference and product. It doesn't seem to be working.

    Anyway, why would someone come up with such a theorem?
    Last edited: Dec 2, 2003
  4. Dec 3, 2003 #3
    The first thought popped up to my mind was pigeon hole principle though I'm not good at applying it. :smile:
  5. Dec 3, 2003 #4
    Just for fun, obviously! (Actually, I didn't think of it, it appeared as a test-problem for a group of students preparing for the International Math Olympiad).

    @KL Kam: that's right, the pigeon hole principle! Shall I give a hint?

    [Hint removed to prevent additional beatings, see below. ]
    Last edited: Dec 3, 2003
  6. Dec 3, 2003 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    pfft, sure, just give away the part that is strongly suggested by the form of the fraction.
  7. Dec 3, 2003 #6
    Well, I did give you 24 hours and even you, Hurkyl, had not yet given a proof... :wink:

    Sorry, maybe I was too fast. I'll remove the hint for a while.
  8. Dec 3, 2003 #7
    The middle part seems to be in the form
    [tex] tan (A - B) = \frac{tan A -tan B}{1- tan A tan B} [/tex]

    [tex] 2-\sqrt{3} = tan \frac{\pi}{13-1} [/tex]
    I think it is where 13 comes from and the place we should apply pigeon hole principle.

    Well, I'm not good enough to finish the proof.
  9. Dec 3, 2003 #8
    Sure you are. In fact: you're nearly there!

    Freek Suyver.
  10. Dec 3, 2003 #9
    Shouldn't that be
    [tex] tan (A - B) = \frac{tan A -tan B}{1+ tan A tan B} [/tex]
    (i am sure it is a typo)
    Last edited: Dec 3, 2003
  11. Dec 3, 2003 #10


    User Avatar
    Science Advisor
    Homework Helper

    Let's apply these notes:

    So, let
    [tex]A_i=\Tan^{-1} x_i[/tex]
    since there are 13 [tex]A_i[/tex] on the interval, so there must be a pair that is at most the mean distance to the next [tex]A_i[/tex], [tex]\frac{\pi}{12}=\frac{\pi}{13-1}[/tex], apart.

    The [tex]A_i[/tex] and [tex]A_j[/tex] in that pair correspond to [tex]x_i[/tex] and [tex]x_j[/tex].

    Since the range for the [tex]A_i[/tex]'s is open, you have a minimum pair distance that is strictly less than [tex]\frac{\pi}{12}[/tex] and the second inequality is also strict.

    Clearly for n distinct real numbers, where n>3, we have the bound:

    [tex]0 \; < \; \frac{x_i-x_j}{1+x_ix_j} \; < tan \frac{\pi}{n-1}[/tex]
    Last edited: Dec 4, 2003
  12. Dec 4, 2003 #11

    And we know that

    [tex] \tan\frac{\pi}{12} = 2-\sqrt{3}[/tex]

    which completes the proof. Neat, huh? (And, absolutely useless! :wink: )

  13. Dec 4, 2003 #12
    Is this proovable (can anyone provide a proof please ?) ?
    Yesterday i was trying to proove this whole 'theory', and i was stuck here, couldn't proove it (Althought it seems logical).
    I used a somehow different way (but mathematically almost the same) to reach this point, but i think NateTG's is better.
  14. Dec 4, 2003 #13


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Chop the interval into 12 equal sized intervals.

    You have 13 points, so one of those portions must contain two points.

    Those two points cannot be seperated by a distance of more than the size of the intervals, thus proving the statement.
  15. Dec 4, 2003 #14


    User Avatar
    Science Advisor
    Homework Helper

    I like Hurkyls proof better b/c it is constructive, but my thought was:

    There are 13 points covering a distance of less than 2&pi;. That means that the mean distance between two points is less than 2/&pi;12.

    Assume by contradiction that there is no pair with distance less than 2&pi;/12. Then the mean distance between points must be larger than or equal to 2&pi;/12 which is a contradiction.
    Last edited: Dec 4, 2003
  16. Dec 6, 2003 #15
    Ummh .... i think i have found a little small problem in this "theory".
    You see, suyver said that the 13 numbers x1,x2 .... x13 should be 13 different numbers (when he said xi<>xj if i<>j).
    But, the 13 different values of x will not give you 13 different values of A.
    Take this example, here are 13 different numbers, that (i think) the theory is not applicable to :
    100*(pi/180), 120*(pi/180), 140*(pi/180), 160*(pi/180), 180*(pi/180), 200*(pi/180), 220*(pi/180), 240*(pi/180), 260*(pi/180), 280*(pi/180), 300*(pi/180), 320*(pi/180), 340*(pi/180)

    Right ?
  17. Dec 6, 2003 #16


    User Avatar
    Science Advisor

    STAii, The [tex]x_i[/tex] values are mapped to [tex]\Theta_i[/tex] values all in the range of [tex]-\pi/2[/tex] to [tex]+\pi/2[/tex]. It has to be like this to have an invertable mapping and to have inequality relationships hold. This was implied in the solution.
  18. Dec 7, 2003 #17
    I don't quite understand your reply (excuse my bad english).
    Is it possible or not to apply the theory on the numbers i put in my last post, if not, is the problem that my numbers didn't match the conditions of the 13 values stated in the original theory, or is it that the theory contains a logic mistake ?
  19. Dec 7, 2003 #18


    User Avatar
    Science Advisor

    Hi STAii, I think you have misunderstood the transform. It is
    [tex] \Theta_i = \tan^{-1}(x_i) [/tex]

    I think you may be mistaking it as [tex] \Theta_i = \tan(x_i) [/tex], which wont work.
  20. Dec 7, 2003 #19
    Yes, you are right. It seems i misunderstood it the first time.
    Thank you.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook