Notation, Notation, Notation

So Matt always says that the key to all mathematics is good notation, with the solution to the improved blind man puzzle that is certainly the case. I began my solution to this problem by first trying to show that it can't be done, because lets face it, its clearly impossible. In trying to make my proof that its impossible correct I managed to improve my notation to the point where the solution was easy to find. Truthfully, the notation I use in this puzzle is not all that amazing, but it does help to clear out the needless junk that this puzzle carries with it.

So, first thing we need notation for the legal moves that the player can make. There are really only three possible moves. One is to choose two coins that are diagonally opposite and flip them both, we will call this move D (for "diagonal"). The next move is to take two coins that are adjacent to eachother and flip them both, I called this move H (for "horizontal"). The last move is to just flip a single coin, which coin is always irrelevant, because the spinning of the board will always result in you not having any control whatsoever on which coin gets flipped, this move is called S (for "single").

Alright, next we need to consider the possible board positions. I will name a board position with a number that corresponds to the maximum number of coins that have a common side up. So a position with three coins white side up and one coin black side up with be called position 3. A position with two coins on white and two on black will be called position 2. Position 4 is of course the goal. All positions of the name 3 are identical to the player, as white cannot be told from black in any way, and the exact location of the odd coin out can never be determined. The 2 positions do break into two distinct categories though, 2H will denote the position with two white coins that are adjacent to eachother and two black coins also adjacent to eachother. 2D will denote the position with two white coins diagonally opposite and the two black coins diagonally opposite.

Now, consider the effect that the 3 moves {D,H,S} have on the 3 non-winning positions {3,2H,2D}. D and H can only take position 3 to position 3, as D and H flip two coins each and so cannot change if there are an odd number of coins with black (or white) side up. So we will begin only using moves D and H to make sure we are not in any of positions {2D, 2H} and then we will solve the position 3 case after.
Move 1: D

This will have no effect on the board from position 2H (the only thing D can do to 2H is make it another 2H), and if the position was 2D, we now win. Of course, position 3 would be unchanged.
Move 2: H

This still does not change position 3, and it will turn position 2H into either position 4 or position 2D.
Move 3: D

If the board was in position 2D, we have now won. We have now totally ruled out any position 2D or 2H. If we have not won yet we must be in position 3.
Move 4: S

On position 3, S will make it either position 4 or one of positions 2D or 2H (which one is unknown). But now we know for a fact the board is not in position 3.
Moves 5-7: D,H,D

By the same logic as before, this will rule out position 2D, then change 2H into 2D, then lead to position 4.

This completes the solution. As before, I'm pretty convinced this solution is optimal, but I don't see a real proof of it.

No comments: