Sometimes people post their homework problems on stackoverflow.com I don’t answer homework problems, but I do like to try to figure them out.

Problem description: Take a stack of coins all heads up. Upturn the topmost coin, place back on the stack and then proceed: take the top 2 coins and upturn as a single stack (tail, head becomes when upturned and placed back on the stack tail, head (the two coins are flipped as if glued together)). Now in the same way flip the top 3 coins and place back on the stack (you get: tail, tail, head (and if there were 4 coins that would be tail, tail, tail, head). When you upturn the whole stack begin again with the first coin. Continue until you return to a stack with all heads up.

Here’s what I came up with:

‘Stack a number of coins all heads up

‘flip the first coin and put on the stack

‘flip the first and second coin as a unit and put on the stack

‘flip the fist n coins as a unit and put on the stack

‘repeat flipping the first coin

‘stop when all coins are heads up

Dim i As Long, j As Long

Dim aCoins() As String

Dim lCount As Long

Dim dMidPoint As Double

Dim sTemp As String

Dim bAllHeads As Boolean

Const lCOINS As Long = 6

ReDim aCoins(1 To lCOINS)

‘set all coins to heads

For i = 1 To lCOINS

aCoins(i) = “H”

Next i

lCount = 0

Debug.Print lCount, Join(aCoins, “,”)

Do

For i = 1 To lCOINS

‘flip the first j coins

For j = 1 To i

If aCoins(j) = “H” Then

aCoins(j) = “T”

Else

aCoins(j) = “H”

End If

Next j

‘swap coins around the midpoint

dMidPoint = i / 2

For j = 1 To Int(dMidPoint)

sTemp = aCoins(j)

aCoins(j) = aCoins(i – (j – 1))

aCoins(i – (j – 1)) = sTemp

Next j

lCount = lCount + 1

Debug.Print lCount, Join(aCoins, “,”)

‘check for tails

bAllHeads = InStr(1, Join(aCoins, “,”), “T”) = 0

If bAllHeads Then Exit Do

Next i

Loop Until bAllHeads

End Sub

I only tested it to six coins. I thought the graph would be prettier.

Dick

It looks like the upper and lower points of your chart are definitely fitting some sort of series

I’ve been bashed over the head with the following advice by professors in the past, and I think it bears repeating here:

“Always label your axes!”

I think that the horizontal axis represents the number of coins in a stack and the vertical axis represents the number of flips required to return all coins to the original orientation…correct?

Yes, x=coins in stack, y=flips to completion. Good advice on labeling axes and one I shall heed.

[…] Daily Dose of ExcelA Dick K. looks at a VBA solution to this […]

I had a go at this at: http://newtonexcelbach.wordpress.com/2011/09/15/flipping-coin-problems/

I concluded that:

Maximum flips = n^2 (where n = number of coins)

Minimum flips = n(m+1)-1 (where m is a sequence number, and n = 2^m)