Cool theorem!

[suyver]

I just learned something really cool. [a)]

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

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

Isn't that cool?!

(I think I have a proof, but feel free to give it a go and post something [:D] ).

[StephenPrivitera]

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 x_i < x_j , then C \leq x_j-x_i \leq R .

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?

[KLscilevothma]

The first thought popped up to my mind was pigeon hole principle though I'm not good at applying it. [:)]

[suyver]

Originally posted by StephenPrivitera
why 13?
[...]
Anyway, why would someone come up with such a theorem?

Just for fun, obviously! [:D] (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. [:D] ]

[Hurkyl]

pfft, sure, just give away the part that is strongly suggested by the form of the fraction. [6)]

[suyver]

Well, I did give you 24 hours and even you, Hurkyl, had not yet given a proof... [;)]

Sorry, maybe I was too fast. I'll remove the hint for a while.

[KLscilevothma]

The middle part seems to be in the form
tan (A - B) = \frac{tan A -tan B}{1- tan A tan B}

Also,
2-\sqrt{3} = tan \frac{\pi}{13-1}
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. [6)]

[suyver]

Sure you are. In fact: you're nearly there! [:))]

Cheers,
Freek Suyver.

[STAii]

Originally posted by KL Kam
The middle part seems to be in the form
tan (A - B) = \frac{tan A -tan B}{1- tan A tan B}

Also,
2-\sqrt{3} = tan \frac{\pi}{13-1}
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. [6)]

Shouldn't that be
tan (A - B) = \frac{tan A -tan B}{1+ tan A tan B}
(i am sure it is a typo)

[NateTG]

Let's apply these notes:

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

The A_i and A_j in that pair correspond to x_i and x_j.

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

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

0 \; < \; \frac{x_i-x_j}{1+x_ix_j} \; < tan \frac{\pi}{n-1}

[suyver]

Exactly!

And we know that

\tan\frac{\pi}{12} = 2-\sqrt{3}

which completes the proof. Neat, huh? (And, absolutely useless! [;)] )

-Freek.

[STAii]

Originally posted by NateTG
... since there are 13 A_i on the interval, so there must be a pair that is at most the mean distance to the next ...
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.

[Hurkyl]

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.

[NateTG]

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.

[STAii]

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 ?
Thanks.

[uart]

STAii, The x_i values are mapped to \Theta_i values all in the range of -\pi/2 to +\pi/2. It has to be like this to have an invertable mapping and to have inequality relationships hold. This was implied in the solution.

[STAii]

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 ?
Thanks.

[uart]

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

I think you may be mistaking it as \Theta_i = \tan(x_i) , which wont work.

[STAii]

Yes, you are right. It seems i misunderstood it the first time.
Thank you.