A magic square is $2\times 4$ matrix with entries $1, 2, \dots, 7, 8$ where no entry occurs twice (equivalent to a permutation). As an example, consider the following magic square:

$\displaystyle \begin{bmatrix} 1 & 2 & 3 & 4 \\ 8 & 7 & 6 & 5 \end{bmatrix}$

There are three transformations that can be applied to a magic square, each an arbitrary number of times and the order doesn't matter:

  1. exchange the top and bottom row,
  2. single right circular shift of the matrix,
  3. single clockwise rotation (90 deg) of the $2\times 2$ submatrix in the middle (the submatrix with the entries $2,3,6,7$ in the example above).

Let's apply these transformations to the example above to illustrate what they do:

$\displaystyle 1: \begin{bmatrix}8 & 7 & 6 & 5 \\ 1 & 2 & 3 & 4\end{bmatrix} \qquad 2: \begin{bmatrix}4 & 1 & 2 & 3 \\ 5 & 8 & 7 & 6\end{bmatrix} \qquad 3: \begin{bmatrix}1 & 7 & 2 & 4 \\ 8 & 6 & 3 & 5\end{bmatrix}$

QUESTION. In the problem statement from IOI '96 one reads the following claim.

All possible configurations are available using the three basic transformations.

Why is that true?

Of course, since there are only $8! = 40320$ magic squares, a simple breadth-first search traversal will show the claim is true. But let's forget about the computer. Is there another way to prove the claim using a combinatorial observation? How can we show that every state is reachable?

  • $\begingroup$ My usual approach for this kind of problem is to fiddle around with the given operations until I find some composition of them that moves as few points as possible, i.e. transposes only two numbers. If you can do this, then you should be able to transpose two numbers of your choice by conjugation (i.e. doing set-up moves before your operation and undoing them after it). At this point, you will be able to switch two numbers at will, so you can put everything in place one by one. $\endgroup$ – Ravi Fernando Sep 3 '17 at 21:59
  • $\begingroup$ In other words (if you're familiar with group theory): to show that some set of permutations generates the symmetric group, show that it generates each of some known set of generators, such as the transpositions. $\endgroup$ – Ravi Fernando Sep 3 '17 at 22:00
  • $\begingroup$ That's basically my question. Are there non-trivial results in group theory that may help solving this problem? From my perspective, it still requires combinatorial observations. $\endgroup$ – neutron-byte Sep 6 '17 at 10:51
  • $\begingroup$ One approach: a set of elements generates a (finite) group if and only if they don't all lie in a common maximal subgroup. If you know all the maximal subgroups of $S_8$, you can check them one by one. (GAP tells me that up to conjugacy, there are seven: $A_8, S_7, S_6 \times S_2, S_5 \times S_3, S_4 \wr S_2, S_2 \wr S_4, PGL(3,2)$. Most of these are easy to check in your case.) If you really want a nuke, there's the O'Nan-Scott theorem classifying maximal subgroups of $S_n$, but I'm sure you have better things to do with your life than working out what O'Nan-Scott says for $n=8$. $\endgroup$ – Ravi Fernando Sep 11 '17 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.