Problem 986. Penny Flipping: Reverse subsets of a sequence of coins until you recover the original configuration

The original Penny Flipping Problem (PF-1) starts with a stack of N pennies arranged with all the coins heads up. The first operation is to flip the top coin. The second operation is to take the top two coins, invert this substack, and replace the substack on the main stack. The Nth operation is to invert the entire stack. The (N+1) operation is the same as the first operation. This sequence of reversals continues until the stack is returned to an all heads up configuration. Here is the sequence for N=3, with 0 corresponding to heads up and 1 corresponding to heads down:

 0 1 2 3 4 5 6 7 8 9
 0 1 1 1 0 0 1 0 1 0
 0 0 0 1 1 1 0 0 1 0
 0 0 0 0 0 0 1 1 1 0

Nine operations are required to regain the all heads up configuration for N=3. The problem for PF-1 is to find the number of operations to regain all heads up, so PF-1(3) = 9.

Note: Inverting the substack performs two distinct operations on the coins. The orientations of the coins are reversed, and the positions of the coins in the substack are also exchanged across the middle of the substack.

The alternating Penny Flipping Problem (PF-2) is the same as for PF-1 except that successive operations alternate from the top and the bottom of the stack, instead of just from the top, as with PF-1. Here is the PF-2 sequence for N=3:

 0 1 2 3 
 0 1 1 0 
 0 0 1 0 
 0 0 1 0 

So PF-2(3) = 3.

Write a function that returns PF-2(N), for N a positive integer.

I have posted a plot of PF-2 for N=1:50 at this Google link:

coinFlipAlt Plot

Solution Stats

76.92% Correct | 23.08% Incorrect
Last solution submitted on Apr 07, 2015

Problem Comments

Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

MATLAB Academy

New to MATLAB?

Learn MATLAB today!