2001 AIME II Problem 1

Question

Let

N

be the largest positive integer with the following property: reading from left to right, each pair of consecutive digits of

N

forms a perfect square. What are the leftmost three digits of

N?

Answer

Each adjacent digit pair must be one of the two-digit perfect squares

16,

25,

36,

49,

64,

81

Every digit has at most one possible next digit, so trace the chains and take the longest one

Each pair of consecutive digits must be one of the two-digit squares

16,

25,

36,

49,

64,

81.

So each digit determines its successor uniquely if one exists:

1 \to 6,

2 \to 5,

3 \to 6,

4 \to 9,

6 \to 4,

8 \to 1,

while

5

and

9

end the number.

Following these chains from each possible starting digit, the longest strings are

25,

3649,

and

81649.

The five-digit chain

8 \to 1 \to 6 \to 4 \to 9

beats everything else, so

N = 81649,

whose leftmost three digits are

816.

Problem 1 in other years