On 31/03/2016 04:36, James Propp wrote:
Now that my daughter and I have both solved "The Dime and Penny Switcheroo" (see page 21 of Martin Gardner's "Perplexing Puzzles and Tantalizing Teasers, or google "dime and penny switcheroo"), I'm wondering what the general story is. What if we start with n pennies and n dimes on a strip of length 2n+1? How many moves does it take to switch the pennies and the dimes? More generally, given two arbitrary configurations on the strip of length 2n+1, is there an easy way to determine the minimum number of moves required to turn one into the other? Surely this has been studied. (Is it explained in Winning Ways? I don't have my copy handy.)
It's discussed very briefly in Winning Ways, which makes the assertion that from the standard initial position you just want to alternate between making as many penny moves as possible and making as many dime moves as possible but says nothing about other configurations or about proofs. -- g