This is China West Mathematics Olympics(CWMO), Day 1 P4

I trust the answer is $\frac{n}{n+1}$, but I can't solve it. Need help.

Indeed, the answer is $\boxed{\frac{n}{n+1}}.$ First, we will attempt to view the problem from a different angle. As written, it is intimidating and confusing. Let $s_0 = 0, s_1 = x_1, s_2 = x_1 + x_2, \cdots, s_n = x_1 + x_2 + \cdots + x_n.$ Let $t_0 = 0, t_1 = \varepsilon_1, t_2 = \varepsilon_1 + \varepsilon_2, \cdots s_n = \varepsilon_1 + \varepsilon_2 + \cdots + \varepsilon_n.$ Observe that $$\max_{i, j} \left | \sum_{k=i}^{j} (\varepsilon_k - x_k) \right | = \max_{i, j} \left | (t_j - s_j) - (t_{i-1} - s_{i-1}) \right | = \max_{0 \le j \le n} (t_j - s_j) - \min_{0 \le i \le n} (t_i - s_i). \qquad (1)$$ With this, we will return to the problem. Notice that for the sequence $x_1, x_2, \cdots, x_n = \frac{1}{n+1}, \frac{1}{n+1}, \cdots, \frac{1}{n+1},$ the minimum $\lambda$ satisfying the inequality in the question is $\frac{n}{n+1}.$ In order to see this, observe that if $t_{i+1} > t_i$ for $i \in \mathbb{Z}_{ \ge 0}$, then $(t_{i+1} - s_{i+1}) - (t_i - s_i) \ge \frac{n}{n+1}$ and we're done. Otherwise, $0 = t_0 = t_1 = t_2 = \cdots = t_n$ and so $(t_0 - s_0) - (t_n - s_n) = \frac{n}{n+1}$ and we're still done. Therefore, we've shown that $\lambda \ge \frac{n}{n+1}.$ Let us now show that we can always select integers $t_1, t_2, \cdots, t_n$ such that $$\max_{0 \le j \le n} (t_j - s_j) - \min_{0 \le i \le n} (t_i - s_i) \le \frac{n}{n+1},$$for any real numbers $0 = s_0 \le s_1 \le s_2 \le \cdots \le s_n$ such that $s_{i+1} - s_i \le 1$ for each $i \in \mathbb{Z}_{\ge 0}.$ Let us now describe how to select these $t_i$'s. Notice that there must exist a $0 \le k < n+1$ such that the $\{s_i \} \notin \left (\frac{k}{n+1}, \frac{k+1}{n+1}\right)$ for every $0 \le i \le n,$ where $\{ \}$ denotes fractional part. This is clear, since there are $n+1$ such "buckets" $\left ( \frac{k}{n+1}, \frac{k+1}{n+1} \right)$, and only $n$ "pigeons" $\{s_i\}.$ Now, our strategy for selecting the $t_i$'s is simple. If $1 \le i \le n$ satisfies $\{s_i\} \le \frac{k}{n+1}$, then pick $t_i = \left \lfloor s_i \right \rfloor$. Otherwise, $1 \le i \le n$ satisfies $\{s_i \} \ge \frac{k+1}{n+1}$, in which case we will select $t_i = \left \lceil s_i \right \rceil.$ In this way, observe that $t_i - s_i \in \left [- \frac{k}{n+1}, \frac{n-k}{n+1} \right ]$, and so therefore $$\max_{0 \le j \le n} (t_j - s_j) - \min_{0 \le i \le n} (t_i - s_i) \le \frac{n-k}{n+1} - \left (- \frac{k}{n+1} \right) = \frac{n}{n+1},$$and so this is our desired choice of $t_i$'s. The only thing left to verify is that $\varepsilon_i = t_i - t_{i-1} \in \{0, 1\}$ for all $1 \le i \le n.$ However, this is easily checked, and so we're done. $\square$

