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

Created by Everett Rubel

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 0 1 2 3 4 5 6 7 8 9\n -------------------\n 0 1 1 1 0 0 1 0 1 0\n 0 0 0 1 1 1 0 0 1 0\n 0 0 0 0 0 0 1 1 1 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Note:</w:t></w:r><w:r><w:t> 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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 0 1 2 3 \n -------\n 0 1 1 0 \n 0 0 1 0 \n 0 0 1 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So PF-2(3) = 3.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Write a function that returns PF-2(N), for N a positive integer.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>I have posted a plot of PF-2 for N=1:50 at this Google link:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"https://picasaweb.google.com/115436881097292918347/Matlab#5798055972168308562\"><w:r><w:t>coinFlipAlt Plot</w:t></w:r></w:hyperlink></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

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:<pre> 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</pre>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:<pre> 0 1 2 3 
 -------
 0 1 1 0 
 0 0 1 0 
 0 0 1 0 </pre>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:<a href="https://picasaweb.google.com/115436881097292918347/Matlab#5798055972168308562">coinFlipAlt Plot</a>

Solve

Solution Stats

18 Solutions
10 Solvers

Last Solution submitted on Jul 21, 2020

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

Jean-Marie Sainthillier on 16 Oct 2012

I don't understand the first description. For me we obtain :
0 1 2 3 4 5 6
-------------
0 1 0 1 0 1 0
0 0 1 0 0 1 0
0 0 0 1 1 1 0

So so PF-1(3) = 6.
Did I miss something ?

Everett Rubel on 18 Oct 2012

Jean-Marie: I think the phrase, "invert the substack" is the issue. For me, this means to take the substack and invert it as a unit. The coins exchange positions in the substack as well as inverting their values. It is a single physical action that translates into two separate operations on the coins. I may have done better to write, "flip the substack as a unit."

Jean-Marie Sainthillier on 24 Oct 2012

Thank you Everett.
Now I understand the second operation, but not the Nth operation (in the example) when you invert all the stack. It's OK between steps 5 and 6 and between steps 8 and 9, but not between steps 2 and 3 (1 0 0 -> 0 1 1 ?).

Everett Rubel on 25 Oct 2012

Jean-Marie: The transformation between steps 2 and 3 (1 0 0 -> 1 1 0) is the same as for the one between steps 8 and 9; we are working with the entire stack of 3 coins. The first/top coin exchanges with the last/bottom coin and then all coins change their orientation.

Rafael S.T. Vieira on 21 Jul 2020

Every i-th step, imagine that we are picking the top i-coins with our fingers and fliping them upside down. That's FP-1. FP-2 does similar, but, instead of always picking the top i-coins, it alternates between top i-coins and bottom i+1-coins.

Problem Recent Solvers10

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!