52nd Putnam 1991

Problem B1

For positive integers n define d(n) = n - m2, where m is the greatest integer with m2 ≤ n. Given a positive integer b0, define a sequence bi by taking bk+1 = bk + d(bk). For what b0 do we have bi constant for sufficiently large i?




Answer: the squares.

If bk is a square, then d(bk) = 0, so bk+1 = bk and the sequence is constant from that point on.

If bk is not a square, then for some m it lies between m2 and (m + 1)2, so we can write it as m2 + r, where 1 ≤ r ≤ 2m. So bk+1 = m2 + 2r. But m2 < bk+1 < (m + 2)2 and bk+1 ≠ (m + 1)2, so bk+1 is not a square (and is > bk).



52nd Putnam 1991

© John Scholes
21 Sep 1999