3
$\begingroup$

Stan (the clumsy coin flipper) is playing with his favorite toy: A set of $3n$ coins arranged in a circle, each one either heads up or tails up. He enjoys flipping these coins, but he's not very good at it: When he tries to flip one coin, he also flips its two neighbors. So, if he started with an arrangement of coins like (where $H$ stands for "heads" and $T$ for "tails")

  T H T
 T     T
H       T
 H     H
  H T H

and tried to flip the leftmost coin, he would end up with the arrangement:

  T H T
 H     T
T       T
 T     H
  H T H

flipping three coins.

He feels like he's getting pretty good at coin flipping, but has gotten bored with just flipping them aimlessly. He's figured out that it's easy to take an arrangement of all heads and flip every coin to tails in $n$ moves. He's asked you to design him a greater challenge - in particular, he wants you to arrange the coins such that it will take him as many flips as possible to return the coins to all heads-up state. What pattern of heads and tails should you choose to satisfy his request?

(P.S. If you put the coins in an arrangement which is unsolvable, he will be very upset and you'll probably feel guilty for the rest of the day)

(This is a variation on this previous puzzle)

$\endgroup$
  • $\begingroup$ Consider changing your example as it contains 10 coins, which isn't 3n $\endgroup$ – CodeNewbie Jul 19 '15 at 11:58
  • $\begingroup$ @CodeNewbie I edited and added a not-so-pretty example lol, it has 9 coins. $\endgroup$ – warspyking Jul 19 '15 at 13:41
  • $\begingroup$ @warspyking Should've gone with 12 coins, it would only need an addition of one coin in the top and bottom row $\endgroup$ – CodeNewbie Jul 19 '15 at 14:09
3
$\begingroup$

As I explained in my answer to the other question, every sequence of flips is equivalent to a set of coins to flip. Performing two sequences in a row is equivalent to taking the symmetric difference of their sets.

We can divide the coins into three groups of $n$ coins by counting 1,2,3,1,2,3,etc. Flipping all of the coins in one of the groups changes the state of every coin. The only non-empty sets of flips that result in all of the coins in the same state as before are the ones consisting of two of the groups.

Proof: Suppose we have a non-empty set of flips that leaves all the coins the same. It can't possibly contain all the coins (because that changes the state of every coin), so there's at least one coin that isn't flipped. Therefore, there must be a coin that is flipped next to one that isn't.

...XO???...

(X indicates a coin to flip, and O is a coin not to flip.) That coin must be switched back, so we have to flip the next coin.

...XOX??...

This coin also has to be switched back, so the next one also has to be flipped:

...XOXX?...

That coin is switched twice already, so the next one can't be flipped:

...XOXXO...

This pattern must repeat every three coins, so it includes all the coins from two groups and no coins from the last group.


If two different sets of flips result in the same position, then their symmetric difference must leave the coins the same. Therefore, the symmetric difference is all the coins from two groups. The converse is also true: if the symmetric difference of the two sets leaves the coins the same, the sets must lead to the same position.

This means that for every set of flips, there are exactly three others equivalent to it: the symmetric difference with groups 1 and 2, the symmetric difference with groups 1 and 3, and the symmetric difference with groups 2 and 3. If the original set contains $a$ coins from group 1, $b$ from group 2, and $c$ from group 3, then the equivalent sets contain $(n-a)+(n-b)+c$ coins, $(n-a)+b+(n-c)$ coins, and $a+(n-b)+(n-c)$ coins, respectively.

Suppose that the original set represents the shortest way to solve the position. Then these three expressions must all be greater than or equal to $a+b+c$. This is equivalent to:

$a+b\le n\\a+c\le n\\b+c\le n$

We can sum these inequalities and divide by 2 to get $a+b+c\le\frac{3n}{2}$.

For even $n$, we can have $a+b+c=\frac{3n}{2}$ by choosing $a=b=c=\frac{n}{2}$. One possible set with these values is $\frac{3n}{2}$ consecutive coins. This corresponds to the position with $\frac{3n-4}{2}$ tails, one heads, one tails, $\frac{3n-4}{2}$ heads, one tails, and one heads. This position cannot be solved with fewer than $\boxed{\frac{3n}{2}}$ flips.

For odd $n$, we can have $a+b+c=\frac{3n-1}{2}$ by choosing $a=\frac{n+1}{2}$ and $b=c=\frac{n-1}{2}$. One possible set with these values is $\frac{3n-1}{2}$ consecutive coins. This corresponds to the position with $\frac{3n-3}{2}$ tails, one heads, one tails, $\frac{3n-5}{2}$ heads, one tails, and one heads. This position cannot be solved with fewer than $\boxed{\frac{3n-1}{2}}$ flips.

$\endgroup$
  • $\begingroup$ This is much nicer than my proof. I had the patterns you found in mind when I posted this, but after some thinking, I notice that the alternating heads-tails-heads-tails pattern for even $n$ also has $a=b=c=\frac{n}2$, which seems a little nicer. For odd $n$, we can just flip $\frac{3n-1}{2}$ triplets of coins, shifting $2$ to the left each flip, and this yields a "mostly" alternating pattern for odd $n$. $\endgroup$ – Milo Brandt Jul 19 '15 at 16:47

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.