IMC 2021 · Day 1 · P3

Hint: To get an upper bound, use that some of the gaps after $n$ steps are still intact some steps later.

Let $d^\star = \sup\{ d \mid d \text{ is good} \}$. We will show that $d^\star = \ln(2) \doteq 0.693$.

1. $d^\star \le \ln 2$:

Assume that some $d$ is good and let $a_1, a_2, \dots$ be the witness sequence.

Fix an integer $n$. By assumption, the prefix $a_1, \dots, a_n$ of the sequence splits the interval $[0, d]$ into $n + 1$ parts, each of length at most $1/n$.

Let $0 \le \ell_1 \le \ell_2 \le \dots \le \ell_{n+1}$ be the lengths of these parts. Now for each $k = 1, \dots, n$ after placing the next $k$ terms $a_{n+1}, \dots, a_{n+k}$, at least $n + 1 - k$ of these initial parts remain intact. Hence $\ell_{n+1-k} \le \frac{1}{n+k}$. Hence $$\tag{2} d = \ell_1 + \dots + \ell_{n+1} \le \frac{1}{n} + \frac{1}{n+1} + \dots + \frac{1}{2n}.$$ As $n \to \infty$, the RHS tends to $\ln(2)$ showing that $d \le \ln(2)$.

Hence $d^\star \le \ln 2$ as desired.

2. $d^\star \ge \ln 2$:

Observe that $$\ln 2 = \ln 2n - \ln n = \sum_{i=1}^{n} \bigl( \ln(n+i) - \ln(n+i-1) \bigr) = \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}{2n} \right) + \ln \left( 1 + \frac{1}{2n+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\frac32$, $a_2 = \ln\frac54$, $a_3 = \ln\frac74$, $a_4 = \ln\frac98$, ….

Remark. This remark describes in fact the same solution from a different view and some ideas behind it. It could be erased after marking is finished.

Estimate (2) is quite natural. To prove that RHS tends to $\ln 2$ we use some integral estimates by $$\int_n^{2n+1} \frac{1}{x}\,dx = \ln(2n+1) - \ln n.$$ Here we can observe that $$\int_n^{2n} \frac{1}{x}\,dx = \ln 2$$ is independent of $n$. This can help us with the construction since the above equality means $$I_1 = \int_n^{n+1} \frac{1}{x}\,dx = \int_{2n}^{2n+1} \frac{1}{x}\,dx + \int_{2n+1}^{2n+2} \frac{1}{x}\,dx = I_2 + I_3,$$ so, interval of length $I_1$ can be splitted into two intervals of lengths $I_2$ and $I_3$. In fact, after placing the point $a_n$ in the construction for $d = \ln 2$, the lengths of the $n + 1$ intervals are $$\int_{n+1}^{n+2} \frac{1}{x}, \quad \int_{n+2}^{n+3} \frac{1}{x}, \quad \dots, \quad \int_{2n+1}^{2n+2} \frac{1}{x}$$ with total length $$d = \int_{n+1}^{2n+2} \frac{1}{x} = \ln 2.$$