AlgebraDifficulty 5.9AIME, harderProve itUnited States
Problem:
On a computer screen is the single character a. The computer has two keys: c (copy) and p (paste), which may be pressed in any sequence.
Pressing p increases the number of a's on screen by the number that were there the last time c was pressed. c doesn't change the number of a's on screen. Determine the fewest number of keystrokes required to attain at least 2018a's on screen. (Note: pressing p before the first press of c does nothing).
Solution
Solution:
The first keystroke must be c and the last keystroke must be p. If there are kc's pressed in total, let ni denote one more than the number of p's pressed immediately following the i'th c, for 1≤i≤k.
Then, we have that the total number of keystrokes is s:=i=1∑kni and the total number of a's is r:=i=1∏kni We desire to minimize s with the constraint that r≥2018. We claim that the minimum possible s is s=21.
This value of s is achieved by k=7 and n1=n2=n3=n4=n5=n6=n7=3, so it remains to show that s=20 is not possible.
Suppose it were for some k and ni. By the AM-GM inequality, (kn1+n2+⋯+nk)≥kn1n2⋯nk implying that 2018≤n1n2⋯nk≤(kn1+n2+⋯+nk)k=(k20)k which is satisfied by no positive integers k. More rigorously, the function f(x)=xx1 is well known to have a maximum at x=e. Making the substitution u=k20, we obtain (k20)k=uu20=(uu1)20 which is maximized by setting u=e. However, ee20≈1568.05, meaning that s=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.