| |||||||||||||

## IMC2021: Day 1, Problem 3
\(\displaystyle \sup\Big\{d\ \big|\ d \text{ is good}\Big\}. \) Josef Tkadlec
- \(\displaystyle d^\star\le \ln 2\):
- \(\displaystyle d^\star\ge \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
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. 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\).
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. | |||||||||||||

© IMC |