## Cut The Knot!An interactive column using Java applets
by Alex Bogomolny |

# Merlin's Magic Squares

April 1998

In *Merlin's Magic Square*, an article that appeared in *The American Mathematical Monthly* in 1987, Don Pelletier explored the mathematical apparatus behind a toy game known as *MERLIN*. The game is not quite trivial and the mathematics is simple enough to provide an entertaining exercise in a Linear Algebra class. The original game is played on a 3x3 array of buttons that toggle between two states. The goal of the game is to achieve a target configuration of button states by pressing the buttons. The difficulty lies in that pressing a button alters its state but also toggles states of some neighboring buttons. The applet below generalizes the game in three ways:

- Buttons are multistate,
- The target configuration is modifiable,
- The manner in which pressing a button affects its neighbors is selectable.

The applet consists of two 3x3 arrays. On the left, the small one shows the target configuration. To modify the target configuration, click on the squares you want modified. On the right, a bigger one holds the puzzle itself and, if the **Hint** box is checked, the hint or, rather, the solution to the puzzle. The hint configuration is also modifiable and the current state of the puzzle changes accordingly. States are represented by a cyclic arrangement of digits - the residues modulo the number of states. I allow only 2, 3, and 4 state buttons for two reasons. For one, with more states the puzzle grew too difficult for me to solve. The second reason will become apparent from the puzzle's theory.

The effect of pressing a button is best described by the following diagram

where the button pressed is colored red and the affected buttons are blue. Other *corner* and *side moves* have an analogous effect.

The applet allows for a second puzzle. Imagine the buttons wrapped on a torus. Then all buttons have exactly the same number of "across-the-edge" neighbors, 4. (In Computer Graphics terms, these are 4-neighbors.) In this modification, all 4-neighbors of a pressed button advance their states along with the button itself. Naturally, the first puzzle is rather **Plane** whereas the second is played on a **Torus**. For technical reasons that will become apparent later, the latter is only played with 3-state buttons. Playing on a torus falls in line with one of Ivars Peterson's recent columns.

### The Theory

Number the nine buttons with digits 1 through 9 starting with the upper left button and proceeding left to right and top to bottom. All possible combinations of button states are then represented by (column) vectors **x** = (x_{1}, ...,x_{9})^{T}. For example, the original target configuration is **t** = (1,1,1,1,0,1,1,1,1)^{T}. Clicking a button adds to the current configuration a certain vector that depends on the button and selected puzzle. For the original puzzle, these vectors form a matrix

To solve the puzzle for a given configuration **x**, we have to find a vector **s** such that

(1)

**t** = **x** + A**s**

where all the operations are carried out modulo N, N being the number of button states. The determinant of matrix A is 5 and the matrix is invertible for any N not divisible by 5. (This is the reason I allow only three values for

### The Practice

Besides solving the puzzle per se, there are several quite meaningful questions that can be asked concerning the puzzle. For example, as you press the buttons, write down their numbers. Every play of the game can be associated with such a sequence of button presses. Now, given two such sequences, is it possible to tell without actually pressing buttons whether they will produce the same result? What abstract properties of mathematical operations help answer this question?

It is often claimed nowadays that mathematics is a quasi-experimental science. Be that as it may, matrix A of the original puzzle has a double eigenvalue 1. Use the applet to find two independent eigenvectors (modulo 2,3,4) for the eigenvalue 1. This is pretty simple if you take into account the symmetry of the puzzle.

In the same spirit of experimental science, use the applet to find A^{-1} (mod N), where *prove* that these are indeed the rules. You may use the applet assuming that it behaves correctly. Check the **Don't touch** box and try answering the question.

A few words about approaching the latter questions. Note that the applet allows us to modify all three vectors in (1), any two of them independently. **s** corresponds to the arrangement on the right with the **Hint** box checked. Let's assume that the applet does indeed implement (1) correctly. Then (everything modulo N) ^{-1}(**t** - **x**) = **s**.**t** - **x****e _{i}**,

**e**have all coordinates 0 with the exception of the i-th one which is 1, we can read columns of A

_{i}^{-1}from the Hint one at a time.

To find unknown rules of the puzzle, set **t** = 0**e _{i}**'s successively with the

**Hint**box checked. Unchecking the box yields -

**x**, responses corresponding to pressing

**e**'s. In this manner, we actually determine the rule matrix A.

_{i}The argument is definitely convincing and the results are at least plausible. But have we *proved* anything? By the way, have you pressed the **Don't touch** button before I asked you to do so? Does *this* prove anything?

### References

- D. Pelletier,
__Merlin's Magic Square__,*The American Mathematical Monthly*, v94, n2, 1987, p143-150. - T. Tymoczko,
*New Directions in the Philosophy of Mathematics*, Princeton University Press, 1998, Revised and Expanded Edition.

- Merlin's Magic Squares
- Merlin Magic Square Game
- Lights Out: an interactive gizmo
- Mini Lights Out
- Flipping Items Simultaneously
- Flipping Items Simultaneously II

|Contact| |Front page| |Contents| |Games|

Copyright © 1996-2018 Alexander Bogomolny

63707994 |