10.9. Given a natural number $k$. Along the road, there are $n$ poles at equal intervals. Misha painted them in $k$ colors and for each pair of monochromatic poles, between which there are no other poles of the same color, he calculated the distance between them. All these distances turned out to be different. For what largest $n$ could this have happened

(M. Tikhomirov, F. Petrov)
Answer. $3 k-1$.

Solution. Let's number the poles from 1 to $n$ along the road and assume the distance between adjacent poles is 1. A pair of poles of the same color, between which there are no other poles of the same color, will be called good.

Estimate. Suppose $n$ poles are painted such that the condition of the problem is satisfied. Let $n_{i}$ be the number of poles of the $i$-th color (from now on, we assume that $n_{i} \geqslant 1$, i.e., all colors are present; otherwise, we can increase $n$ by adding a pole of a new color at the end). Let $a_{i}$ and $b_{i}$ be the numbers of the first and last poles of the $i$-th color.

We have a total of $t=\left(n_{1}-1\right)+\left(n_{2}-1\right)+\ldots+\left(n_{k}-1\right)=$ $=\left(n_{1}+n_{2}+\ldots+n_{k}\right)-k=n-k$ good pairs of poles. Since all distances between poles in good pairs are different, the smallest of these distances is at least 1, the next is at least 2, and so on. Thus, for the sum $S$ of distances in all good pairs, we get the estimate $S \geqslant 1+2+\ldots+t=t(t+1) / 2$.

On the other hand, the sum of all distances for the $i$-th color is $b_{i}-a_{i}$. Therefore, $S=\left(b_{1}+\ldots+b_{k}\right)-\left(a_{1}+\ldots+a_{k}\right)$. The sum $b_{1}+\ldots+b_{k}$ does not exceed the sum of the $k$ largest among the numbers $1,2, \ldots, n$, and the sum $a_{1}+\ldots+a_{k}$ is at least the sum of the $k$ smallest among the numbers $1,2, \ldots, n$, so $S \leqslant(n+(n-$ $-1)+\ldots+(n-k+1))-(1+2+\ldots+k)=k(n-k)=k t$.

Thus, $t(t+1) / 2 \leqslant S \leqslant k t$, from which $t \leqslant 2 k-1$ and $n=k+t \leqslant 3 k-1$. Example. For example, the following coloring works:

$$
1,2, \ldots, k-1, k, k, k-1, \ldots, 2,1,2,3, \ldots, k-1, k
$$

Here, for color 1, there is only one good pair, and the distance between the poles in it is $2 k-1$. For all other colors, there are two good pairs, and for color 2, the distances are $2 k-3$ and 2, for color 3, the distances are $2 k-5$ and 4, and so on, for color $k$ - the distances are 1 and $2 k-2$.

Remark. There are other, more complex examples. For example, the first $k$ poles can be painted in colors $1,2, \ldots, k$, and the pole with number $k+s$, where $s=2^{p}(2 q-1)$, can be painted in color $q$ (for example, for $k=8$ the coloring will look like this: $1,2,3,4,5,6,7,8,1,1,2,1,3,2,4,1,5,3,6,2,7,4,8$). An inductive description of suitable examples is also possible.

Comment. Only the answer - 0 points.

For solving the problem for specific small values of $n$ without generalizing to arbitrary $n$ - no points are awarded.

For proving a weaker estimate or constructing an example with $n<3 k-1$ - no points are awarded.

If in the solution (explicitly or implicitly) it is assumed that all $k$ colors are used - no points are deducted.

The parts "estimate" + "example" are scored $5+2$ points.

The following progress in the "estimate" part is scored and summed:
(a) The number of good pairs of poles is found ($n-k$ in the case of using all $k$ colors) - 1 point.

(b) The lower estimate $S \geqslant 1+2+\ldots+(n-k)=(n-$ $-k)(n-k+1) / 2$ is proved - 1 point.

(c) The upper estimate $S \leqslant k(n-k)$ is proved - 2 points.

To get 2 points for the "example" part, it is sufficient to present a suitable coloring and show that it works. In the case of the coloring from the solution, the proof that it works is obvious, and the absence of an explanation that it works does not result in a point deduction. In the case of presenting non-obvious correct examples (as in the remark), the absence of a proof that the coloring works results in a 1-point deduction. 10.10. Prove that for any three positive real numbers $x, y, z$ the inequality

$$
(x-y) \sqrt{3 x^{2}+y^{2}}+(y-z) \sqrt{3 y^{2}+z^{2}}+(z-x) \sqrt{3 z^{2}+x^{2}} \geqslant 0
$$

(P. Bibikov)

Solution. We will prove that $(x-y) \sqrt{3 x^{2}+y^{2}} \geqslant(x-y)(x+$ $+y)=x^{2}-y^{2}$. If $x \geqslant y$, then $x-y \geqslant 0$ and $\sqrt{3 x^{2}+y^{2}} \geqslant$ $\geqslant \sqrt{x^{2}+2 x y+y^{2}}=x+y$. If $x \leqslant y$, then $x-y \leqslant 0$ and $\sqrt{3 x^{2}+y^{2}} \leqslant \sqrt{x^{2}+2 x y+y^{2}}=x+y$.

By adding the proven inequality $(x-y) \sqrt{3 x^{2}+y^{2}} \geqslant x^{2}-$ $-y^{2}$ to the analogous inequalities $(y-z) \sqrt{3 y^{2}+z^{2}} \geqslant y^{2}-z^{2}$ and $(z-x) \sqrt{3 z^{2}+x^{2}} \geqslant z^{2}-x^{2}$, we obtain the required result.

Comment. The necessary inequality is derived from the inequality $(x-y) \sqrt{3 x^{2}+y^{2}} \geqslant x^{2}-y^{2}$, which is not proven or is incorrectly proven (for example, proven only for $x \geqslant y$) - 3 points.