Takeaway squares

Today I worked through the final five problems from the 2010 AMC10 Paper A, an American Maths Challenge. It was the very last problem that turned out to be my favourite:

Jim starts with a positive integer n and creates a sequence of numbers. Each successive number is obtained by subtracting the largest possible integer square less than or equal to the current number, until zero is reached. For example, if Jim starts with n = 55, then his sequence contains five numbers: 55, 6, 2, 1, 0.

What is the smallest value of n for which his sequence contains eight numbers?

__________

Let f(n) be the number of terms in the sequence beginning with n. For example, the sequence beginning with 21 goes: 21, 5, 1, 0. This has 4 terms, so f(21) = 4.

Notice that this sequence tells us a lot more than just the value of f(21). It also tells us that f(5) = 3, f(1) = 2 and f(0) = 1.

Perhaps it’s easier to work backwards from the end of the sequence. We know that the last term is 0. What could come before it? That’s easy – any square number!

But what could come before, say, 27? We must have subtracted a square number to end up with 27, so the term before 27 is of the form 27 + k^2. But is any value of k possible?

Well, if k = 5, then 27 + k^2 = 52. But this doesn’t work: the term 52 must be followed by 3 (we have to subtract 49), and not 27. So which values of k are allowed?

Now we remind ourselves of how the sequence is formed. To get from one term to the next, we subtract the largest possible square. So if the number 27 + k^2 is followed by 27, then k^2 must be the largest square less than 27 + k^2. In particular, (k+1)^2 must be greater than 27 + k^2. Solving

(k+1)^2 > 27 + k^2

yields k > 13. Let’s test this: if k = 14, then 27 + k^2 = 223. This works, since in a sequence, 223 must be followed by 27: 196 is the biggest square less than or equal to 223.

Following the same reasoning as above, in general we obtain that a term r may be preceded by a term r + k^2 for any k greater than \frac{r-1}{2}.   (*)

This gives us a way of quickly finding an eight-term sequence. We work backwards from 0, continually adding squares that satisfy the condition above. If we do this so that we write down the smallest possible number at every stage, we end up with:

0, 1, 2, 3, 7, 23, 167, 7223.

We have now found a value of n such that f(n) = 8, namely n = 7223.

But how can we be sure that 7223 is the smallest such value of n?  We picked the smallest possible term at every stage in the above sequence, but unfortunately this alone is not enough to prove that 7223 is the best we can do overall. Is it not possible that by starting 0, 4, … we actually end up with a number smaller than 7223 in the 8th position?

A little thought puts our mind at ease. When working backwards, we continually add squares to get from one term to the next. The condition (*) above means that in some sense, the bigger the term, the bigger the square we add must be (for example, from the term 10, the smallest square we can add is 25, but from the term 14, the smallest square we can add is 49).

So if, working backwards from 0, we pick a number bigger than 1 (like 4 or 9) for our second term, then the square we add to the second term to obtain the third term must be at least 1, so that the third term is greater than 2.

Similarly, the fourth term must be greater than 3, the fifth term must be greater than 7, the sixth term greater than 23, the seventh greater than 167, and finally the eighth term must be greater than 7223.

In fact, if we deviate from the sequence given at any point, we will always end up with a term greater than 7223 in the eighth position.

Thus, the answer to the problem is \boxed{7223}.

I love this problem. The setup is easy to understand, and the mathematics required to solve it is minimal, but a successful method is far from obvious. Finally, the answer is surprisingly large, and completely unguessable (if that’s a real word).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s