Bernardo and Silvia play the following game. An integer between 0 and 999, inclusive, is selected and given to Bernardo. Whenever Bernardo receives a number, he doubles it and passes the result to Silvia. Whenever Silvia receives a number, she adds 50 to it and passes the result to Bernardo. The winner is the last person who produces a number less than 1000. Let be the smallest initial number that results in a win for Bernardo. What is the sum of the digits of ?
- A)
- B)
- C)
- D)
- E)
Answer
A
Key insight
Silvia only adds 50, so Bernardo wins exactly when he hands her a number from 950 to 999. Find the smallest start that lands there.
Solution
- Try a small start to see how the game goes. With : Bernardo makes , Silvia , Bernardo , Silvia , Bernardo , Silvia , Bernardo , Silvia , Bernardo . Bernardo went over first, so Silvia made the last number under and she wins.
- Who wins depends on who first goes over . Bernardo wins when Silvia is the one who goes over. Silvia adds only , so this happens when Bernardo hands her a number from to .
- Write every number in terms of . Bernardo doubles, Silvia adds :
| Turn | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Bernardo makes | ||||
| Silvia makes |
(Bernardo's fifth number would be , which is already over , so the game is always decided by then.)
4. For any starting , Bernardo's fourth number is his biggest, so it is the one that can reach with the smallest . Start there. Need :
- means , so , that is ;
- means , so .
So all win this way.
5. Could an earlier turn give a smaller ? For we need , and the first two turns need even bigger . So nothing smaller than works.
6. Check : Bernardo , Silvia , Bernardo , Silvia , Bernardo , Silvia , Bernardo , Silvia . Silvia went over, so Bernardo's was the last number under . Bernardo wins.
7. The digit sum of is .
The answer is .
Why this works
A process that repeats "double, then add" turns into a simple expression in the starting number after each round, so the whole game fits in one table. The winning condition becomes a window: Bernardo must land just below , close enough that Silvia's pushes her over. Turning "who wins" into an inequality is the key step.
The trap
Finding that N = 16, 17, 18 all win and giving the digit sum of the wrong one, or forgetting that Silvia's number must reach 1000 or more for Bernardo to win.
Concise solution
Write out the numbers produced, starting from :
| Bernardo | |||||
|---|---|---|---|---|---|
| Silvia |
The outputs increase, and the game ends at the first output of or more. Bernardo wins when that first big output is Silvia's, which happens exactly when some Bernardo output satisfies , i.e. . (Bernardo's own output is always at least , so the game never continues past Silvia's fourth turn.)
Test each Bernardo output for the smallest :
- , and . So work.
- needs ; the earlier outputs need even larger .
The smallest winning is : Bernardo produces and Silvia then produces . The digit sum of is .
The answer is .
Review in the AoPS books
- Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
- Introduction to Algebra, Chapter 20: Special Functions (§20.2, §20.5)
- Prealgebra, Chapter 15: Problem-Solving Strategies (§15.4)
- Introduction to Algebra, Chapter 15: More Inequalities (§15.1, §15.3, §15.4)
Techniques
Bound the quantity above/below or estimate to pin it down · Start from the end state / desired conclusion and reverse