6
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ @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. $\endgroup$ – wimi Sep 4 '20 at 7:44
  • 1
    $\begingroup$ @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. $\endgroup$ – tehtmi Sep 4 '20 at 9:45
  • 1
    $\begingroup$ @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. $\endgroup$ – tehtmi Sep 4 '20 at 12:36
  • 1
    $\begingroup$ @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. $\endgroup$ – tehtmi Sep 4 '20 at 12:37
  • 1
    $\begingroup$ @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, ... $\endgroup$ – tehtmi Oct 6 '20 at 6:08
2
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for trying ..see if you can describe it more ..make further attempt at solving it ...best wishes . $\endgroup$ – Hemant Agarwal Sep 5 '20 at 2:03
  • $\begingroup$ 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! $\endgroup$ – bean delivery man Sep 5 '20 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.