Maths Olympiad Prep

Library / /719 of 740

, 2018

Algebra Difficulty 5.9 AIME, harder Prove it United States

Problem:

On a computer screen is the single character aa. The computer has two keys: cc (copy) and pp (paste), which may be pressed in any sequence.

Pressing pp increases the number of aa's on screen by the number that were there the last time cc was pressed. cc doesn't change the number of aa's on screen. Determine the fewest number of keystrokes required to attain at least 20182018 aa's on screen. (Note: pressing pp before the first press of cc does nothing).

Solution

Solution:

The first keystroke must be cc and the last keystroke must be pp. If there are kk cc's pressed in total, let nin_{i} denote one more than the number of pp's pressed immediately following the ii'th cc, for 1ik1 \leq i \leq k.

Then, we have that the total number of keystrokes is
s:=i=1kni s := \sum_{i=1}^{k} n_{i}
and the total number of aa's is
r:=i=1kni r := \prod_{i=1}^{k} n_{i}
We desire to minimize ss with the constraint that r2018r \geq 2018. We claim that the minimum possible ss is s=21s=21.

This value of ss is achieved by k=7k=7 and n1=n2=n3=n4=n5=n6=n7=3n_{1}=n_{2}=n_{3}=n_{4}=n_{5}=n_{6}=n_{7}=3, so it remains to show that s=20s=20 is not possible.

Suppose it were for some kk and nin_{i}. By the AM-GM inequality,
(n1+n2++nkk)n1n2nkk \left(\frac{n_{1}+n_{2}+\cdots+n_{k}}{k}\right) \geq \sqrt[k]{n_{1} n_{2} \cdots n_{k}}
implying that
2018n1n2nk(n1+n2++nkk)k=(20k)k \begin{aligned} 2018 & \leq n_{1} n_{2} \cdots n_{k} \\ & \leq \left(\frac{n_{1}+n_{2}+\cdots+n_{k}}{k}\right)^{k} \\ & = \left(\frac{20}{k}\right)^{k} \end{aligned}
which is satisfied by no positive integers kk. More rigorously, the function f(x)=x1xf(x)=x^{\frac{1}{x}} is well known to have a maximum at x=ex=e. Making the substitution u=20ku=\frac{20}{k}, we obtain
(20k)k=u20u=(u1u)20 \begin{aligned} \left(\frac{20}{k}\right)^{k} & = u^{\frac{20}{u}} \\ & = \left(u^{\frac{1}{u}}\right)^{20} \end{aligned}
which is maximized by setting u=eu=e. However, e20e1568.05e^{\frac{20}{e}} \approx 1568.05, meaning that s=20s=20 is not possible.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.