On Endarkenment

| 0 Comments

The first thing to note about the Baron's game is that since four tiles must be turned over at each turn it is impossible to turn out an odd number of lamps. If one of the four was lit at the start of the turn, then three would be at its end yielding a net change of two. Considering the change made when from zero to four tiles were lit at the outset makes it clear that a game with an odd parity of lit lamps cannot be won.
If presented with such a board Sir R----- should most certainly have declined the Baron's wager.

The question we are presented with is whether or not all games of even parity can be won. To answer it, consider turning the following patterns of tiles one after the other for the same rightmost tile


to yield a change of


Now we can use this pattern, together with its rotation, to move a lit tile up, down, left or right and consequently, with repetition, to an arbitrary position upon the board. We can in this manner construct, and equivalently destruct, any even parity pattern of tiles upon the topological torus of the board.
Sir R----- would consequently have been well advised to have taken the Baron up on his first wager if, and only if, the board had even parity.

I should have advised Sir R----- not to have taken the second wager if the board had odd parity for the exact same reason as I would have for the first. In addition, if the board had more than sixty lit tiles Sir R----- could not have turned enough to endarken them all and should consequently have declined to play.

Unfortunately figuring whether or not to take the wager otherwise is a rather trickier proposition.
If we consider the tiles to represent Boolean atomics, with lit tiles equating to true and unlit to false, we can treat the game as a logical satisfiability problem; a problem of choosing truth values for some Boolean variables that satisfies some set of logical expressions.
To see how, consider the following two by two arrangement of tiles.


We can switch the state of any horizontal or vertical pair of tiles using the combinations of moves described above. If we label the top row \(a\), the bottom row \(b\), the left column \(c\) and the right column \(d\) we can express those we should switch as a set of Boolean simultaneous equations
\[ \begin{align*} E_1:& a \oplus c = false\\ E_2:& b \oplus c = true\\ E_3:& a \oplus d = true\\ E_4:& b \oplus d = false \end{align*} \]
where \(\oplus\) means exclusive-or.
Satisfiability problems are, in general, extremely difficult to solve but that ours only involves exclusive-or operations means that we can solve it in much the same way that we solve regular simultaneous equations, by eliminating variables
\[ \begin{align*} E_5 = E_1 \oplus E_2:& a \oplus b = true\\ E_6 = E_3 \oplus E_4:& a \oplus b = true \end{align*} \]
That we can proceed no further is a consequence of there being more than one way to clear the board; we can either switch the top row and the left column or the bottom row and the right column.
We should almost certainly fail to rule out all of the options in the game writ large, so unless Sir R----- was willing to evaluate all of those remaining in search of the shortest sequence of moves, or at least had some good confidence in his strategising, I should not have advised him to accept the Baron's second wager.
\(\Box\)

Leave a comment

 
This site requires HTML5, CSS 2.1 and JavaScript 5 and has been tested with

Chrome Chrome 26+
Firefox Firefox 20+
Internet Explorer Internet Explorer 9+