0
$\begingroup$

I have attempted a solution to a beginners programming question which produces what I think is unexpected output. I need a way to validate it and was hoping to do that mathematically.

Problem description: Take a stack of coins all heads up. Upturn/flip the topmost coin 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.

Beginning with 2 coins and increasing the stack by 1 each time the output is:- 3, 9, 11, 24, 35, 28, 31, 80, 60, 121... not quite what I expected.

Any pointers on how best to model this?

Regards, Ian

  • 0
    I confess I expected the number of flips to increase as the stack of coins increases. A stack of 7 coins is 28 flips which surprised me. I think I should modify the question slightly, what I want to be able to do is be able to calculate directly the required number of flips for a given stack size, and to prove it. This would then be the optimised solution rather than a brute force solution (though the original computer problem requires visual output of each flip as part of the solution).2011-09-09

1 Answers 1

2

See http://oeis.org/A089645 and references there.