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.