Jackson's Subsets

Find the smallest value of n n for which the following statement is true:

"Given a set of n n distinct real numbers { x 1 , , x n } \{x_1,\ldots,x_n\} , there will always exist at least one pair of those numbers x a x_a and x b x_b that satisfy the inequality x a x b 1 + x a x b 1 3 . \left|\dfrac{x_a-x_b}{1+x_ax_b}\right|\leq\dfrac{1}{\sqrt{3}}. "


The answer is 7.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Jubayer Nirjhor
Apr 7, 2015

Let S = ( π / 2 , π / 2 ) \mathbb S=\left(-\pi/2,\pi/2\right) . The function tan : S R \tan : \mathbb S\mapsto \mathbb R ranges over all real numbers, so for all real numbers x i x_i there exists a unique θ i S \theta_i\in\mathbb S such that x i = tan θ i x_i=\tan\theta_i . So there exists a bijection between sequences of real numbers with their respective θ i S \theta_i\in\mathbb S value. We can hence work only with the θ i \theta_i values.

Suppose x a = tan θ a x_a=\tan \theta_a and x b = tan θ b x_b=\tan\theta_b , and WLOG let θ a θ b \theta_a\ge\theta_b . We have tan π 6 = 1 3 x a x b 1 + x a x b = tan θ a tan θ b 1 + tan θ a tan θ b = tan ( θ a θ b ) \tan\dfrac\pi 6=\dfrac{1}{\sqrt 3}\ge \left|\dfrac{x_a-x_b}{1+x_ax_b}\right|=\left|\dfrac{\tan\theta_a-\tan\theta_b}{1+\tan\theta_a\tan\theta_b}\right|=\left|\tan\left(\theta_a-\theta_b\right)\right| and since θ a θ b \theta_a\ge\theta_b we have tan π 6 tan ( θ a θ b ) θ a θ b π 6 \tan\dfrac\pi 6\ge\tan\left(\theta_a-\theta_b\right)\implies \theta_a-\theta_b\le \dfrac\pi 6 because tan : S R \tan:\mathbb S\mapsto \mathbb R is increasing.

Now split S = ( π 2 , π 2 ) \mathbb S=\left(-\dfrac\pi 2,\dfrac\pi 2\right) into the following 6 6 intervals ( π 2 , π 3 ] , ( π 3 , π 6 ] , ( π 6 , 0 ] , ( 0 , π 6 ] , ( π 6 , π 3 ] , ( π 3 , π 2 ) . \left(-\dfrac {\pi} 2,-\dfrac{\pi} 3\right],\left(-\dfrac {\pi} 3,-\dfrac\pi 6\right],\left(-\dfrac \pi 6,0\right],\left(0,\dfrac\pi 6\right],\left(\dfrac\pi 6,\dfrac \pi 3\right],\left(\dfrac\pi 3,\dfrac\pi 2\right). If n 6 n\le 6 we can choose all the θ i \theta_i from different intervals, equally spaced, so that we'll have θ i θ j > π / 6 \theta_i-\theta_j>\pi/6 for all i , j i,j . Therefore all sequences with n 6 n\le 6 might not satisfy the problem conditions.

If n = 7 n=7 then by the Pigeonhole Principle at least two θ i \theta_i will be from the same interval, so we'll have θ a θ b π / 6 \theta_a-\theta_b\le\pi/6 for those two values. Hence n = 7 n=\fbox{7} is the smallest size of such sequence.

This is awesome!

Pi Han Goh - 5 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...