Rotating position in a square grid

Question

I was asked a question about the following problem (maybe puzzle would be a better word), which originally came from programming. The person, who asked me this, was programming something involving 3-by-3 square. He decided to index the positions on the square like this:

-------------
| 1 | 2 | 3 |
-------------
| 4 | 5 | 6 |
-------------
| 7 | 8 | 9 |
-------------

Later he found out that he wants to rotate the grid clockwise. So he needed map working like this: $1\mapsto 3$, $2\mapsto 6$, $3\mapsto9$, $4\mapsto2$, $5\mapsto5$, $6\mapsto8$ etc. And he noticed that he can get this map by using $n\mapsto 3n\bmod{10}$. His first question was:

Why does this work?

I'll add the way I was able to explain this, but feel free to include better explanation, if you have one.

I have added a coordinate system to the table:

    -1   0   1
   -------------
-1 | 1 | 2 | 3 |
   -------------
 0 | 4 | 5 | 6 |
   -------------
 1 | 7 | 8 | 9 |
   -------------

In these coordinates, the number in the square can be calculated as $x+3y+5$, where $x$ is the number of the of column and $y$ is the number of the row.

The clockwise rotation is given in this coordinate system by $(x,y)\mapsto(-y,x)$. Hence we want to have $f(x+3y+5)=-y+3x+5$. And the difference $$3(x+3y+5)-(-y+3x+5)=10y+10$$ is indeed a multiple of 10.

A very natural question was:

Can this be generalized?

The natural generalization I was able to think of was taking $n\times n$-square for $n=2k+1$. Again, I can index rows and columns by numbers $-k,\dots,-1,0,1,\dots,k$. Now the number in each row will be $x+ny+(n+1)k+1$. And multiplying by $n$ and taking reminder modulo $n^2+1$ will work: $$n(x+ny+(n+1)k+1)-(-y+nx+(n+1)k+1)=(n^2+1)y+(n^2-1)k+(n-1)=(n^2+1)(y+k)$$

I would be interested to see other generalizations (if there are some):

Another natural question is:

Can something similar be done, if I do not start indexing by 1, but by some other number (for example 0). If starting with 1 is the "best" or "most natural choice", what are the reasons behind it?

Can I get similar simple formula for rotating this table? (Since the numbers used here are 0,1,...,8; I would naturally expect something using modulus 9.)

-------------
| 0 | 1 | 2 |
-------------
| 3 | 4 | 5 |
-------------
| 6 | 7 | 8 |
-------------

One thing that could be helpful for your last question probably is to look at the numbers in base 3. Then they are all 2-digit numbers, the lower digit being the x coordinate and the higher the y coordinate. — mlk, Jun 13 '14 at 14:01

score 1 · Answer 1 · answered Jun 13 '14 at 14:42

For the $3 \times 3$ case, you wrote the number for given coordinates $(x,y)$ as $x + 3y + 5$. This is only the condensed form of the general formula.

For a $(2k+1) \times (2k+1)$ grid centered at the origin, the $0$-based number in one cell for given $(x,y)$ coordinates is $(x+k) + (2k+1) (y+k)$. You can just add $1$ to obtain the original, $1$-based numbers

With this description, the problem turns out to be a purely geometrical one. You can rotate grids of arbitrary sizes (i.e. with arbitrary values for $k$). You can even mirror the grid by letting $(x,y)\mapsto(-x,y)$. Basically, you can use any affine transform, but few of them will produce results that intuitively make sense.

An interesting task could be the generalization of this for even grid sizes, e.g. for a $4 \times 4$ grid (I don't have the time to do this right now, but maybe will have another look at this later).

vadim123 · Answer 2 · 2014-06-13T14:59:44.963

In the ring $\mathbb{Z}/10\mathbb{Z}$, we may multiply by any number coprime to $10$ and permute the elements. Multiplying by $3$ partitions into two cycles of length 1 (namely $0$ and $5$), and two cycles of length $4$ (namely $2,6,8,4$ and $1,3,9,7$). Using a different modulus is possible, provided that some of the cycles are completely unused. Such a solution seems to break the spirit of the problem, though, unless the missing numbers are at the boundaries of the interval, like here (0 is at the boundary of $[0,9]$).

For this to work in a $4\times 4$ grid, you would need to work modulo $16$ or $17$, and find an automorphism that partitions into four cycles of length $4$. It turns out that $13$ works, with modulus $17$. They won't be arranged in the grid in the usual way; it was a great coincidence for the $3\times 3$.

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

Rotating position in a square grid

2 Answers2