5
$\begingroup$

Disclaimer: This is not mine but taken out of the game Sand Castle Builder, but I can't find it anywhere in a distilled version and it's a nice puzzle :)

You are given N (6 is a good start) coins which are laid out in a row from left to right, all with heads visible.

A coin can be flipped if the coin directly to the left is tails and all other coins left of that one are heads. The leftmost coin can be flipped at any time.

Your task is to make all coins tails. What is the strategy to do that? How many moves are needed for N coins?

$\endgroup$

2 Answers 2

6
$\begingroup$

This seems like an induction problem.

N=1

H -> T it's the trivial case because the only coin is also the leftmost (1 Step)

N=2

HH -> TH -> TT also pretty easy (2 Steps)

N=3

HHH -> THH -> TTH -> HTH -> HTT -> TTT as you can see, we need to flip the first N-1 coins, then flip all but the N-1st coin back and finally flip all of them (2+3 = 5 Steps)

N=4

Thanks to the rule in N=3 we can simplify the operation: HHHH -5-> TTTH -> THTH -> HHTH -> HHTT -> THTT -> TTTT (5+5 = 10 Steps)

By now we see that the way to flip N coins is: 1. Flip the first N-1 coins, Flip the first N-2 Coins back, Flip the Nth Coin, Flip the first N-2 Coins.

Let's look at the process for flipping N coins back (from Tails to Heads): This is also a case of induction: To flip the last coin, flip the first N-2 Coins back, then flip the Nth coin back and then flip the first N-2 Coins. Then repeat the process for N-1 Coins.

Let's put together a formula: Flips(N) = Flips(N-1) + Backflips(N-2) + Flips(N-2) +1; Backflips(N) = Backflips(N-1) + Flips(N-2) + Backflips(N-2) + 1; The base cases are Flips(N<0) = Backflips(N<0) = 0; Flips(1) = Backflips(1) = 1; Since the formulae are interchangeable and the base cases are the same we see that Flips(N) = Backflips(N)

Therefore Flips(N) = Flips(N-1) + 2Flips(N-2) + 1

N = 5

using the process outlined above, it would take 10 + 10 + 1 = 21 moves

N = 6

using the process outlined above, it would take 21 + 20 + 1 = 42 Moves

Formula for any N:

I haven't been able to find a solution myself, so I'll prove the one Wolframalpha and Jaap Scherphuis give me. WolframAlpha, Jaap Scherphuis and some algebra tell me the answer is $Flips(N) = -\frac{1}{6}*(-1)^N + \frac{2}{3}*2^N - \frac{1}{2}$, so maybe I'll just try to prove that this formula fulfills the requirements. For N=1 the result is one, so the base case holds true. For Any N we get from the recursive formula $Flips(N) = -\frac{1}{6}*(-1)^{N-1} + \frac{2}{3}*2^{N-1} - \frac{1}{2} + -\frac{2}{6}*(-1)^{N-2} + \frac{4}{3}*2^{N-2} - 1 + 1 = \frac{1}{6}*(-1)^{N-1} - \frac{2}{6}*(-1)^N + \frac{1}{3}*2^N + \frac{1}{3}*2^N - \frac{1}{2} = -\frac{1}{6}*(-1)^N + \frac{2}{3}*2^N - \frac{1}{2}$ which is the expected iterative function. Thus by induction the formula is $Flips(N) = -\frac{1}{6}*(-1)^N + \frac{2}{3}*2^N - \frac{1}{2}$.

$\endgroup$
4
  • $\begingroup$ Nice answer! You figured out the pattern, can you find the direct formula? :) $\endgroup$
    – Nurator
    Feb 22, 2022 at 8:39
  • 3
    $\begingroup$ There are standard mathematical techniques for solving such a recursive formula. IIRC, it gives you that it is a linear combination of $2^n$ and $(-1)^n$, and the initial conditions for n=1 and n=2 then allow you to solve the coefficients, which turn out to be 2/3 and -1/3 I think. $\endgroup$ Feb 22, 2022 at 8:39
  • $\begingroup$ Unfortunately, It's been a long time since I learned the standard techniques for solving recursive sequences. I'll try my best, to get to Jaaps solution myself! $\endgroup$
    – xyldke
    Feb 22, 2022 at 8:46
  • 2
    $\begingroup$ Nice work! I forgot about the constant +1 term in the recursive formula for Flips, so my previous comment wasn't quite right. The smaller terms add up to a number between -1 and 0, so you can ignore them and simply take the dominating $\frac{2}{3} \cdot 2^N$ term rounded down to an integer. $\endgroup$ Feb 22, 2022 at 10:54
9
$\begingroup$

There are several physical versions of this puzzle:

(Elephant) Spinout, by thinkfun:
enter image description here

The Brain, by Mag-Nif:
enter image description here

and the traditional Chinese Rings puzzle:
enter image description here

The solution is based on the Binary Gray Code. At any moment at most 2 moves are available, so there is never really any choice - you can only move forwards to the solution or backwards away from the solution. With the physical puzzles above, there are two moves available at the start so you can start off in the wrong direction.

With the coin puzzle as described there is only one possible first move, so you will always start in the right direction, and if you never reverse direction by undoing a move, it will eventually be solved. It would have been more interesting if the coins started all tails, and the aim was to get all heads. Then you could flip either the first or second coin as a first move. The correct first move is then:

the first if there are an odd number of coins, the second if there are an even number of coins.

Starting at all heads, you can run through all $2^n$ configurations in $2^n-1$ moves, ending with the configuration where all but the last coin is heads. The all-tails position is two-thirds of the way through, so it takes $\lfloor \frac{2^{n+1}}{3} \rfloor$ moves to solve the puzzle.

You can find more information on my website.

$\endgroup$
3
  • $\begingroup$ Oh awesome that there is a physical version of this puzzle! $\endgroup$
    – Nurator
    Feb 22, 2022 at 8:39
  • $\begingroup$ I feel like you could probably also draw a connection to the classic Towers of Hanoi puzzle. (Another 2^n - 1 problem) It's not quite the same, but feels like it may have some mathematical parallels. It follows the same pattern but doesn't quite go all the way through the sequence. $\endgroup$ Feb 22, 2022 at 16:21
  • $\begingroup$ @DarrelHoffman if you play with a physical copy of the "chinese rings" version of this (I have one, but by a different name) you will feel an even stronger similarity to the towers of hanoi. $\endgroup$
    – fectin
    Feb 22, 2022 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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