Discovering an Unexpected Relationship Between 13 Real Numbers

[suyver]

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 ).

 

[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 [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?

 

[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! (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. ]

 

[Hurkyl]

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

 

[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
[tex] tan (A - B) = \frac{tan A -tan B}{1- tan A tan B} [/tex]

Also,
[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.

 

[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
[tex] tan (A - B) = \frac{tan A -tan B}{1- tan A tan B} [/tex]

Also,
[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.

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)

 

[NateTG]

Let's apply these notes:

So, let
[tex]A_i=\Tan^{-1} x_i[/tex]
then
[tex]-\frac{\pi}{2}<A_i<\frac{\pi}{2}[/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]

 

[suyver]

Exactly!

And we know that

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

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

-Freek.

 

[STAii]

Originally posted by NateTG
... 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 ...

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 separated 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 x₁,x₂ ... x₁₃ should be 13 different numbers (when he said x_i<>x_j 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 [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.

 

[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
[tex] \Theta_i = \tan^{-1}(x_i) [/tex]

I think you may be mistaking it as [tex] \Theta_i = \tan(x_i) [/tex], which won't work.

 

[STAii]

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