International Mathematics Competition
for University Students

Select Year:

IMC 2021
  Problems & Solutions

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\):
  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.

  3. \(\displaystyle d^\star\ge \ln 2\):
  4. 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.