uniolympiads Ελληνικά

IMC 2008, Day 1, Problem 4

We say a triple (a1,a2,a3)(a_1, a_2, a_3) of nonnegative reals is better than another triple (b1,b2,b3)(b_1, b_2, b_3) if two out of the three following inequalities a1>b1a_1 > b_1, a2>b2a_2 > b_2, a3>b3a_3 > b_3 are satisfied. We call a triple (x,y,z)(x, y, z) special if x,y,zx, y, z are nonnegative and x+y+z=1x + y + z = 1. Find all natural numbers nn for which there is a set SS of nn special triples such that for any given special triple we can find at least one better triple in SS.

Original from the official PDFWe say a triple (a 1 , a 2 , a 3 ) of nonnegative reals is better than another triple (b 1 , b 2 , b 3 ) if two out of the three following inequalities a 1 > b 1 , a 2 > b 2 , a 3 > b 3 are satisfied. We call a triple (x, y, z) special if x, y, z are nonnegative and x + y + z = 1. Find all natural numbers n for which there is a set S of n special triples such that for any given special triple we can find at least one better triple in S.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. The answer is n⩾4n \geqslant 4.

Consider the following set of special triples:

(0,815,715),(25,0,35),(35,25,0),(215,1115,215).\left(0, \frac{8}{15}, \frac{7}{15}\right), \qquad \left(\frac{2}{5}, 0, \frac{3}{5}\right), \qquad \left(\frac{3}{5}, \frac{2}{5}, 0\right), \qquad \left(\frac{2}{15}, \frac{11}{15}, \frac{2}{15}\right).
We will prove that any special triple (x,y,z)(x,y,z) is worse than one of these (triple aa is worse than triple bb if triple bb is better than triple aa). We suppose that some special triple (x,y,z)(x,y,z) is actually not worse than the first three of the triples from the given set, derive some conditions on x,y,zx, y, z and prove that, under these conditions, (x,y,z)(x,y,z) is worse than the fourth triple from the set.

Triple (x,y,z)(x,y,z) is not worse than (0,815,715)\left(0, \frac{8}{15}, \frac{7}{15}\right) means that y⩾815y \geqslant \frac{8}{15} or z⩾715z \geqslant \frac{7}{15}. Triple (x,y,z)(x,y,z) is not worse than (25,0,35)\left(\frac25, 0, \frac35\right) — x⩾25x \geqslant \frac25 or z⩾35z \geqslant \frac35. Triple (x,y,z)(x,y,z) is not worse than (35,25,0)\left(\frac35, \frac25, 0\right) — x⩾35x \geqslant \frac35 or y⩾25y \geqslant \frac25. Since x+y+z=1x+y+z = 1, then it is impossible that all inequalities x⩾25x \geqslant \frac25, y⩾25y \geqslant \frac25 and z⩾715z \geqslant \frac{7}{15} are true. Suppose that x<25x < \frac25, then y⩾25y \geqslant \frac25 and z⩾35z \geqslant \frac35. Using x+y+z=1x+y+z = 1 and x⩾0x \geqslant 0 we get x=0,y=25,z=35x = 0, y = \frac25, z = \frac35. We obtain the triple (0,25,35)\left(0, \frac25, \frac35\right) which is worse than (215,1115,215)\left(\frac{2}{15}, \frac{11}{15}, \frac{2}{15}\right). Suppose that y<25y < \frac25, then x⩾35x \geqslant \frac35 and z⩾715z \geqslant \frac{7}{15} and this is a contradiction to the admissibility of (x,y,z)(x,y,z). Suppose that z<715z < \frac{7}{15}, then x⩾25x \geqslant \frac25 and y⩾815y \geqslant \frac{8}{15}. We get (by admissibility, again) that z⩽115z \leqslant \frac{1}{15} and y⩽35y \leqslant \frac35. The last inequalities imply that (215,1115,215)\left(\frac{2}{15}, \frac{11}{15}, \frac{2}{15}\right) is better than (x,y,z)(x,y,z).

We will prove that for any given set of three special triples one can find a special triple which is not worse than any triple from the set. Suppose we have a set SS of three special triples

(x1,y1,z1),(x2,y2,z2),(x3,y3,z3).(x_1, y_1, z_1), \qquad (x_2, y_2, z_2), \qquad (x_3, y_3, z_3).
Denote a(S)=min(x1,x2,x3),b(S)=min(y1,y2,y3),c(S)=min(z1,z2,z3)a(S) = min(x_1, x_2, x_3), b(S) = min(y_1, y_2, y_3), c(S) = min(z_1, z_2, z_3). It is easy to check that S1S_1:
(x1−a1−a−b−c,y1−b1−a−b−c,z1−c1−a−b−c)(x2−a1−a−b−c,y2−b1−a−b−c,z2−c1−a−b−c)(x3−a1−a−b−c,y3−b1−a−b−c,z3−c1−a−b−c)\begin{aligned} &\left(\frac{x_1 - a}{1-a-b-c}, \frac{y_1 - b}{1-a-b-c}, \frac{z_1 - c}{1-a-b-c}\right)\\ &\left(\frac{x_2 - a}{1-a-b-c}, \frac{y_2 - b}{1-a-b-c}, \frac{z_2 - c}{1-a-b-c}\right)\\ &\left(\frac{x_3 - a}{1-a-b-c}, \frac{y_3 - b}{1-a-b-c}, \frac{z_3 - c}{1-a-b-c}\right) \end{aligned}
is a set of three special triples also (we may suppose that a+b+c<1a+b+c < 1, because otherwise all three triples are equal and our statement is trivial).

If there is a special triple (x,y,z)(x,y,z) which is not worse than any triple from S1S_1, then the triple

((1−a−b−c)x+a,(1−a−b−c)y+b,(1−a−b−c)z+c)((1-a-b-c)x + a, (1-a-b-c)y + b, (1-a-b-c)z + c)
is special and not worse than any triple from SS. We also have a(S1)=b(S1)=c(S1)=0a(S_1) = b(S_1) = c(S_1) = 0, so we may suppose that the same holds for our starting set SS.

Suppose that one element of SS has two entries equal to 00.

Note that one of the two remaining triples from SS is not worse than the other. This triple is also not worse than all triples from SS because any special triple is not worse than itself and the triple with two zeroes.

So we have a=b=c=0a = b = c = 0 but we may suppose that all triples from SS contain at most one zero. By transposing triples and elements in triples (elements in all triples must be transposed simultaneously) we may achieve the following situation x1=y2=z3=0x_1 = y_2 = z_3 = 0 and x2⩾x3x_2 \geqslant x_3. If z2⩾z1z_2 \geqslant z_1, then the second triple (x2,0,z2)(x_2, 0, z_2) is not worse than the other two triples from SS. So we may assume that z1⩾z2z_1 \geqslant z_2. If y1⩾y3y_1 \geqslant y_3, then the first triple is not worse than the second and the third and we assume y3⩾y1y_3 \geqslant y_1. Consider the three pairs of numbers x2,y1x_2, y_1; z1,x3z_1, x_3; y3,z2y_3, z_2. The sum of all these numbers is three and consequently the sum of the numbers in one of the pairs is less than or equal to one. If it is the first pair then the triple (x2,1−x2,0)(x_2, 1-x_2, 0) is not worse than all triples from SS, for the second we may take (1−z1,0,z1)(1-z_1, 0, z_1) and for the third — (0,y3,1−y3)(0, y_3, 1-y_3). So we found a desirable special triple for any given SS.

Transcribed from the official solutions, page 2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?