Cool theorem!

  • Thread starter suyver
  • Start date
  • #1
248
0
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 ).
 

Answers and Replies

  • #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:
  • #3
The first thought popped up to my mind was pigeon hole principle though I'm not good at applying it. :smile:
 
  • #4
248
0
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. ]
 
Last edited:
  • #5
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
pfft, sure, just give away the part that is strongly suggested by the form of the fraction.
 
  • #6
248
0
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.
 
  • #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]

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.
 
  • #8
248
0
Sure you are. In fact: you're nearly there!

Cheers,
Freek Suyver.
 
  • #9
333
1
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)
 
Last edited:
  • #10
NateTG
Science Advisor
Homework Helper
2,450
6
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]
 
Last edited:
  • #11
248
0
Exactly!

And we know that

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

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

-Freek.
 
  • #12
333
1
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.
 
  • #13
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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.
 
  • #14
NateTG
Science Advisor
Homework Helper
2,450
6
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:
  • #15
333
1
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.
 
  • #16
uart
Science Advisor
2,776
9
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.
 
  • #17
333
1
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.
 
  • #18
uart
Science Advisor
2,776
9
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.
 
  • #19
333
1
Yes, you are right. It seems i misunderstood it the first time.
Thank you.
 

Related Threads on Cool theorem!

  • Last Post
Replies
3
Views
54K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
6
Views
17K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
2K
Replies
1
Views
481
Top