# International Mathematics Competition for University Students 2021

Select Year:

IMC 2021
 Information Schedule Problems & Solutions Results Contact

## 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\}.$

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. IMC1994 IMC1995 IMC1996 IMC1997 IMC1998 IMC1999 IMC2000 IMC2001 IMC2002 IMC2003 IMC2004 IMC2005 IMC2006 IMC2007 IMC2008 IMC2009 IMC2010 IMC2011 IMC2012 IMC2013 IMC2014 IMC2015 IMC2016 IMC2017 IMC2018 IMC2019 IMC2020 IMC 2021 