6

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

Jaap Scherphuis
  • 53,019
  • 7
  • 120
  • 208
Hemant Agarwal
  • 2,912
  • 14
  • 31

3 Answers3

12

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).

tehtmi
  • 3,241
  • 15
  • 18
  • hi, for part 1, what about N=4? You can't get the 2 middle coins to have different sides up. – Pierre Schneegans Sep 04 '20 at 07:23
  • 2
    @PierreSchneegans yes you can, note that the coins are placed in a circle. So you can switch coins 4, 1, and 2 and go from TTTT to HHTH in one move. – wimi Sep 04 '20 at 07:44
  • What does this line mean : "So, we need concern ourselves only with (unordered) sets of move positions (of which there are also 2^N).". What does "set of move positions" mean here and why are they 2^N? – Hemant Agarwal Sep 04 '20 at 09:27
  • 1
    @HemantAgarwal There are N different moves you can make. In my answer, I chose not to introduce any notation, but for example move 1 could flip 1,2,3; move 2 could flip 2,3,4; ...; move N could flip N,1,2. "Set of move positions" is just a set of moves in the formal mathematical sense of "set": for each move, a set of moves either contains that move or doesn't, and order doesn't matter. Since can make N independent binary choices to specify this set -- for each move, it contains the move or doesn't -- that gives 2^N total. I guess the term "move position" suggests thinking of moves abstractly. – tehtmi Sep 04 '20 at 09:45
  • Thanks. Can you also please explain what you meant by the following, "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" ? I am guessing that in the above, "these move sets" is referring to 2 move sets that are giving the same result. But I didn't understand the rest. I do know though what it means to XOR 2 bits. What was also not clear to me was why XORing the 2 strings of move sets will result in a move sequence that will result in an all tails configuration. – Hemant Agarwal Sep 04 '20 at 12:27
  • 1
    @HemantAgarwal: Consider the two sets of moves that give the same result. If we start in that result configuration and make the moves from the first set, we will get back to all tails (by self-inverse), and then if we proceed and make the moves from the second set, we will get back to the result configuration where we started. So, applying these two moves sets in sequence gets us back to where we started. If we instead started with all T, apply these two move sets would then still get us back where we started. This corresponds to a new move set. – tehtmi Sep 04 '20 at 12:36
  • 1
    @HemantAgarwal: To combine the move sets, we take moves that appear in either one or the other. But, if a move appears in both, the two copies will cancel out and it won't be in the new set. This "one or the other but not both" is the symmetric difference. – tehtmi Sep 04 '20 at 12:37
  • I had asked @tehtmi the following question on chat. His reply is given in the next comment . My question: I also didn't get this, "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". I especially did not understand how you came to the conclusion that the number of flips for adjacent coins must differ only by 0 or 1. – Hemant Agarwal Sep 11 '20 at 10:32
  • His answer to the above question which was given to me on chat, "For example consider coins 3 and 4. Flipping 1,2,3 flips 3 and not 4. 2,3,4 or 3,4,5 flip both. 4,5,6 flips 4 but not 3. So if we want to know the difference in the number of flips for 3 and 4, 2,3,4 and 3,4,5 don't matter. If we flip both or neither of 1,2,3 and 4,5,6 the number of flips for 3 and 4 is the same. If we flip one or the other but not both, then the difference will be 1. (This is only true if we can't repeat the same move twice, but we can assume that as noted previously.) Contd. below – Hemant Agarwal Sep 11 '20 at 10:34
  • Then, for the full result to be all T, the number of flips for each individual coin has to be 0 or 2, but since adjacent coins can't differ by more than 1, there is no way to have some coins with 0 and some coins with 2, so it is either all 0 or all 2." – Hemant Agarwal Sep 11 '20 at 10:34
  • @tehtmi , "To quickly compute the move set for a given ending position, I would suggest first computing the move set that just flips coin 1." Can you please tell us how to just make coin 1, heads? I tried various ways but couldn't come up with the required move set. – Hemant Agarwal Oct 06 '20 at 03:42
  • @tehtmi , "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)." So, let us say that we want to just change position of coins 1 and 5 to heads. We also already know the move set to make just coin 1, heads and the move set to make just coin 5, heads. How do we then know that XORing the above 2 move sets will result in a configuration where only coins 1 and 5 are at heads position and all the rest are in tails position? – Hemant Agarwal Oct 06 '20 at 04:29
  • 1
    @HemantAgarwal: To flip coin 1 if N is one more than a multiple of 3, you can move at 2, 5, 8, ... and continue at every third position to flip every coin except 1. Then recall that moving at every position flips every coin, so follow by doing that to get just coin one. (This will be equivalent to the move set 1, 3, 4, 6, 7, 9, 10, ...) If N is two more than a multiple of three, move at 1, 4, 7, 10, ... ; this flips every coin, but since N but that last move will wrap around and "un-flip" 1. Then again, we can follow up by flipping every coin to "invert" the pattern: 2, 3, 5, 6, 8, 9, ... – tehtmi Oct 06 '20 at 06:08
  • @HemantAgarwal: The explanation for combining with XOR is the same fundamental idea as the previous mention of XOR. If we apply one move set to flip coin 1 followed by another move set to flip coin 5, then we will end up with 1 and 5 flipped. Recall that moves are commutative and that two moves in the same position cancel each other out. So, if we take moves that appear in one of the sets, but not both (as these cancel out), we get a set that is the same as applying the two sets in succession. This is the XOR. – tehtmi Oct 06 '20 at 06:16
  • @HemantAgarwal: It is important to be precise about what we mean by combining the results of two move sets. The result I'm talking about is the result of applying the move sets one after the other. (This has a nice formulation I will comment on below, but I think it is not needed for the immediate discussion.) So, in your example combining move sets 1, 2, 3 and 3, 5 gives 1, 2, 3, 3, 5 which has a duplicate 3. The second application of this 3 move will just reverse the first application, so this gives the same result as 1, 2, 5. – tehtmi Oct 06 '20 at 14:40
  • @HemantAgarwal: For the purpose of my answer, I am only concerned with combining a move set that flips a single coin with a move set that didn't flip that coin with the (implicit) claim that this flips all the coins flipped by both sets. But, in general, combining two move sets sequentially (equivalently with XOR) will flip the XOR of the sets coins flipped by the move sets individually. – tehtmi Oct 06 '20 at 14:40
  • @HemantAgarwal: This can be understood directly in terms T resulting from an even number of flips and H from an odd number. If the two sets both flip a particular coin an even number of times, the total for that coin is even (T+T=T); if one set flips an even number of times and the other flips an odd number of times, the result is odd (T+H=H, H+T=H); if both flip an odd number of times, the result is even (H+H=T). This illustration may be helpful: https://imgur.com/a/UONyDPv – tehtmi Oct 06 '20 at 14:40
  • The above 3 comments by tehtmi are in response to this query of mine: I am unable to understand your XOR argument given above and how XORing two move sets will combine the results that the move sets will achieve independently. For example, let the first move set be 11100 and the second move set be 00101. Notice that both the move sets have a 1 in the 3rd position . This means that the first move set needs a 1 in the 3rd position to achieve it's desired configuration and the second move set also needs a 1 in the 3rd position to achieve it's desired configuration. contd. below – – Hemant Agarwal Oct 07 '20 at 01:37
  • But when we XOR these two move sets, then we will get 11001 which does not have a 1 in it's 3rd position. How can we then say that this new move set (11001) will give us the combination of the 2 original move sets? – Hemant Agarwal Oct 07 '20 at 01:38
  • @tehtmi , I found the last comment of yours , incomplete. I did understand what you are saying but couldn't understand how it proves that XORing 2 move sets and then applying the resultant move set to the initial all tails configuration will result in the same configuration as XORing the 2 configurations we will get by applying each individual move set independently to the all tails configuration . I am talking about this comment of yours :. "This can be understood directly in terms T .........if both flip an odd number of times, the result is even (H+H=T). This illustration may be helpful " – Hemant Agarwal Oct 07 '20 at 06:46
  • @HemantAgarwal: Answered in chat. – tehtmi Oct 07 '20 at 09:35
  • @tehtmi , I came across the following question . This is very similar to the question above and has many parallels. In case you would like to try this question, then request you to use your above method / use your above method with the slightest of modifications to solve it. This is the question : https://puzzling.stackexchange.com/questions/36479/is-this-chromatic-puzzle-always-solvable – Hemant Agarwal Oct 10 '20 at 13:19
  • @HemantAgarwal: I'm not sure the same kind of approach is as fruitful. With coin flipping, moves have a helpful algebraic structure that is not clear in the other question where moves are not even invertible. – tehtmi Oct 11 '20 at 13:39
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.

Zizy Archer
  • 2,150
  • 7
  • 15
-2

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.

bean delivery man
  • 193
  • 9
  • Thank you for trying ..see if you can describe it more ..make further attempt at solving it ...best wishes . – Hemant Agarwal Sep 05 '20 at 02:03
  • I'm afraid that's the best I can do, I am not good at things like this. However, efforts unused are no good, and hopes that are low bring no joy. Thank you for a mentally stimulating puzzle! – bean delivery man Sep 05 '20 at 02:52