PUMaC 2012 · 团队赛 · 第 6 题

PUMaC 2012 — Team Round — Problem 6

(3 digits) Bob is punished by his math teacher and has to write all perfect squares, one after another. His teacher’s blackboard has space for exactly 2012 digits. He can stop when he cannot fit the next perfect square on the board. (At the end, there might be some space left 2 on the board - he does not write only part of the next perfect square.) If n is the largest perfect square he writes, what is n ?

解析

Problem: (3 digits) Bob is punished by his math teacher and has to write all perfect squares, one after another. His teacher’s blackboard has space for exactly 2012 digits. He can stop when he cannot fit the next perfect square on the board. (At the end, there might be some 2 space left on the board - he does not write only part of the next perfect square.) If n is the largest perfect square he writes, what is n ? Answer: 411 2 Solution: Since a positive integer k has exactly 1 + b log k c digits, we want to find the 10 largest integer n such that n ∑ ( ) 2 1 + b log k c ≤ 2012 10 k =1 √ Using the approximation 10 ≈ 3 . 16228 · · · , we have   1 , if k = 1 , 2 , 3     2 , if k = 4 , 5 , 6 , 7 , 8 , 9     3 , if k = 10 , 11 , . . . , 31 2 1 + b log k c = 10  4 , if k = 32 , 33 , . . . , 99      5 , if k = 100 , 101 , . . . , 316    6 , if k = 317 , 318 , . . . , 999 2 By the time Bob finishes writing 316 on the blackboard, the number of digits he will have written down will be 1 · 3 + 2 · 6 + 3 · 22 + 4 · 68 + 5 · 217 = 1438 2012 − 1438 2 2 The numbers 317 , . . . , 999 all have 6 digits, so he will have space for b c = 95 more 6 2 numbers. The last square he writes is then 411 . Author: Alan