How do you know that jumping a frog over a frog, or a toad over a toad, is a bad idea? Naively, it seems to bring you twice as much closer to your goal as a sliding move does. Jim On Fri, Apr 8, 2016 at 11:18 AM, Andy Latto <andy.latto@pobox.com> wrote:
8 moves is the best possible; also the worst possible. N frogs and N toads must each move N+1 spaces, for a total of 2N^2 + 2N spaces. Given any toad and any frog, one jumps over the other once, so there are a total of N^2 moves that move N spaces, while the other moves are all 1 space. So the total number of moves made is 2 N^2 + 2N = N^2 = N^2 + 2N.
Andy
On Wed, Mar 30, 2016 at 11:41 PM, James Propp <jamespropp@gmail.com> wrote:
Come to think of it, I'm not really "done" with the n=2 case; is there a non-brute-force way to see that 8 moves is best possible?
Jim Propp
On Wednesday, March 30, 2016, James Propp <jamespropp@gmail.com> 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.)
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun