## Thursday, March 20, 2008

### Coins In A Row Puzzle Solution

This is the solution to the Coins in a row riddle posted on 10th Feb 2008. Before going forward try the puzzle at Coins in a row puzzle.

It turns out that we can answer this puzzle by starting with a simple 2 by 2 checkerboard, with a head in the lower left corner. This board obviously has 1 coin of one type, and three of the other.

We have four allowed moves. Flipping row 2 or column 1 leaves us with 1 head and 3 tails, but we prefer to think of this as 1 coin of 1 type, and 3 of the other. Flipping row 1 or column 2 changes two tails to heads, but still leaves us with 1 coin of one type, and 3 of the other.

In other words, every move we make leaves 1 of one kind and 3 of the other. So we can never use these moves to get a board that is all the same type.

If we can assume that our checkerboard has at least 2 rows and 2 columns, then the analysis for the 2 by 2 board above still applies. In other words, given, for example, a 6 by 17 board, we simply note where the one head is, and look at the little 2 by 2 square containing that head and three tails. Although lots will happen all over the board as we make moves, we concentrate on this one little area. Just as before, the little area will always have 1 coin of one type and 3 of the other. Therefore, the board can never be all of one type.

---

This analysis will not apply if the board has only one row, or only one column, but of course, then it's obvious that the coins can all be matched.

It should also be obvious that the actual location of the single head doesn't matter.