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.