I stumbled upon a mathematical puzzle that goes like this: You have 2n coins that alternate between head and tail. For example, if n=3, then it looks like H T H T H T, where H = head and T = tail. To win the game, all coins must be either head or tail. The permitted move is alternating the face of 2 or more adjacent coins. For example, if n=3, I would solve it like this:

Start: H T H T H T First move: H H T H T T (I alternated the face of coin number 2,3,4 and 5 ) Second move: H H H T T T (I alternated the face of coin number 3 and 4) Third move: H H H H H H (I alternated the face of coin number 3,4 and 5 )

So basically I won because all coins are head.

Now the problem is to prove that the number of moves cannot be below n. How would I prove something like that?

We could also make the game more general by forming a square of 2n by 2n alternating coins, and now the problem would be to find the minimum amount of moves so that all 4n^2 coins are either head or tail. The permitted move in this case would be to alternate the face of any coins that form a rectangle or square inside the 2n by 2n square.

  • $\begingroup$ Not sure why you had no upvotes before now. The generalisation of this looks very interesting. $\endgroup$
    – hexomino
    Oct 7 '18 at 22:52

Proof for the row of coins:

In the row of 2n coins of alternating orientations, there are 2n-1 places where adjacent coins have different orientation. In one move you flip a continuous sequence of coins. The difference in orientation of pairs of adjacent coins inside this sequence is preserved (because both coins are flipped). Only the pairs of adjacent coins at the ends of the sequence (where one coin is flipped and the other is not) can change the difference in their orientation. This means that in one move you can fix at most 2 such places. In the final configuration there are no such places, so you need to do at least n moves to fix them all.

I'm pretty sure you can generalize this approach to deal with a square of coins.


This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .