HMMT 十一月 2018 · 冲刺赛 · 第 15 题
HMMT November 2018 — Guts Round — Problem 15
题目详情
英文原题
- [ 9 ] 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 waspressed. c doesn’t change the number of a ’s on screen. Determine the fewest number of keystrokesrequired to attain at least 2018 a ’s on screen. ( Note : pressing p before the first press of c doesnothing).
HMMT November 2018, November 10, 2018 — GUTS ROUND
Organization Team Team ID#
解析
英文解析
- [ 9 ] 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 waspressed. c doesn’t change the number of a ’s on screen. Determine the fewest number of keystrokesrequired to attain at least 2018 a ’s on screen. ( Note : pressing p before the first press of c doesnothing).
Proposed by: John Michael Wu
Answer: 21
The first keystroke must be c and the last keystroke must be p . If there are k c ’s pressed in total, letn 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 isiks := n xii =1
and the total number of a ’s iskr := n yii =1
We desire to minimize s with the constraint that r 2018. We claim that the minimum possible s iss = 21.
This value of s is achieved by k = 7 and n = n = n = n = n = n = n = 3, so it remains to
1 2 3 4 5 6 7
show that s = 20 is not possible.
Suppose it were for some k and n . By the AM-GM inequality,
✓ ◆ipn + n + · · · + n
1 2 kkn n · · · n
1 2 kkimplying that
2018 n n · · · n
1 2 k
✓ ◆
n + n + · · · + nk
1 2 k
✓ ◆kk =20
1 kxwhich is satisfied by no positive integers k . More rigorously, the function f ( x ) = x is well known tohave a maximum at x = e . Making the substitution u = , we obtain 20
✓ ◆kk
20 20 = uuk
⇣ ⌘
u 120 = ue 20
which is maximized by setting u = e . However, e ⇡ 1568 . 05, meaning that s = 20 is not possible.