Maths Olympiad Prep

Library / /28 of 43

Algebra Difficulty 8.0 Shortlist Find the answer

We say a triple (a1,a2,a3)\left(a_{1}, a_{2}, a_{3}\right) of nonnegative reals is better than another triple (b1,b2,b3)\left(b_{1}, b_{2}, b_{3}\right) if two out of the three following inequalities a1>b1,a2>b2,a3>b3a_{1}>b_{1}, a_{2}>b_{2}, a_{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.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The answer is n4n \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), \quad\left(\frac{2}{5}, 0, \frac{3}{5}\right), \quad\left(\frac{3}{5}, \frac{2}{5}, 0\right), \quad\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 y815y \geqslant \frac{8}{15} or z715z \geqslant \frac{7}{15}. Triple (x,y,z)(x, y, z) is not worse than (25,0,35)x25\left(\frac{2}{5}, 0, \frac{3}{5}\right)-x \geqslant \frac{2}{5} or z35z \geqslant \frac{3}{5}. Triple (x,y,z)(x, y, z) is not worse than (35,25,0)x35\left(\frac{3}{5}, \frac{2}{5}, 0\right)-x \geqslant \frac{3}{5} or y25y \geqslant \frac{2}{5}. Since x+y+z=1x+y+z=1, then it is impossible that all inequalities x25,y25x \geqslant \frac{2}{5}, y \geqslant \frac{2}{5} and z715z \geqslant \frac{7}{15} are true. Suppose that x<25x<\frac{2}{5}, then y25y \geqslant \frac{2}{5} and z35z \geqslant \frac{3}{5}. Using x+y+z=1x+y+z=1 and x0x \geqslant 0 we get x=0,y=25,z=35x=0, y=\frac{2}{5}, z=\frac{3}{5}. We obtain the triple (0,25,35)\left(0, \frac{2}{5}, \frac{3}{5}\right) which is worse than (215,1115,215)\left(\frac{2}{15}, \frac{11}{15}, \frac{2}{15}\right). Suppose that y<25y<\frac{2}{5}, then x35x \geqslant \frac{3}{5} and z715z \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 x25x \geqslant \frac{2}{5} and y815y \geqslant \frac{8}{15}. We get (by admissibility, again) that z115z \leqslant \frac{1}{15} and y35y \leqslant \frac{3}{5}. 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)\left(x_{1}, y_{1}, z_{1}\right), \quad\left(x_{2}, y_{2}, z_{2}\right), \quad\left(x_{3}, y_{3}, z_{3}\right) Denote a(S)=min(x1,x2,x3),b(S)=min(y1,y2,y3),c(S)=min(z1,z2,z3)a(S)=\min \left(x_{1}, x_{2}, x_{3}\right), b(S)=\min \left(y_{1}, y_{2}, y_{3}\right), c(S)=\min \left(z_{1}, z_{2}, z_{3}\right). It is easy to check that S1S_{1} : (x1a1abc,y1b1abc,z1c1abc)(x2a1abc,y2b1abc,z2c1abc)(x3a1abc,y3b1abc,z3c1abc)\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 ((1abc)x+a,(1abc)y+b,(1abc)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\left(S_{1}\right)=b\left(S_{1}\right)=c\left(S_{1}\right)=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 0. 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 x2x3x_{2} \geqslant x_{3}. If z2z1z_{2} \geqslant z_{1}, then the second triple (x2,0,z2)\left(x_{2}, 0, z_{2}\right) is not worse than the other two triples from SS. So we may assume that z1z2z_{1} \geqslant z_{2}. If y1y3y_{1} \geqslant y_{3} then the first triple is not worse than the second and the third and we assume y3y1y_{3} \geqslant y_{1}. Consider the three pairs of numbers x2,y1;z1,x3;y3,z2x_{2}, y_{1} ; z_{1}, x_{3} ; y_{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,1x2,0)\left(x_{2}, 1-x_{2}, 0\right) is not worse than all triples from SS, for the second we may take (1z1,0,z1)\left(1-z_{1}, 0, z_{1}\right) and for the third (0,y3,1y3)-\left(0, y_{3}, 1-y_{3}\right). So we found a desirable special triple for any given SS.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.