Given a circular list of coins, that all have Tails facing up. In each move, if we flip the coin at position $i$, then the coins at positions $i-1$ and $i+1$ get flipped as well. That is, consider: H H H T T: if I flip the coin at index 3 (0-based indexing), then the result would be: H H T H H.
Initial state: T T T T T ... T $~~$($N$ coins)
Final state: H H H H H ... H $~~$($N$ coins)
What would be the minimum number of moves to make all coins have Heads facing up?
Answer
If N is divisible by 3, then flipping every third coin will work (N/3 moves). This must be the minimum because there are N coins changed and each move changes only 3 coins' states.
If N is not divisible by 3, then flipping every coin makes every coin change states three times (N moves).
To prove that this is the minimum, notice that it doesn't matter in what order coins are flipped, and flipping the same coin twice is pointless. This means that every possible sequence of flips is equivalent to a set of which coins are flipped. There are $2^N$ of these sets.
If we start to flip every third coin starting at an arbitrary position, eventually we will reach a state where exactly one coin is heads up and the rest are tails up. Because this can be repeated, any combination of heads and tails is possible. There are $2^N$ of these combinations. This is the same as the number of sets of coins that can be flipped, so each set must correspond to exactly one combination of heads and tails, and vice versa.
We know that flipping every coin makes all coins heads up, so no other set of flips can lead to all heads up. In particular, every sequence of fewer than N flips will be equivalent to a set of flips which is not this set, so it will not lead to the desired position. Therefore, N moves is the minimum.
No comments:
Post a Comment