Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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?
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.
Every move flips 3 coins, so it can never be done in fewer moves than the ceiling of $N/3$.
If $N$ = $3k+1$, there'll be an overlap and at least $k+1$ moves will be needed.
If we just choose every single coin (more than once would be redundant), each will be flipped the amount of an odd number, and the state can be reversed. The question is, are fewer moves enough? If so, then choosing all the omitted (unchosen) coins instead will have no effect. The only way this would work would be for every omitted coin to have another next to it, but not two. With o indicating the omitted:
xoox
xooxo
xooxoox... (put os at the end to cover the "outermost" xes twice, leading to a contradiction when it covers the full circle for any $N$ not divisible by 3. In this case, no coin must be omitted, thus all $N$ moves must be made. For any $N$, $N$ moves guarantee all coins can be flipped.)
