HaCkEd By KaSpEr511

First Part Of MMM#37

July 24th, 2009

Here is MMM#37 problem:

Based on the introduction to spiral numbers presented in MMM #36, solve one (or both) of these problems:

Come up with an algorithm that tells what number is at an arbitrary X, Y coordinate.

Come up with an algorithm that tells the X, Y coordinates for an arbitrary positive integer.

Solution (1st Part)

Note that the plane can be partitioned into nested square $S_0,S_1,S_2,\cdots$ like this

nested

where $S_n$ is the $(2n+1)\times (2n+1)$ square. We claim that the top left corner of $S_n$ is the number $(2n+1)^2$ and its coordinate is $(-n,n)$ . The proof is similar to the solution of MMM#36 here. As we can see from the picture above, this claim is true for $n=0,1$ . Suppose the statement is true for $n-1$ . To prove for $n$ look at the following picture:

nested2

Suppose $S_{n-1}$ is the orang square and $S_n$ is the green one. By induction hypothesis $B'=\left(2(n-1)+1\right)^2=(2n-1)^2$ and the coordinate of $B'$ is $(-n+1,n-1)$ . As we can see from the picture $B=B'+4(2n)=(2n-1)^2+8n=4n^2+4n+1=(2n+1)^2$ and the coordinate of $B$ is clearly $(-n,n)$ (since the coordinate of $B'$ is $(-n+1,n-1)$ ).

Since $(0,0)$ is the center of $S_n$ , then by symmetry the coordinate of $A,C,D$ are $(n,n),(-n,-n),(n,-n)$ respectively. Also

$\begin{align*}A&=B-2n=(2n+1)^2-2n\\ D&=A-2n=(2n+1)^2-4n\\ C&=D-2n=(2n+1)^2-6n\end{align*}$ .

Let $(a,b)$ be an integer coordinate. Then $(a,b)$ belong to $S_n$ for some $n$ . Then $(a,b)$ can be on top, left, bottom or right of $S_n$ as we can see from this picture nested3 Note for any position of $(a,b)$ in $S_n$ we have $|a|=n$ or $|b|=n$ . Hence $n=\max\{|a|,|b|\}$ .

If $(a,b)$ is on the top, then $b=n$ and $(a,b)$ is the coordinate of $B-(a+n)=(2n+1)^2-(a+n)=4n^2+3n+1-a$ .
If $(a,b)$ is on the left, then $a=-n$ and $(a,b)$ is the coordinate of $C-(b+n)=(2n+1)^2-6n-(b+n)=4n^2-3n+1-b$ .
If $(a,b)$ is on the bottom, then $b=-n$ and $(a,b)$ is the coordinate of $C+(a+n)=(2n+1)^2-6n+a+n=4n^2-n+1+a$ .
If $(a,b)$ is on the right, then $a=n$ and $(a,b)$ is the coordinate of $D+(b+n)=(2n+1)^2-4n+b+n=4n^2+n+1+b$ .

Hence the algorithm to know what number corresponds to $(a,b)$ is the following:

Compute $n=\max\{|a|,|b|\}$ .
Then $(a,b)$ is the coordinate of $\begin{cases}4n^2+3n+1-a&\text{ if } n=b\\4n^2-3n+1-b&\text{ if } n=-a\\4n^2-n+1+a&\text{ if } n=-b\\4n^2+n+1+b&\text{ if }n=a \end{cases}$

Categories: Math Monday Madness

Tags: Math Monday Madness, Math Problem, Problem Solving, puzzle Leave a comment

First Part Of MMM#37

Leave a comment

Subscribe

Translator

Recent Posts

Categories

Math Videos

Search

Comments

Meta

Categories