HMMT 二月 2008 · 冲刺赛 · 第 25 题

HMMT February 2008 — Guts Round — Problem 25

[ 12 ] Alice and the Cheshire Cat play a game. At each step, Alice either (1) gives the cat a penny, which causes the cat to change the number of (magic) beans that Alice has from n to 5 n or (2) gives the cat a nickel, which causes the cat to give Alice another bean. Alice wins (and the cat disappears) as soon as the number of beans Alice has is greater than 2008 and has last two digits 42. What is the minimum number of cents Alice can spend to win the game, assuming she starts with 0 beans?

解析

[ 12 ] Alice and the Cheshire Cat play a game. At each step, Alice either (1) gives the cat a penny, which causes the cat to change the number of (magic) beans that Alice has from n to 5 n or (2) gives the cat a nickel, which causes the cat to give Alice another bean. Alice wins (and the cat disappears) as soon as the number of beans Alice has is greater than 2008 and has last two digits 42. What is the minimum number of cents Alice can spend to win the game, assuming she starts with 0 beans? Answer: 35 Consider the number of beans Alice has in base 5. Note that 2008 = 31013 , 42 = 132 , 5 5 and 100 = 400 . Now, suppose Alice has d · · · d d beans when she wins; the conditions for winning 5 k 2 1 mean that these digits must satisfy d d = 32, d · · · d ≥ 310, and d · · · d = 4 i + 1 for some i . To 2 1 k 3 k 3 gain these d · · · d d beans, Alice must spend at least 5( d + d + · · · + d ) + k − 1 cents (5 cents k 2 1 1 2 k to get each bean in the “units digit” and k − 1 cents to promote all the beans). We now must have k ≥ 5 because d · · · d d > 2008. If k = 5, then d ≥ 3 since d · · · d ≥ 3100; otherwise, we have k 2 1 k k 3 d ≥ 1. Therefore, if k = 5, we have 5( d + d + · · · + d ) + k − 1 ≥ 44 > 36; if k > 5, we have k 1 2 k 5( d + d + · · · + d ) + k − 1 ≥ 30 + k − 1 ≥ 35. But we can attain 36 cents by taking d · · · d = 1000, 1 2 k k 3 so this is indeed the minimum.