Serbian Mathematical Olympiad

Solution:

a) It suffices to prove that every normed sequence $a_{1}, a_{2}, \ldots, a_{2 n+1}$ is embeddable in some interval of length $2-\frac{1}{2^{n}}$. We prove the claim by induction on $n$. It is true for $n=0$; let $n \geqslant 1$. By the induction hypothesis there exists a sequence $x_{0}, x_{1}, \ldots, x_{2 n-1} \in\left[0,2-\frac{1}{2^{n-1}}\right]$ such that $\left|x_{i}-x_{i-1}\right|=a_{i}$ for $i=1, \ldots, 2 n-1$. Without loss of generality, we shall assume that $x_{2 n-1} \leqslant 1-\frac{1}{2^{n}}$.

(1) If $a_{2 n} \geqslant \frac{1}{2^{n}}$, we can take $x_{2 n}=x_{2 n-1}+a_{2 n} \in\left[1,2-\frac{1}{2^{n}}\right]$ and $x_{2 n+1}=x_{2 n}-a_{2 n+1} \in\left[0,2-\frac{1}{2^{n}}\right]$, whereby the sequence is embedded in the interval $\left[0,2-\frac{1}{2^{n}}\right]$.

(2) If $a_{2 n}<\frac{1}{2^{n}}$, we shall take $x_{2 n}=x_{2 n-1}-a_{2 n} \in\left[-\frac{1}{2^{n}}, 1-\frac{1}{2^{n}}\right]$ and $x_{2 n+1}=x_{2 n}+a_{2 n+1}$, whereby the sequence is embedded in one of the intervals $\left[0,2-\frac{1}{2^{n}}\right]$ and $\left[-\frac{1}{2^{n}}, 2-\frac{1}{2^{n-1}}\right]$.

b) Let us denote $N=3 \cdot 2^{n-1}-1$. We shall prove that the sequence of length $4 n-1$

$1,1-\frac{1}{N}, 1,1-\frac{2}{N}, 1,1-\frac{2^{2}}{N}, \ldots, 1,1-\frac{2^{n-1}}{N}, 1,1-\frac{2^{n-2}}{N}, 1, \ldots, 1-\frac{2}{N}, 1,1-\frac{1}{N}, 1$

cannot be embedded in the interval $\left(-1+\frac{1}{2 N}, 1-\frac{1}{2 N}\right)$, from which the claim follows.

Assume the contrary. By a simple induction one proves that:

(i) $\left|x_{2 i}\right|<1-\frac{2^{i+1}-1}{2 N}$ and $\left|x_{2 i+1}\right|>\frac{2^{i+1}-1}{2 N}$ for $i=0, \ldots, n$;

(ii) $\left|x_{2 i}\right|<\frac{2^{2 n+2-i}-1}{2 N}$ and $\left|x_{2 i+1}\right|>1-\frac{2^{2 n+2-i}-1}{2 N}$ for $i=n+1, \ldots, 2 n+1$.

Thus for $x_{4 n+3}$ we obtain a contradiction.