Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
what had you expected? –  leonbloy Sep 9 '11 at 18:00
    
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). –  Ian Sep 9 '11 at 18:18
add comment

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
Thank you Robert –  Ian May 6 '12 at 12:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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