Question

Let $S_i$ be the set of all integers $n$ such that $100i \le n \lt 100(i + 1).$ For example, $S_4$ is the set $\{400, 401, 402, \ldots, 499\}.$ How many of the sets $S_0, S_1, S_2, \ldots, S_{999}$ do not contain a perfect square?

答案

Solution:

Consecutive squares $a^2$ and $(a + 1)^2$ differ by $2a + 1 \le 99$ for $a \le 49,$ so the squares from $1^2$ to $50^2 = 2500$ never skip a hundred-block: every set $S_0, S_1, \ldots, S_{25}$ contains a perfect square. For $a \ge 50$ the gap $2a + 1 \ge 101$ exceeds $100,$ so each of the sets $S_{26}, \ldots, S_{999}$ contains at most one square.

The largest number involved is $99999,$ and $316^2 = 99856 \le 99999 \lt 317^2.$ So the squares landing in $S_{26}, \ldots, S_{999}$ are $51^2, 52^2, \ldots, 316^2$ — that is, $266$ squares occupying $266$ distinct sets out of those $974.$

Therefore $974 - 266 = 708$ sets contain no perfect square.

2008 AIME I Problem 7

Solution:

Problem 7 in Other Years