Flipping coins in a circle

Question

We have a set of N coins that are all placed in a circle. They all have "Tails" as their face up side. The coins are all distinct and have numbers (1,2,3...N) written on them.

In each move, we flip any 3 consecutive coins. That is, consider:

H H H T T

If I decide to flip the coins 3,4 and 5 then I will get : H H T H H

Now, there can be 2^N distinct heads-tails permutations of N distinct coins.

1.Prove/disprove that there is a finite set of moves in which we can reach any one of the (2^N) heads-tails permutation of these N coins, from the initial all tails permutation.

2.Also, if reaching any permutation is indeed possible, then what is the maximum number of moves that are needed to get to any permutation from the initial all tails permutation.

For further clarification,if N was 3, for example, then the 2^3 distinct permutations of these 3 coins would be:

TTT

TTH

THT

THH

HHH

HHT

HTH

HTT

Answer 1

Let us assume $N \geq 3$ or else the problem isn't well defined.

Part 1:

The ending position of a coin depends only on how many times it has been flipped (even number of flips, it will be T; odd number, H).

So, moves (consisting of three flips) are commutative. Also, moves are clearly self-inverse, so there is no point in making the same move twice. So, we need concern ourselves only with (unordered) sets of move positions (of which there are also $2^N$).

If not all positions are reachable, then two different move sets must give the same result. But that means the symmetric difference (XOR) between these move sets must give the configuration with all T. So we can instead ask if there is some non-empty move set that gives all T.

For any move set, each coin will be flipped between 0 and 3 times. Also, the number of flips for adjacent coins must differ only by 0 or 1. (There is only one move that flip $x$ and not $x + 1$ and vice versa.) So, to get all T, the number of flips must either be all 0 or all 2. All 0 is only possible with the empty move set. What about all 2?

The total number of flips must be a multiple of 3 because each move flips three coins. So, it is impossible to get all 2 unless $N$ is a multiple of 3. If $N$ is a multiple of 3 it is easy. Every coin can be flipped by moving in every third position. Then we can do the same thing again but shifted over by 1 to flip them back.

So, every ending position is reachable if and only if $N$ is not divisible by 3.

Part 2:

If every position is reachable, then every move set reaches a different position. In particular, the set of all move positions reaches a certain ending position in $N$ moves, and no other position will require more than that many moves. This particular position is actually all H as it will flip each coin 3 times.

To quickly compute the move set for a given ending position, I would suggest first computing the move set that just flips coin 1. Then we know how to flip any single coin by shifting this move set. And then we can compute any result by combining single coin move sets (with symmetric difference/XOR).

Answer 2

Less "mathy" approach:

It is obvious that the problem to reach arbitrary configuration is equivalent to a set of moves that flips exactly one coin.

Now how to find it:

You can easily construct required flip sequence using sequence 1,2,4,5,7,... (numbers correspond to starting coin, 1 means flipping coins 1,2,3). This will flip either coin 2 (N = 3k+1) or N (N=3k+2). Construction is obvious, start with coin 1 you are setting as heads with first move, keep flipping all the rest so there is just 1-2 heads propagating towards the "end" of the circle. Once those heads (nearly) meet your first one, perform the final flip. With N=3k+1 you get one head at the end and end up flipping just coin 2, with N=3k+2 you get one head 1 before the end and flip just coin N. With N=3k you get 2 coins at the end and reach all tails. Because you can't "squeeze" those coins out to be left with a single "heads", it is not possible to reach all configurations.

Now worst case:

To get all heads you require all coins to get flipped 1 or 3 times. You obviously can't make all coins get flipped 1 times with N=3k+1 or 2. If a coin X is flipped 3 times, coin X+1 was already flipped 2 times and needs to be flipped one more time etc, proving you need to flip all coins 3 times to get all heads from initial all tails.

Answer 3

I'm probably out of my league here (if I was in one) however, I believe that you explained it very clearly in your question. I'm going to put this simply, because pizza's almost ready and it's been a long Friday. Say you wanted to continue flipping the coins in the order you had said in the problem. You could repeat this sequence: HHH HHT HTH THH, etc., however, since there is a finite amount of coins, a finite amount of sides as well, you could only get a finite amount of answers. I'm unsure if this is what you were getting at, but I hope I have made my point (right or wrong), clean, and clear.