The Theory behind the Merlin Game
This page outlines the theory behind the Merlin Game. It will be useful to those who grabbed the page out of curiosity only to find obscure sums and multiplications of several quantities in JavaScript code which does not actually reveals the algorithm. The explanation is by necessity short but provides sufficient information for further search and study. Probably any book encompassing High School Algebra I&II will do although it's unlikely to consider higher (beyond 3 as, for example, 9) dimensionality spaces. For further reading find beginner's books on Linear Algebra.
There are two keywords to what follows: boolean system and $9$-dimensional vector space. Every checkbox may be in one of two states: it's either checked or unchecked. The notion is quite suggestive but does not yet make it to the class of boolean numbers as they are commonly understood.
What makes numbers numbers is their relationship to other numbers. For example, one would expect to be able to add and multiply two numbers. Boolean arithmetic is extremely simple and is based on the following two tables:
| $+$ | $0$ | $1$ | $\times$ | $0$ | $1$ | ||
|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $1$ | $0$ | $0$ | $0$ | ||
| $1$ | $1$ | $1$ | $1$ | $0$ | $1$ |
The second table is unexceptional and only means that $0$ times any number gives $0$ whereas $1$ times a number gives that same number. The first table brings one surprise though, viz.,
$1 + 1 = 0.$
As with all other number systems we also have
$1 - 1 = 0.$
Now, a $9$-dimensional vector is a sequence $v = (v_{1}, v_{2}, ..., v_{9}).$ Vector $v$ is boolean if all its components $v_{i},$ $i = 1, 2, ..., 9,$ are either $0$ or $1.$ But again calling a sequence a vector only makes sense if it's done in its relationship to other similar entities.
Thus let there be two vectors $v,$ as above, and $u$ defined similarly:
$u = (u_{1}, u_{2}, ..., u_{9}).$
Their addition $u + v$ is defined componentwise, i.e.,
$(u + v)_{i} = u_{i} + v_{i}.$
Multiplication by a number s is also defined componentwise:
$(su)_{i} = su_{i}.$
Returning to the game, let enumerate all $9$ squares from left to right and from the top row downwards:
| $1$ | $2$ | $3$ |
|---|---|---|
| $4$ | $5$ | $6$ |
| $7$ | $8$ | $9$ |
Both the original and target square configurations could then be described using $9$-dimensional boolean vectors where in the $i$'th position stands $1$ if the corresponding box is checked and $0$ otherwise. Let us call this vectors $v_{o}$ and$ v_{T},$ respectively. Clicking the checkbox #1 on the right board adds to $v_{o}$ the vector $(1, 1, 0, 1, 1, 0, 0, 0, 0).$ As another example, clicking on the box #6 adds the vector $(0, 0, 1, 0, 0, 1, 0, 0, 1).$ Thus, one may construct nine vectors, say, $v^{1}, ..., v^{9}$ each corresponding to a click on one of the checkboxes in the right square. The problem of solving the game might then be reformulated as:
Find boolean $s_{1}, s_{2}, ..., s_{9}$ such that
$v_{T} = v_{o} + s_{1}v^{1} + ... + s_{9}v^{9}$
where $s_{i} = 1$ if and only if the box #i must be clicked on in order to solve the problem. This is a system of $9$ linear equations that could be rewritten as
$v_{T} - v_{o} = v_{T} + v_{o} = s_{1}v^{1} + ... + s_{9}v^{9}$
And in matrix notations it will look like $v_{T} + v_{o} = sV$ where $9\times 9$ matrix $V$ is composed of vectors $v^{i}.$ Finally,
$s = (v_{T} + v_{o})V^{-1}.$
I computed inverse $V^{-1}$ using MathCAD 6.0 which is a pleasure to use due to its power and abundance of various features. Sure enough, the result was a rational $9\times 9$ matrix which is too cumbersome to cite. However, it brings one important point. Boolean operations may actually be viewed as operations in modulo $2$ arithmetic. Then $1 + 1= 0$ is interpreted as the fact that the sum of two odd numbers is even. Other entries in the tables above may be interpreted in a similar fashion. If you ever get $V^{-1},$ the following remark will help you reduce it to the boolean one below.
Remark
Since in the arithmetic modulo $2,$ $1 + 1 + 1 + 1 + 1 = 1,$ one may claim that $1/5 = 1.$
Here then the promised boolean inverse of the matrix $V:$
| $1$ | $1$ | $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ |
| $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $1$ | $0$ | $1$ |
| $1$ | $1$ | $1$ | $0$ | $1$ | $1$ | $1$ | $0$ | $1$ |
| $0$ | $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $1$ | $1$ |
| $0$ | $1$ | $0$ | $1$ | $1$ | $1$ | $0$ | $1$ | $0$ |
| $1$ | $1$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $0$ |
| $1$ | $0$ | $0$ | $1$ | $1$ | $0$ | $1$ | $1$ | $1$ |
| $1$ | $0$ | $1$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ |
| $0$ | $0$ | $1$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ |
The fact that the above matrix is invertible is equivalent to the assertion that vectors $v^{1}, ..., v^{9}$ form a basis in the 9-dimensional space. A simpler basis is formed by nine vectors each sporting a single 1 in a different position. Selecting a basis of vectors with binary coordinates generates a different game. As an example, I coded three games that are played by different rules.
Further details can be found in
Don Pelletier, Merlin's Magic Square, The American Mathematical Monthly, v94, n2, 1987, p143-150.
P.S. You can check your understanding of the above material by trying to solve the following
In a $4\times 4$ chessboard, all squares are colored white or black. Given an initial coloring of the board, we are allowed to recolor it by changing the color of all squares in any $3\times 3$ or $2\times 2$ subboard. Is it possible to get every possible recoloring of the board from the "all-white" coloring by applying some number of these "subboard recolorings"?
I picked it up from Tangents, a delightful Harvard University student publication. I enjoyed several articles in this interactive magazine that also offers a problem column.
Solution
|Contact| |Contents| |Merlin Game|
Copyright © 1996-2018 Alexander Bogomolny71535013