Maths Olympiad Prep

Library / /74 of 299

Algebra Difficulty 6.0 National Olympiad Prove it Iran

Prove that among any 9 distinct real numbers, there exist 4 distinct numbers aa, bb, cc, dd such that
(ac+bd)2910(a2+b2)(c2+d2). (ac + bd)^2 \geq \frac{9}{10}(a^2 + b^2)(c^2 + d^2).

Solutions — 2

Solution 1

According to the Lagrange's identity, we have (a2+b2)(c2+d2)=(ac+bd)2+(adbc)2(a^2 + b^2)(c^2 + d^2) = (ac + bd)^2 + (ad - bc)^2. So we have to prove that:
(ac+bd)29(adbc)2    ac+bd3adbc (ac + bd)^2 \geq 9(ad - bc)^2 \iff |ac + bd| \geq 3|ad - bc|
First, we check the case where none of the numbers are zero. By dividing both sides by ac|ac|, we have:
1+badc3dcba |1 + \frac{b}{a} \cdot \frac{d}{c}| \geq 3|\frac{d}{c} - \frac{b}{a}|
Suppose a,b,ca, b, c, and dd have the same sign. In this case:
1+badc1 |1 + \frac{b}{a} \cdot \frac{d}{c}| \geq 1
It suffices to prove that:
dcba13 |\frac{d}{c} - \frac{b}{a}| \leq \frac{1}{3}
Now, if we put the positive numbers in set AA and the negative numbers in set BB, each of them will give us A2\lfloor \frac{|A|}{2} \rfloor and B2\lfloor \frac{|B|}{2} \rfloor pairs of numbers that have the same sign. So, in total, we will have 4 pairs of numbers that have the same sign (because one of the sets has an even number of elements and the other has an odd number of elements). For each pair (ai,bi)(a_i, b_i), we choose a fraction from among aibi\frac{a_i}{b_i}, biai\frac{b_i}{a_i} that doesn't exceed one. Now we have 4 fractions between zero and one, so according to the pigeonhole principle, the distance between two of them is less than 13\frac{1}{3}, and the result follows.

If one of the numbers, like aa, is zero, then just before the division, by proof by contradiction we have bb is non zero and:
dc13 |\frac{d}{c}| \geq \frac{1}{3}
Similar to the previous case, it is possible to find 3 pairs of the same sign where the assigned fractions are between 13\frac{1}{3} and 1, and again according to the pigeonhole principle, a difference between two fractions will be less than 13\frac{1}{3}. The result follows.

Solution 2

We shall prove a more strong argument; We choose 8 numbers from these nine numbers and denote them by x1,y1,,x4,y4x_1, y_1, \dots, x_4, y_4. We arranged them in the way that xiyi|x_i| \leq |y_i| and xi,yix_i, y_i have the same sign. Consider four points ui=(xi,yi)u_i = (|x_i|, |y_i|) and the angle they make with the origin would be in the interval [0,π4][0, \frac{\pi}{4}]. Thus, the angle between two of them, say ui,uju_i, u_j is less that or equal to π12\frac{\pi}{12}. Hence, putting a=xi,b=yia = x_i, b = y_i and c=xj,d=yjc = x_j, d = y_j it follows that

ac+bd=xixj+yiyj=uiuj=uiujcosθ. |ac + bd| = |x_i x_j + y_i y_j| = u_i \cdot u_j = |u_i| \cdot |u_j| \cos \theta.
That is, (ac+bd)2(a2+b2)(c2+d2)cos2π12=2+34(a2+b2)(c2+d2)(ac + bd)^2 \ge (a^2 + b^2)(c^2 + d^2)\cos^2 \frac{\pi}{12} = \frac{2+\sqrt{3}}{4}(a^2 + b^2)(c^2 + d^2).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.