Sand Castle Builder Glass Ceilings Puzzle

Question

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?

Answer 1

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}$.

Answer 2

There are several physical versions of this puzzle:

(Elephant) Spinout, by thinkfun:

The Brain, by Mag-Nif:

and the traditional Chinese Rings puzzle:

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.