International Mathematics Competition

Let $d^{\star}=\sup \{d \mid d$ is good $\}$. We will show that $d^{\star}=\ln (2) \doteq 0.693$. 1. $d^{\star} \leq \ln 2:$ Assume that some $d$ is good and let $a_{1}, a_{2}, \ldots$ be the witness sequence. Fix an integer $n$. By assumption, the prefix $a_{1}, \ldots, a_{n}$ of the sequence splits the interval $[0, d]$ into $n+1$ parts, each of length at most $1 / n$. Let $0 \leq \ell_{1} \leq \ell_{2} \leq \cdots \leq \ell_{n+1}$ be the lengths of these parts. Now for each $k=1, \ldots, n$ after placing the next $k$ terms $a_{n+1}, \ldots, a_{n+k}$, at least $n+1-k$ of these initial parts remain intact. Hence $\ell_{n+1-k} \leq \frac{1}{n+k}$. Hence $$\begin{equation*} d=\ell_{1}+\cdots+\ell_{n+1} \leq \frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{2 n} \tag{2} \end{equation*}$$ As $n \rightarrow \infty$, the RHS tends to $\ln (2)$ showing that $d \leq \ln (2)$. Hence $d^{\star} \leq \ln 2$ as desired. 2. $d^{\star} \geq \ln 2$ : Observe that $$\ln 2=\ln 2 n-\ln n=\sum_{i=1}^{n} \ln (n+i)-\ln (n+i-1)=\sum_{i=1}^{n} \ln \left(1+\frac{1}{n+i-1}\right)$$ Interpreting the summands as lengths, we think of the sum as the lengths of a partition of the segment $[0, \ln 2]$ in $n$ parts. Moreover, the maximal length of the parts is $\ln (1+1 / n)<1 / n$. Changing $n$ to $n+1$ in the sum keeps the values of the sum, removes the summand $\ln (1+1 / n)$, and adds two summands $$\ln \left(1+\frac{1}{2 n}\right)+\ln \left(1+\frac{1}{2 n+1}\right)=\ln \left(1+\frac{1}{n}\right)$$ This transformation may be realized by adding one partition point in the segment of length $\ln (1+1 / n)$. In total, we obtain a scheme to add partition points one by one, all the time keeping the assumption that once we have $n-1$ partition points and $n$ partition segments, all the partition segments are smaller than $1 / n$. The first terms of the constructed sequence will be $a_{1}=\ln \frac{3}{2}, a_{2}=\ln \frac{5}{4}, a_{3}=\ln \frac{7}{4}, a_{4}=\ln \frac{9}{8}, \ldots$.