Maths Olympiad Prep

Library / /2 of 43

Algebra Difficulty 7.2 National olympiad, round 2 Find the answer

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}, \ldots \in(0, d) such that for each nn, the points a1,,ana_{1}, \ldots, a_{n} partition the interval [0,d][0, d] into segments of length at most 1/n1 / n each. Find sup{dd is good }\sup \{d \mid d \text { is good }\}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let d=sup{ddd^{\star}=\sup \{d \mid d is good }\}. We will show that d=ln(2)0.693d^{\star}=\ln (2) \doteq 0.693. 1. dln2:d^{\star} \leq \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 012n+10 \leq \ell_{1} \leq \ell_{2} \leq \cdots \leq \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+1kn+1-k of these initial parts remain intact. Hence n+1k1n+k\ell_{n+1-k} \leq \frac{1}{n+k}. Hence d=1++n+11n+1n+1++12n\begin{equation*} d=\ell_{1}+\cdots+\ell_{n+1} \leq \frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{2 n} \tag{2} \end{equation*} As nn \rightarrow \infty, the RHS tends to ln(2)\ln (2) showing that dln(2)d \leq \ln (2). Hence dln2d^{\star} \leq \ln 2 as desired. 2. dln2d^{\star} \geq \ln 2 : Observe that ln2=ln2nlnn=i=1nln(n+i)ln(n+i1)=i=1nln(1+1n+i1)\ln 2=\ln 2 n-\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,ln2][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}{2 n}\right)+\ln \left(1+\frac{1}{2 n+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 n1n-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=ln32,a2=ln54,a3=ln74,a4=ln98,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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.