Sorry to still be banging on about this triple coin flip game (see POTW #160 and #161), but the maths behind it is particularly interesting. Today’s puzzle has a very long preamble, but I feel it’s worth the journey and the puzzle itself is quite good fun!
For a given array there will be a particular number of coins, and a particular number of possible moves. For instance, a 4 by 4 grid will have 16 coins and 24 moves.
There are four directions of moves: Horizontal, Vertical, Downhill and Uphill. For the purposes of notation I will place a letter H, V, D or U at the point in the grid corresponding to the centre of the three coins being flipped. So the grid to the right shows all 24 possible moves.
The solution to POTW #161 is particularly interesting, as the number of coins and the number of moves are the same. This means that for any given starting arrangement, there is exactly one set of moves that will solve it. (We can safely say that performing the same move twice is the same as not performing it at all, so we don’t need to worry about repeating a move; a move is either performed or not).
For any arrangement larger than the solution to POTW #161, there will be some sets of moves, which I will call ‘null sets’, that cancel each other out (the simplest of these to understand would be three horizontal moves and three vertical moves within a 3 by 3 area of the array – each of the 9 coins will be flipped twice and end the same as it began). You can even work out how many ‘null sets’ that will exist:
For example, a 3 by 4 grid has 12 coins, and 14 moves. This means there are 2^12 (4096) possible arrangements and 2^14 (16384) possible sets of moves. This means there are 4 times as many ‘move sets’ as there are arrangements. It follows from that that there are 4 ‘null sets’ (although one of those null sets is the empty set – no moves at all).
I’ll now introduce the concept of an ‘independent null set’. That is a null set that cannot be formed by combining other null sets you’ve already found (so technically any null set might be an independent null set if it happens to be one of the first you find). For the 3 by 4 grid there will be 2 independent null sets (let’s call them a and b), and the total of 4 null sets can be formed by a binary combination of these (that is, ‘a and b’, ‘a only’, ‘b only’, and ‘the empty set’). Below is a possible ‘a’ and ‘b’ for the 3 by 4 grid:
This actually simplifies things a little, as the number of independent null sets will simply be the difference between the number of moves and the number of coins. So back to the 4 by 4 grid which will be the basis of this week’s puzzle. As mentioned before, there are 16 coins and 24 moves, so there will be 8 independent null sets. I have found six of them for you. It may initially look as if reflections of e and f will also be independent, but in fact they can be formed by combining each of them with all four of a, b, c and d.
The final two independent null sets are reflections or rotations of each other. Can you find them?
So to recap in case you are a little lost, find a set of moves within the 4 by 4 grid (with no individual move repeated) that cancels itself out, and that cannot be formed by combining any of the other six such sets of moves above.
Addendum: to explain how to 'combine' existing sets of moves: you superimpose all of the moves in the move sets you want to combine. Any moves that occur an even number of times cancel out, any that occur an odd number will be in the combined move set.