HMMT 二月 2018 · 冲刺赛 · 第 28 题
HMMT February 2018 — Guts Round — Problem 28
题目详情
英文原题
- [ 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#
解析
英文解析
- [ 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