Suppose $x_{1}, \ldots, x_{n}$ and $y_{1}, \ldots, y_{n}$ are monotonically increasing sequences of non-negative numbers, each with $n$ terms summing to 1.

a) What is the maximum possible value of $\min _{1 \leq i \leq n}\left|x_{i}-y_{i}\right|$ ?

b) What is the maximum possible value of $\sum_{i=1}^{n}\left|x_{i}-y_{i}\right|$ ?
Solution. a) If $n=1$, then $x_{1}=y_{1}=1$, and thus the minimum value asked in the problem is 0. In the following, we will deal with the case $2 \leq n$. Since the sum of the non-negative numbers $x_{1}, \ldots, x_{n}$ is 1, and $x_{1}$ is the (one of the) smallest among them, we have

$$
0 \leq x_{1} \leq \frac{x_{1}+\ldots+x_{n}}{n}=\frac{1}{n}
$$

Similarly, $0 \leq y_{1} \leq \frac{1}{n}$, and thus $\left|x_{1}-y_{1}\right| \leq \frac{1}{n}$ also holds. Therefore, the inequality

$$
\min _{1 \leq i \leq n}\left|x_{i}-y_{i}\right| \leq \frac{1}{n}
$$

always holds. On the other hand, if, for example, the two sequences are

$$
x_{1}=x_{2}=\ldots=x_{n}=\frac{1}{n} \quad \text { and } \quad y_{1}=\ldots=y_{n-1}=0, \quad y_{n}=1
$$

then $\left|x_{1}-y_{1}\right|=\ldots=\left|x_{n-1}-y_{n-1}\right|=\frac{1}{n}$, and $\left|x_{n}-y_{n}\right|=1-\frac{1}{n} \geq \frac{1}{n}$. Thus, there exist sequences for which $\min _{1 \leq i \leq n}\left|x_{i}-y_{i}\right|=\frac{1}{n}$, meaning that the $\frac{1}{n}$ estimate cannot be improved. This proves that for $n \geq 2$, the answer to part a) of the problem is $\frac{1}{n}$.

b) The terms of both sequences are non-negative numbers, so

$$
\begin{aligned}
\sum_{i=1}^{n}\left|x_{i}-y_{i}\right| & =\left|x_{n}-y_{n}\right|+\sum_{i=1}^{n-1}\left|x_{i}-y_{i}\right| \leq\left|x_{n}-y_{n}\right|+\sum_{i=1}^{n-1}\left(x_{i}+y_{i}\right)= \\
& =\max \left(x_{n}, y_{n}\right)-\min \left(x_{n}, y_{n}\right)+1-x_{n}+1-y_{n}=2-2 \min \left(x_{n}, y_{n}\right)
\end{aligned}
$$

Since the sum of the numbers $x_{1}, \ldots, x_{n}$ is 1, and $x_{n}$ is the (one of the) largest among them, we have $x_{n} \geq \frac{1}{n}$, and similarly, $y_{n} \geq \frac{1}{n}$ can also be proven. Thus, $2-2 \min \left(x_{n}, y_{n}\right) \leq 2-\frac{2}{n}$, meaning that the sum in question can be at most $2-\frac{2}{n}$. However, for the sequences mentioned in the solution to part a), we saw that

$$
\left|x_{1}-y_{1}\right|=\ldots=\left|x_{n-1}-y_{n-1}\right|=\frac{1}{n} \quad \text { and } \quad\left|x_{n}-y_{n}\right|=1-\frac{1}{n}
$$

so the value of the sum $\sum_{i=1}^{n}\left|x_{i}-y_{i}\right|$ is exactly $2-\frac{2}{n}$. Therefore, the largest possible value of the sum is $2-\frac{2}{n}$.