Alan Frank (guided by the hallowed find-the-first-few-terms method) located a relevant OEIS entry: A005563 a(n) = n*(n+2) (or, (n+1)^2 - 1). (Formerly M2720) 209
From R. K. Guy <http://oeis.org/wiki/User:R._K._Guy>, Feb 01 2008: (Start)
This is also the number of moves that it takes n frogs to swap places with n toads on a strip of 2n + 1 squares (or positions, or lilypads) where a move is a single slide or jump, illustrated for n = 2, a(n) = 8 by T T - F F T - T F F T F T - F T F T F - T F - F T - F T F T F - T F T F F T - T F F - T T I was alerted to this by the Holton article, but on consulting Singmaster's sources, I find that the puzzle goes back at least to 1867. Probably the first to publish the number of moves for n of each animal was Edouard Lucas in 1883. (End) The OEIS entry lists several sources: Derek Holton, Math in School, 37 #1 (Jan 2008), 20-22 Edouard Lucas, Recreations Mathematiques, Gauthier-Villars, Vol. 2 (1883) 141-1 <2%20(1883)%20141-14>43. Does either of them give a proof of optimality? (Both are on the short side, so I'd be surprised if they did.) I still don't get why 8 moves is best possible for n=2. I'm sure I could do an exhaustive analysis, but that wouldn't necessarily provide insight. Jim Propp On Thursday, March 31, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun