Cut The Knot!An interactive column using Java applets
by Alex Bogomolny
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:
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
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 N: 2,3,4. 5 disqualifies anyway. For N beyond 5, the puzzle is simply too difficult.) On the torus, the corresponding matrix has the determinant 80 and the only small value of N for which it is invertible is N=3.
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 what 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 N=2,3,4 (only N=3 on the torus.) And here is a related question. At the outset, you were told that pressing button #1 will cycle states of buttons 1,2,4, and 5. You were given similar information about the remaining buttons. These were the rules of the game. Now, is it possible to solve the puzzle without the rules being announced in advance? Is it possible to derive the rules with the help of the applet? It would be all right if you surmised the rules by observing button responses. But I ask you to 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) A-1(t - x) = s. Arranging to have t - x equal successively to ei, i = 1, ...,9, where vectors ei have all coordinates 0 with the exception of the i-th one which is 1, we can read columns of A-1 from the Hint one at a time.
To find unknown rules of the puzzle, set t = 0 and apply ei's successively with the Hint box checked. Unchecking the box yields -x, responses corresponding to pressing ei's. In this manner, we actually determine the rule matrix A.
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?
Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at firstname.lastname@example.org
Copyright © 1998 Alexander Bogomolny