Cut The Knot!An interactive column using Java applets
by Alex Bogomolny
Merlin's Magic Squares
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.
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 = (x1, ...,x9)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
t = x + As
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
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
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)
To find unknown rules of the puzzle, set
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?
- 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.
Copyright © 1996-2018 Alexander Bogomolny