Library / /607 of 740

, 2018

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

Alice starts with the number $0$ . She can apply $100$ operations on her number. In each operation, she can either add $1$ to her number, or square her number. After applying all operations, her score is the minimum distance from her number to any perfect square. What is the maximum score she can attain?

Solution

Solution:

Answer: $94$

Note that after applying the squaring operation, Alice's number will be a perfect square, so she can maximize her score by having a large number of adding operations at the end. However, her score needs to be large enough that the many additions do not bring her close to a larger square. Hence the strategy is as follows: $2$ additions to get to $2$ , $4$ consecutive squares to get to $65536$ , and $94$ more additions for a score of $94$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.