HaCkEd By KaSpEr511

Spiraling Numbers (MMM #36)

July 18th, 2009

Here is the MMM#36 problem from wildaboutmath.com:

Imagine arranging the positive integers in a spiral pattern.
The numbers from 1 to 16 look like this in the spiral pattern.

10  9  8  7
11  2  1  6
12  3  4  5
13 14 15 16

The location of each number corresponds to an X,Y Cartesian coordinate where the number 1 is at the origin: (0,0).
2 is at (-1,0). 3 is at (-1,-1). 4 is at (0,-1). 5 is at (1,-1). 6 is at (1,0). 7 is at (1,1) and so on.

What is the X,Y coordinate of the number 1,000,000?

Solution

We will prove by induction that the number $4n^2$ is on the bottom-right corner of the $2n\times 2n$ square and the coordinate of this number is $(n-1,-n)$ .

For n=1 the statement is obvious
2 1
3 4

As we can see the number $(2\cdot 1)^2=4$ is on the bottom-right corner of the $2\times 2$ square and the its coordinate is $(0,-1)$ .

Assume the statement is true for $n$

For $n+1$ , look at the following picture

spiral2

By induction hypothesis , the bottom-right corner of the inner square which is the $2n\times 2n$ square is $4n^2$ . The next number will spiraling along the indicated arrow. Now to fill in the outer square, i.e., the $(2n+2)\times (2n+2)$ square we need to use numbers to fill in the gray area and four of the red corners. So we need $4(2n)+4$ numbers to fill in the bigger square. But notice that $4n^2+4(2n)+4=4(n^2+2n+1)=4(n+1)^2$ . Therefore the number $4(n+1)^2$ is on the bottom-right corner of the $(2n+2)\times (2n+2)$ square. Since the coordinate of $4n^2$ is $(n-1,-n)$ (by induction hypothesis), then clearly the coordinate of $4(n+1)^2$ is $(n,-n-1)$ .