Marcy Brook

Blog

Karnaugh Maps [MPMP 4]

Published 2020-04-15 18:15:14.862502 UTC

The first thing I immediately noticed with this puzzle is that the state of whether each of the 4 cards are flipped is the equivalent to a 4 digit binary integer. From there there are a few key points that make the solution easy:

1) Flipping over a card twice is the same as not flipping it over, therefore any combination of flips can also be represented as a 4 bit number.
2) Performing an XOR function between the original state and a series of flips will result in the new state of the 4 cards.
3) If you XOR the original state with every one of the 16 combinations of flips, then you are guaranteed that one of the results will be 0000, which is the final goal.

Using this information, we can see that the lowest number of flips is 15 (1 between each adjacent card state), and the puzzle becomes a task of finding a series of 4-bit integers such that each integer is only 1 bit different from the last (to represent one flip), and every one of the 16 unique 4-bit integers is visited. Luckily, this can be done quite easily using only 16 numbers (15 flips: 1 between each adjacent pair), and in a number of ways. How do you find these ways you might ask? Well, let me introduce you to the magic of Karnaugh Maps!
AB CD 00 0000 0100 1100 1000 01 0001 0101 1101 1001 11 0011 0111 1111 1011 10 0010 0110 1110 1010 00 01 11 10
Karnaugh Maps are a way of representing binary strings such that all adjacent squares are exactly one bit different from one another. Moving around a 2x2 Karnaugh map is the equivalent to making a flip for each step, and a step in each of the directions corresponds to flipping each of the cards. (Also, they're technically toroidal, so you can always move in each direction from any cell)
AB CD 00 0000 010 1100 1000 01 0 01 0101 101 1001 11 0011 01 1 1111 1011 10 0010 0110 1110 1010 00 01 11 10 0 1 0 1
So how do we use these maps? Well, if we apply the above rules, we can see that to find the order in which to put the 16 numbers, we can simply take a walk around a Karnaugh map, and as long as we visit each cell once and only once, we have a solution! This is the solution I came up with on the Karnaugh map.
AB CD 00 0000 0100 1100 1000 01 0001 0101 1101 1001 11 0011 0111 1111 1011 10 0010 0110 1110 1010 00 01 11 10
And this corresponds to the following series of flips: 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1.

Of course, any complete path around the map will work, and as such, there are many solutions.

EXT: If you don't care about which way the cards are up (all face-up or face-down), then what you can do is as you go around the Karnaugh map, cross off the inverse of the number you just visited since you know that if your answer isn't one of the two win states, then there's no point visiting the inverse. This reduces the number of flips to 7 for a 4 card game.