返回题库

HMMT 十一月 2018 · 冲刺赛 · 第 15 题

HMMT November 2018 — Guts Round — Problem 15

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 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#
解析

英文解析

  1. [ 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.