Pathological wrote: Indeed, the answer is $\boxed{\frac{n}{n+1}}.$ First, we will attempt to view the problem from a different angle. As written, it is intimidating and confusing. Let $s_0 = 0, s_1 = x_1, s_2 = x_1 + x_2, \cdots, s_n = x_1 + x_2 + \cdots + x_n.$ Let $t_0 = 0, t_1 = \varepsilon_1, t_2 = \varepsilon_1 + \varepsilon_2, \cdots s_n = \varepsilon_1 + \varepsilon_2 + \cdots + \varepsilon_n.$ Observe that $$\max_{i, j} \left | \sum_{k=i}^{j} (\varepsilon_k - x_k) \right | = \max_{i, j} \left | (t_j - s_j) - (t_{i-1} - s_{i-1}) \right | = \max_{0 \le j \le n} (t_j - s_j) - \min_{0 \le i \le n} (t_i - s_i). \qquad (1)$$ With this, we will return to the problem. Notice that for the sequence $x_1, x_2, \cdots, x_n = \frac{1}{n+1}, \frac{1}{n+1}, \cdots, \frac{1}{n+1},$ the minimum $\lambda$ satisfying the inequality in the question is $\frac{n}{n+1}.$ In order to see this, observe that if $t_{i+1} > t_i$ for $i \in \mathbb{Z}_{ \ge 0}$, then $(t_{i+1} - s_{i+1}) - (t_i - s_i) \ge \frac{n}{n+1}$ and we're done. Otherwise, $0 = t_0 = t_1 = t_2 = \cdots = t_n$ and so $(t_0 - s_0) - (t_n - s_n) = \frac{n}{n+1}$ and we're still done. Therefore, we've shown that $\lambda \ge \frac{n}{n+1}.$ Let us now show that we can always select integers $t_1, t_2, \cdots, t_n$ such that $$\max_{0 \le j \le n} (t_j - s_j) - \min_{0 \le i \le n} (t_i - s_i) \le \frac{n}{n+1},$$for any real numbers $0 = s_0 \le s_1 \le s_2 \le \cdots \le s_n$ such that $s_{i+1} - s_i \le 1$ for each $i \in \mathbb{Z}_{\ge 0}.$ Let us now describe how to select these $t_i$'s. Notice that there must exist a $0 \le k < n+1$ such that the $\{s_i \} \notin \left (\frac{k}{n+1}, \frac{k+1}{n+1}\right)$ for every $0 \le i \le n,$ where $\{ \}$ denotes fractional part. This is clear, since there are $n+1$ such "buckets" $\left ( \frac{k}{n+1}, \frac{k+1}{n+1} \right)$, and only $n$ "pigeons" $\{s_i\}.$ Now, our strategy for selecting the $t_i$'s is simple. If $1 \le i \le n$ satisfies $\{s_i\} \le \frac{k}{n+1}$, then pick $t_i = \left \lfloor s_i \right \rfloor$. Otherwise, $1 \le i \le n$ satisfies $\{s_i \} \ge \frac{k+1}{n+1}$, in which case we will select $t_i = \left \lceil s_i \right \rceil.$ In this way, observe that $t_i - s_i \in \left [- \frac{k}{n+1}, \frac{n-k}{n+1} \right ]$, and so therefore $$\max_{0 \le j \le n} (t_j - s_j) - \min_{0 \le i \le n} (t_i - s_i) \le \frac{n-k}{n+1} - \left (- \frac{k}{n+1} \right) = \frac{n}{n+1},$$and so this is our desired choice of $t_i$'s. The only thing left to verify is that $\varepsilon_i = t_i - t_{i-1} \in \{0, 1\}$ for all $1 \le i \le n.$ However, this is easily checked, and so we're done. $\square$ Wonderful! My solution is similar as you. It is easy to find $\lambda \leq 1$, but our goal is $\frac{n}{n+1}$, the distance is $\frac{1}{n+1}$ which lead us to consider $$[0,1)=\bigcup\limits_{m=1}^{n+1} [\frac{m-1}{n+1},\frac{m}{n+1}),$$then it's same as yours. I consider this problem from afternoon to the next day.