返回题库

HMMT 二月 2018 · 冲刺赛 · 第 28 题

HMMT February 2018 — Guts Round — Problem 28

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

题目详情

英文原题

  1. [ 15 ] Arnold and Kevin are playing a game in which Kevin picks an integer 1 ≤ m ≤ 1001, and Arnoldis trying to guess it. On each turn, Arnold first pays Kevin 1 dollar in order to guess a number k of
    Arnold’s choice. If m ≥ k , the game ends and he pays Kevin an additional m − k dollars (possiblyzero). Otherwise, Arnold pays Kevin an additional 10 dollars and continues guessing.
    Which number should Arnold guess first to ensure that his worst-case payment is minimized?
    HMMT February 2018, February 10, 2018 — GUTS ROUND
    Organization Team Team ID#
解析

英文解析

  1. [ 15 ] Arnold and Kevin are playing a game in which Kevin picks an integer 1 ≤ m ≤ 1001, and Arnoldis trying to guess it. On each turn, Arnold first pays Kevin 1 dollar in order to guess a number k of
    Arnold’s choice. If m ≥ k , the game ends and he pays Kevin an additional m − k dollars (possiblyzero). Otherwise, Arnold pays Kevin an additional 10 dollars and continues guessing.
    Which number should Arnold guess first to ensure that his worst-case payment is minimized?
    Proposed by:
    Answer: 859
    We let f ( n ) denote the smallest amount we can guarantee to pay at most if Arnold’s first choice is n .
    For each k < n , if Arnold’s first choice is k + 1, in both worst case scenarios, he could end up payingeither n − k or 11 + f ( k ). It is then clear that f ( n ) = min max { n − k, 11 + f ( k ) } .
    k +1 <n
    Now clearly f ( k ) is a non-decreasing function of k , and n − k is a strictly decreasing function of k .
    Therefore if there exists k such that n − k = 11 + f ( k ), we have f ( n ) = n − k = 11 + f ( k ) with pickingk + 1 as an optimal play (and picking K + 1 also optimal iff K ≥ k and f ( K ) = f ( k ).
    Now note that f ( k ) = k for k ≤ 12 (but f (13) = 12 though it’s not relevant to the solution). Leta = 11. Now recursively define a such that a − a = 11 + f ( a ). Thus f ( a ) = a − a with
    1 i i i − 1 i − 1 i i i − 1
    the optimal move to pick a + 1.
    i − 1
    a = 11
    a − 11 = 11 + 11 : a = 33 , f ( a ) = 221
    2 2 2
    a − 33 = 11 + f (33) : a = 66 , f ( a ) = 33
    3 3 3
    14 × 13
    It is clear by induction that a is 11 times the i th triangular number. 1001 is 11 × 91 = , so thei
    12 × 132
    optimal strategy is to pick 1 more than 11 × = 858. So the answer is 859. 2