International Mathematics Competition
for University Students
2021

IMC2021: Day 1, Problem 3

Problem 3. We say that a positive real number $\displaystyle d$ is good if there exists an infinite sequence $\displaystyle a_1,a_2,a_3,\ldots \in (0,d)$ such that for each $\displaystyle n$, the points $\displaystyle a_1,\dots,a_n$ partition the interval $\displaystyle [0,d]$ into segments of length at most $\displaystyle 1/n$ each. Find

$\displaystyle \sup\Big\{d\ \big|\ d \text{ is good}\Big\}.$

Josef Tkadlec

Solution 1. Let $\displaystyle d^\star=\sup\{d\ |\ d \textrm{ is good}\}$. We will show that $\displaystyle d^\star=\ln (2)\doteq 0.693$.

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

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

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

Let $\displaystyle 0 \le \ell_1 \le \ell_2 \le \dots \le \ell_{n+1}$ be the lengths of these parts. Now for each $\displaystyle k=1,\dots,n$ after placing the next $\displaystyle k$ terms $\displaystyle a_{n+1},\dots,a_{n+k}$, at least $\displaystyle n+1-k$ of these initial parts remain intact. Hence $\displaystyle \ell_{n+1-k} \le \frac{1}{n+k}$. Hence

$\displaystyle d=\ell_1+\dots+\ell_{n+1} \le \frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{2n}.$

$\displaystyle (1)$

As $\displaystyle n \to \infty$, the RHS tends to $\displaystyle \ln(2)$ showing that $\displaystyle d \le \ln (2)$.

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

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

Observe that

$\displaystyle \ln 2 = \ln 2n - \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 $\displaystyle [0, \ln 2]$ in $\displaystyle n$ parts. Moreover, the maximal length of the parts is $\displaystyle \ln (1 + 1/n) < 1/n$.

Changing $\displaystyle n$ to $\displaystyle n+1$ in the sum keeps the values of the sum, removes the summand $\displaystyle \ln(1+1/n)$, and adds two summands

$\displaystyle \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 $\displaystyle \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 $\displaystyle n-1$ partition points and $\displaystyle n$ partition segments, all the partition segments are smaller than $\displaystyle 1/n$.

The first terms of the constructed sequence will be $\displaystyle a_1=\ln \frac{3}{2}, a_2=\ln \frac{5}{4}, a_3=\ln \frac{7}{4}, a_4=\ln \frac{9}{8},\dots$.

Solution 2. Idea of another proof of $\displaystyle d^*\ge \ln 2$. We show that $\displaystyle d_n=\frac1n+\dots+\frac1{2n-2}$ is good for $\displaystyle n=2^k$, $\displaystyle k\in \N$. Since $\displaystyle d_n\nearrow \ln 2$, this will imply $\displaystyle d^*\ge \ln 2$.

1st step: We show (by backward induction) that an initial setting with $\displaystyle n-1$ intervals of lengths $\displaystyle \frac1n$, ..., $\displaystyle \frac1{2n-2}$ (splitted by $\displaystyle n-2$ points $\displaystyle a_1$, ..., $\displaystyle a_{n-2}$) can be constructed. These intervals are all shorter than $\displaystyle \frac1{n-2}$. We remove points and join pairs of neighboring intervals and show that the intervals are still short enough.

2nd step: We show by forward induction that the initial intervals can be further partitioned. In each step, we have intervals with lengths $\displaystyle \le \frac1k$, ..., $\displaystyle \le \frac1{2k-2}$. We divide the first one into two intervals with lengths $\displaystyle \le \frac1{2k-1}$, $\displaystyle \le \frac1{2k}$. This is possible since $\displaystyle \frac1{2k-1}+\frac1{2k}\ge \frac1{k}$. Thus we obtain intervals with lenths $\displaystyle \le \frac1{k+1}$, ..., $\displaystyle \le \frac1{2k}$ and we can continue by induction.