Flipping Coin Problems

At Daily Dose of Excel Dick K. looks at a VBA solution to this problem:

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.

Dick’s macro produced this output for 1 to 50 coins:

Flips vs Number of Coins

I thought I’d see if I could come up with a reasonably tidy macro-free solution.  The formula I came up with is:

  • =IF(D$1<$B2,C2,MOD(INDEX(C$2:C$100,C$1+$A2-$B2+2)+1,2))

This treats a zero as a head, and a 1 as a tail.  The formula was entered into cell D2 and copied into D2:I7 (for a 6 coin stack), with numbers 1 to 6 in D1:I1 zeros in A2:A7, 1 to 6 in B2:B7 and zeros in C2:C7 :

First 6 flips

Next cells D2:I7 were copied to D9:I14; =I2 was entered in C9 and copied down to C14; =A2+7 was entered in A9 and copied down to A14, and 1 to 6 entered in B9:B14

Second block of six flips

This block of 6×9 cells (A9:I14) can then be copied down as often as required:

Completed solution for 6 coins

Having done that, I thought I’d try a similar approach in VBA.  Here’s the code:

Sub CoinStack2()
Dim StackA() As Long, NumCoins As Long, Numtails As Long, NumIts As Long
Dim i As Long, j As Long, k As Long, L As Long, ItTable() As Long, NumOut As Long
Const MaxLoops As Long = 1000000

NumOut = 300
ReDim ItTable(1 To NumOut, 1 To 2)

For L = 1 To NumOut
NumCoins = L
ReDim StackA(1 To NumCoins, 1 To NumCoins + 1)
Numtails = 0
NumIts = 0
For i = 1 To MaxLoops
For j = 1 To NumCoins
StackA(j, 1) = StackA(j, NumCoins + 1)
            Next j

For j = 1 To NumCoins
NumIts = NumIts + 1
                For k = 1 To j
StackA(k, j + 1) = (StackA(j - k + 1, j) + 1) Mod 2
Numtails = Numtails - StackA(k, j) + StackA(k, j + 1)
                Next k
For k = j + 1 To NumCoins
StackA(k, j + 1) = StackA(k, j)
                Next k
If Numtails = 0 Then
ItTable(L, 1) = L
ItTable(L, 2) = NumIts
GoTo nextstack
                End If
            Next j
Next i
    Next L
Range("stacka").Resize(L - 1, 2) = ItTable
End Sub

Output for up to 300 coins is shown below:

Number of Iterations vs Number of Coins (click for full size view)

The trend seen in Dick’s graph is continued, in fact the number of flips required to return to all heads is never more than n^2 (where n is the number of coins), but the peaks are more often n^2-1, and the number of points between peaks doesn’t seem to have any clear trend.  Also the trend for the minimum number apparent in the 1-50 coin graph seems to have disappeared.

Correction: Following Mawdo’s comment I had another look at the minimums, and there is a pattern, and it is more regular than the maximums.  For the integers 1,2,3 … m:

  • Coin stacks with (2^m)-1 coins are at a minimum
  • The number of flips required is  ((2^m)-1)(m+1); i.e. number of coins x (m+1)
  • The next stack (with 2^m coins) requires only (2^m)(m+1)-1 flips; i.e. number of coins x (m+1)-1
  • There are no other stacks that require less than (number of coins) x (m+1) flips.

I have added these minimum points to the chart below:

Iterations vs Number of coins with minimum line

This entry was posted in Charts, Excel, VBA and tagged , , . Bookmark the permalink.

2 Responses to Flipping Coin Problems

  1. Mawdo says:

    I like the approch, as great as VBA can be its nice to see solutions that avoid it. Especially considering the amount of support calls where users simply haven’t enavbled macros!
    Without the time (currently) to run this myself can I ask if there any bounding for the minimum as there is for the max? Also do the peaks and troughs appear at any intervlas? Maybe 2^x?

    I’ll try to work it out another time, but a system like this should be able to be modelled as a straight equation where # of flips is a function of the number of coins.

    Thanks, like the blog even if I’m new to it.



  2. dougaj4 says:

    Thanks Mawdo.
    See my correction above.

    Regarding VBA vs no-macro solutions, I think this little problem is a good example of getting a working solution with a small example, then translating it into VBA to deal with problems that would be unwieldy (if not impossible) on the spreadsheet (like the 89,401 iterations required for a 300 coin stack).


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s