IMC 2008 · Day 1 · P4

The answer is $n > 4$.

Consider the following set of special triples: $$\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)$ is worse than one of these (triple $a$ is worse than triple $b$ if triple $b$ is better than triple $a$). We suppose that some special triple $(x, y, z)$ is actually not worse than the first three of the triples from the given set, derive some conditions on $x, y, z$ and prove that, under these conditions, $(x, y, z)$ is worse than the fourth triple from the set.

Triple $(x, y, z)$ is not worse than $\left( 0, \frac{8}{15}, \frac{7}{15} \right)$ means that $y > \frac{8}{15}$ or $z > \frac{7}{15}$. Triple $(x, y, z)$ is not worse than $\left( \frac{2}{5}, 0, \frac{3}{5} \right)$ — $x > \frac{2}{5}$ or $z > \frac{3}{5}$. Triple $(x, y, z)$ is not worse than $\left( \frac{3}{5}, \frac{2}{5}, 0 \right)$ — $x > \frac{3}{5}$ or $y > \frac{2}{5}$. Since $x + y + z = 1$, then it is impossible that all inequalities $x > \frac{2}{5}$, $y > \frac{2}{5}$ and $z > \frac{7}{15}$ are true. Suppose that $x < \frac{2}{5}$, then $y > \frac{2}{5}$ and $z > \frac{3}{5}$. Using $x + y + z = 1$ and $x > 0$ we get $x = 0$, $y = \frac{2}{5}$, $z = \frac{3}{5}$. We obtain the triple $\left( 0, \frac{2}{5}, \frac{3}{5} \right)$ which is worse than $\left( \frac{2}{15}, \frac{11}{15}, \frac{2}{15} \right)$. Suppose that $y < \frac{2}{5}$, then $x > \frac{3}{5}$ and $z > \frac{7}{15}$ and this is a contradiction to the admissibility of $(x, y, z)$. Suppose that $z < \frac{7}{15}$, then $x > \frac{2}{5}$ and $y > \frac{8}{15}$. We get (by admissibility, again) that $z \leqslant \frac{1}{5}$ and $y \leqslant \frac{3}{5}$. The last inequalities imply that $\left( \frac{2}{15}, \frac{11}{15}, \frac{2}{15} \right)$ is better than $(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 $S$ of three special triples $$(x_1, y_1, z_1), \quad (x_2, y_2, z_2), \quad (x_3, y_3, z_3).$$ Denote $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 $S_1$: $$\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)$$ is a set of three special triples also (we may suppose that $a + b + c < 1$, because otherwise all three triples are equal and our statement is trivial).

If there is a special triple $(x, y, z)$ which is not worse than any triple from $S_1$, then the triple $$\bigl( (1 - a - b - c) x + a, (1 - a - b - c) y + b, (1 - a - b - c) z + c \bigr)$$ is special and not worse than any triple from $S$. We also have $a(S_1) = b(S_1) = c(S_1) = 0$, so we may suppose that the same holds for our starting set $S$.

Suppose that one element of $S$ has two entries equal to 0.

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

So we have $a = b = c = 0$ but we may suppose that all triples from $S$ 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 $x_1 = y_2 = z_3 = 0$ and $x_2 > x_3$. If $z_2 > z_1$, then the second triple $(x_2, 0, z_2)$ is not worse than the other two triples from $S$. So we may assume that $z_1 > z_2$. If $y_1 > y_3$, then the first triple is not worse than the second and the third and we assume $y_3 > y_1$. Consider the three pairs of numbers $x_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 $(x_2, 1 - x_2, 0)$ is not worse than all triples from $S$, for the second we may take $(1 - z_1, 0, z_1)$ and for the third — $(0, y_3, 1 - y_3)$. So we found a desirable special triple for any given $S$.