HMMT 十一月 2018 · 团队赛 · 第 2 题

HMMT November 2018 — Team Round — Problem 2

[ 20 ] 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?

解析

[ 20 ] 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? Proposed by: Dhruv Rohatgi 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 scores needs to be large enough that the many additions to 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.