Problem:
Let Si​ be the set of all integers n such that 100i≤n<100(i+1). For example, S4​ is the set {400,401,402,…,499}. How many of the sets S0​,S1​,S2​,…,S999​ do not contain a perfect square?
Solution:
Note that 12=1∈S0​. All sets Si​ contain a perfect square unless i is so large that, for some integer a,a2∈Sj​ with j<i, and (a+1)2∈Sk​ with k>i. This implies that (a+1)2−a2>100, and hence a≥50. But 502=2500, which is a member of S25​, so all sets S0​,S1​,S2​,…,S25​ contain at least one perfect square. Furthermore, for all i>25, each set Si​ which contains a perfect square can only contain one such square. The largest value in any of the given set is 99999, and 3162<99999<3172. Disregarding the first 50 squares dealt with above, there are 316−50=266 perfect squares, each the sole perfect square member of one of the 974 sets S26​,S27​,S28​,…,S999​. Thus there are 974−266 sets without a perfect square, and the answer is 708​.
The problems on this page are the property of the MAA's American Mathematics Competitions