You have ten coins in a row, all facing tails up. You are to perform a sequence of moves on the coins where one move consists of flipping over any one coin from tails to heads, then flipping over the coin to its immediate right (whether the second coin is heads or tails does not matter, just flip it over). Can you prove that no matter what moves you select, there are a finite number of moves in the sequence? (In other words, prove that you will always reach a state where there are no more legal moves.) Click below for the answer.

It helps to try this out a few times to get a feel for how the combinations of coins progresses as you make moves in this game. If you don't have any coins handy, just use 0s (tails) and 1s (heads) on a piece of paper, starting with ten 0s, and work through a few sequences. Here's an example:

Now, instead of focusing on the sequence of moves, focus on the sequence of resulting numbers. Do you notice anything? This is a binary number sequence that is always increasing. The rules of the game are designed such that no matter which bit you choose, the next number in the sequence will always be higher. (Because you flip a 0 to a 1, then flip a lower-order bit.) Since the sequence is strictly increasing, you must eventually reach a state where there are no more legal moves.

## No comments:

Post a Comment