uniolympiads Ελληνικά

IMC 2021, Day 1, Problem 3

We say that a positive real number dd is good if there exists an infinite sequence a1,a2,a3,⋯∈(0,d)a_1, a_2, a_3, \dots \in (0, d) such that for each nn, the points a1,…,ana_1, \dots, a_n partition the interval [0,d][0, d] into segments of length at most 1/n1/n each. Find

sup⁡{d∣d is good}.\sup\big\{d \mid d \text{ is good}\big\}.
Original from the official PDFWe say that a positive real number d is good if there exists an infinite sequence a 1 , a 2 , a 3 , . . . ∈ (0, d) such that for each n, the points a 1 , . . . , a n partition the interval [0, d] into segments of length at most 1/n each. Find sup {d ∣ d is good}.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Josef Tkadlec)

Hint: To get an upper bound, use that some of the gaps after nn steps are still intact some steps later.

Solution. Let d⋆=sup⁡{d∣d is good}d^\star = \sup\{d \mid d \text{ is good}\}. We will show that d⋆=ln⁡(2)≐0.693d^\star = \ln(2) \doteq 0.693.

  1. d⋆≤ln⁡2d^\star \le \ln 2:

    Assume that some dd is good and let a1,a2,…a_1, a_2, \ldots be the witness sequence.

    Fix an integer nn. By assumption, the prefix a1,…,ana_1, \ldots, a_n of the sequence splits the interval [0,d][0, d] into n+1n+1 parts, each of length at most 1/n1/n.

    Let 0≤ℓ1≤ℓ2≤⋯≤ℓn+10 \le \ell_1 \le \ell_2 \le \cdots \le \ell_{n+1} be the lengths of these parts. Now for each k=1,…,nk = 1, \ldots, n after placing the next kk terms an+1,…,an+ka_{n+1}, \ldots, a_{n+k}, at least n+1−kn+1-k of these initial parts remain intact. Hence ℓn+1−k≤1n+k\ell_{n+1-k} \le \frac{1}{n+k}. Hence

    d=ℓ1+⋯+ℓn+1≤1n+1n+1+⋯+12n.(2)d = \ell_1 + \cdots + \ell_{n+1} \le \frac{1}{n} + \frac{1}{n+1} + \cdots + \frac{1}{2n}. \tag{2}
    As n→∞n \to \infty, the RHS tends to ln⁡(2)\ln(2) showing that d≤ln⁡(2)d \le \ln(2).

    Hence d⋆≤ln⁡2d^\star \le \ln 2 as desired.

  2. d⋆≥ln⁡2d^\star \ge \ln 2:

    Observe that

    ln⁡2=ln⁡2n−ln⁡n=∑i=1nln⁡(n+i)−ln⁡(n+i−1)=∑i=1nln⁡(1+1n+i−1).\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 [0,ln⁡2][0, \ln 2] in nn parts. Moreover, the maximal length of the parts is ln⁡(1+1/n)<1/n\ln(1 + 1/n) < 1/n.

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

    ln⁡(1+12n)+ln⁡(1+12n+1)=ln⁡(1+1n).\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 ln⁡(1+1/n)\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 n−1n-1 partition points and nn partition segments, all the partition segments are smaller than 1/n1/n.

    The first terms of the constructed sequence will be a1=ln⁡32,a2=ln⁡54,a3=ln⁡74,a4=ln⁡98,…a_1 = \ln\frac{3}{2}, a_2 = \ln\frac{5}{4}, a_3 = \ln\frac{7}{4}, a_4 = \ln\frac{9}{8}, \ldots.

Remark. This remark describes in fact the same solution from a different view and some ideas behind it. It could be erased after marking is finished. Estimate (2) is quite natural. To prove that RHS tends to ln⁡2\ln 2 we use some integral estimates by

∫n2n+11xdx=ln⁡(2n+1)−ln⁡n.\int_n^{2n+1} \frac{1}{x}dx = \ln(2n+1) - \ln n.
Here we can observe that
∫n2n1xdx=ln⁡2\int_n^{2n} \frac{1}{x}dx = \ln 2
is independent of nn. This can help us with the construction since the above equality means
I1=∫nn+11xdx=∫2n2n+11xdx+∫2n+12n+21xdx=I2+I3,I_1 = \int_n^{n+1} \frac{1}{x}dx = \int_{2n}^{2n+1} \frac{1}{x}dx + \int_{2n+1}^{2n+2} \frac{1}{x}dx = I_2 + I_3,
so, interval of length I1I_1 can be splitted into two intervals of lengths I2I_2 and I3I_3. In fact, after placing the point ana_n in the construction for d=ln⁡2d = \ln 2, the lengths of the n+1n+1 intervals are
∫n+1n+21x, ∫n+2n+31x, …, ∫2n+12n+21x\int_{n+1}^{n+2} \frac{1}{x},\ \int_{n+2}^{n+3} \frac{1}{x},\ \ldots,\ \int_{2n+1}^{2n+2} \frac{1}{x}
with total length
d=∫n+12n+21x=ln⁡2.d = \int_{n+1}^{2n+2} \frac{1}{x} = \ln 2.

Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?