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 was pressed. c doesn’t change the number of a ’s on screen. Determine the fewest number of keystrokes required to attain at least 2018 a ’s on screen. ( Note : pressing p before the first press of c does nothing). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 was pressed. c doesn’t change the number of a ’s on screen. Determine the fewest number of keystrokes required to attain at least 2018 a ’s on screen. ( Note : pressing p before the first press of c does nothing). 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, let n denote one more than the number of p ’s pressed immediately following the i ’th c , for 1 i k . i Then, we have that the total number of keystrokes is k X s := n i i =1 and the total number of a ’s is k Y r := n i i =1 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 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, i ✓ ◆ p n + n + · · · + n 1 2 k k n n · · · n 1 2 k k implying that 2018 n n · · · n 1 2 k ✓ ◆ k n + n + · · · + n 1 2 k k ✓ ◆ k 20 = k 1 x which is satisfied by no positive integers k . More rigorously, the function f ( x ) = x is well known to 20 have a maximum at x = e . Making the substitution u = , we obtain k ✓ ◆ k 20 20 u = u k ⇣ ⌘ 20 1 u = u 20 e which is maximized by setting u = e . However, e ⇡ 1568 . 05, meaning that s = 20 is not possible.