6
$\begingroup$

Given a circular list of coins, that all have Tails facing up. In each move, if we flip the coin at position $i$, then the coins at positions $i-1$ and $i+1$ get flipped as well. That is, consider: H H H T T: if I flip the coin at index 3 (0-based indexing), then the result would be: H H T H H.

  • Initial state: T T T T T ... T $~~$($N$ coins)

  • Final state: H H H H H ... H $~~$($N$ coins)

What would be the minimum number of moves to make all coins have Heads facing up?

$\endgroup$
  • 4
    $\begingroup$ Why not just tell us to flip 3 coins that are next to eachother at once? Instead of going into detail about I-1 and I+1... $\endgroup$ – warspyking Jul 19 '15 at 3:21
7
$\begingroup$

If N is divisible by 3, then flipping every third coin will work (N/3 moves). This must be the minimum because there are N coins changed and each move changes only 3 coins' states.


If N is not divisible by 3, then flipping every coin makes every coin change states three times (N moves).

To prove that this is the minimum, notice that it doesn't matter in what order coins are flipped, and flipping the same coin twice is pointless. This means that every possible sequence of flips is equivalent to a set of which coins are flipped. There are $2^N$ of these sets.

If we start to flip every third coin starting at an arbitrary position, eventually we will reach a state where exactly one coin is heads up and the rest are tails up. Because this can be repeated, any combination of heads and tails is possible. There are $2^N$ of these combinations. This is the same as the number of sets of coins that can be flipped, so each set must correspond to exactly one combination of heads and tails, and vice versa.

We know that flipping every coin makes all coins heads up, so no other set of flips can lead to all heads up. In particular, every sequence of fewer than N flips will be equivalent to a set of flips which is not this set, so it will not lead to the desired position. Therefore, N moves is the minimum.

$\endgroup$
  • $\begingroup$ Can you construct the algorithm? $\endgroup$ – the4seasons Jul 19 '15 at 5:07
  • $\begingroup$ @the4seasons Which algorithm? $\endgroup$ – f'' Jul 19 '15 at 5:38
  • $\begingroup$ The algorithm on how to turn all the coins to heads in n moves $\endgroup$ – the4seasons Jul 19 '15 at 8:48
  • $\begingroup$ @the4seasons You don't need an algorithm. If N is divisible exactly by 3, flip every third coin (in any order) and it works in N/3 flips. If N is not divisible by 3, flip each coin (in any order) and it works in N flips. $\endgroup$ – abligh Jul 19 '15 at 8:56
  • $\begingroup$ ... Ahh I should have thought a bit. Why did I... bangs head on table $\endgroup$ – the4seasons Jul 19 '15 at 9:03
0
$\begingroup$

Every move flips 3 coins, so it can never be done in fewer moves than the ceiling of $N/3$.

  • If $N$ = $3k$, we just choose every third coin ($N/3$ moves).
  • If $N$ = $3k+1$, there'll be an overlap and at least $k+1$ moves will be needed.

    If we just choose every single coin (more than once would be redundant), each will be flipped the amount of an odd number, and the state can be reversed. The question is, are fewer moves enough? If so, then choosing all the omitted (unchosen) coins instead will have no effect. The only way this would work would be for every omitted coin to have another next to it, but not two. With o indicating the omitted:

    xoox
    xooxo
    xooxoox... (put os at the end to cover the "outermost" xes twice, leading to a contradiction when it covers the full circle for any $N$ not divisible by 3. In this case, no coin must be omitted, thus all $N$ moves must be made. For any $N$, $N$ moves guarantee all coins can be flipped.)

$\endgroup$

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.