[math-fun] The Dime and Penny Switcheroo
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
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
Back when Kohner was marketing the Hi-Q peg-jumping game, there was a time when then included what they called the "brain buster" puzzle, which was exactly this puzzle, but with 11 holes. You'd start with 5 red pegs and 5 black pegs, and had to swap them. I think the only allowed moved were (1) moving forward one space and (2) jumping forward over one peg of the opposite color. This image shows it pretty well: https://s-media-cache-ak0.pinimg.com/736x/0e/f7/df/0ef7df2ded3da0631ebe21a7e... Tom James Propp writes:
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
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
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
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
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
On Thursday, March 31, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
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.
Are you sure this is the same puzzle? That strategy would result in T T - F F -> T - T F F -> - T T F F -> ?! which is plainly a cul-de-sac. WFL On 4/8/16, James Propp <jamespropp@gmail.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 08/04/2016 16:24, Fred Lunnon wrote:
On Thursday, March 31, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
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.
Are you sure this is the same puzzle? That strategy would result in T T - F F -> T - T F F -> - T T F F -> ?! which is plainly a cul-de-sac.
Well, unless I'm misunderstanding (WW is frequently rather terse) they say what I say they say, but of course you're right. I think what they actually mean is: make the obvious single move with one kind of piece, then switch to the other and *from then on* always move as many as possible. So: T T - F F single move with T: T - T F F as many F moves as possible: T F T - F T F T F - as many T moves as possible: T F - F T - F T F T as many F moves as possible: F - T F T F F T - T as many T moves as possible: F F - T T and I think this works in general. But it isn't what they actually say. -- g
There's still the question of optimality. Last I checked, Andy Latto proposed an argument that I found unconvincing. Were other people convinced? If so, could someone explain to me why you should never jump a frog over a frog or a toad over a toad? Jim Propp On Sunday, April 10, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 08/04/2016 16:24, Fred Lunnon wrote:
On Thursday, March 31, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com>
wrote:
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.
Are you sure this is the same puzzle? That strategy would result in T T - F F -> T - T F F -> - T T F F -> ?! which is plainly a cul-de-sac.
Well, unless I'm misunderstanding (WW is frequently rather terse) they say what I say they say, but of course you're right. I think what they actually mean is: make the obvious single move with one kind of piece, then switch to the other and *from then on* always move as many as possible. So:
T T - F F
single move with T:
T - T F F
as many F moves as possible:
T F T - F T F T F -
as many T moves as possible:
T F - F T - F T F T
as many F moves as possible:
F - T F T F F T - T
as many T moves as possible:
F F - T T
and I think this works in general. But it isn't what they actually say.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Sun, Apr 10, 2016 at 8:28 PM, James Propp <jamespropp@gmail.com> wrote:
There's still the question of optimality. Last I checked, Andy Latto proposed an argument that I found unconvincing. Were other people convinced? If so, could someone explain to me why you should never jump a frog over a frog or a toad over a toad?
If you jump a frog over a frog, then you have two consecutive frogs, with the space behind them. any Toads that still need to pass these frogs will never be able to, so you had better only do this, if at all, at the very end, after all toads have passes all frogs. Since solutions can be time reversed, reversing the directions that toads and frogs move, the same argument shows that if you jump a frog over a frog, you had better do this only at the very beginning, before any frogs have jumped over any toads. (or to put it another way, if you jump a frog over a frog at the very end, after all the toads have passed over all the frogs, you can only do this from a position that is impossible to reach). So jumping frog over frog, or toad over toad, will always get you stuck. (I hadn't included this in my argument, because I hadn't realized it was legal to jump a frog over a frog, but now see that it makes no difference whether it's legal). Andy
Jim Propp
On Sunday, April 10, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 08/04/2016 16:24, Fred Lunnon wrote:
On Thursday, March 31, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com>
wrote:
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.
Are you sure this is the same puzzle? That strategy would result in T T - F F -> T - T F F -> - T T F F -> ?! which is plainly a cul-de-sac.
Well, unless I'm misunderstanding (WW is frequently rather terse) they say what I say they say, but of course you're right. I think what they actually mean is: make the obvious single move with one kind of piece, then switch to the other and *from then on* always move as many as possible. So:
T T - F F
single move with T:
T - T F F
as many F moves as possible:
T F T - F T F T F -
as many T moves as possible:
T F - F T - F T F T
as many F moves as possible:
F - T F T F F T - T
as many T moves as possible:
F F - T T
and I think this works in general. But it isn't what they actually say.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
This makes sense to me now. Thanks! Jim On Sun, Apr 10, 2016 at 11:49 PM, Andy Latto <andy.latto@pobox.com> wrote:
On Sun, Apr 10, 2016 at 8:28 PM, James Propp <jamespropp@gmail.com> wrote:
There's still the question of optimality. Last I checked, Andy Latto proposed an argument that I found unconvincing. Were other people convinced? If so, could someone explain to me why you should never jump a frog over a frog or a toad over a toad?
If you jump a frog over a frog, then you have two consecutive frogs, with the space behind them. any Toads that still need to pass these frogs will never be able to, so you had better only do this, if at all, at the very end, after all toads have passes all frogs. Since solutions can be time reversed, reversing the directions that toads and frogs move, the same argument shows that if you jump a frog over a frog, you had better do this only at the very beginning, before any frogs have jumped over any toads. (or to put it another way, if you jump a frog over a frog at the very end, after all the toads have passed over all the frogs, you can only do this from a position that is impossible to reach). So jumping frog over frog, or toad over toad, will always get you stuck.
(I hadn't included this in my argument, because I hadn't realized it was legal to jump a frog over a frog, but now see that it makes no difference whether it's legal).
Andy
Jim Propp
On Sunday, April 10, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 08/04/2016 16:24, Fred Lunnon wrote:
On Thursday, March 31, 2016, Gareth McCaughan <
gareth.mccaughan@pobox.com>
wrote:
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.
Are you sure this is the same puzzle? That strategy would result in T T - F F -> T - T F F -> - T T F F -> ?! which is plainly a cul-de-sac.
Well, unless I'm misunderstanding (WW is frequently rather terse) they say what I say they say, but of course you're right. I think what they actually mean is: make the obvious single move with one kind of piece, then switch to the other and *from then on* always move as many as possible. So:
T T - F F
single move with T:
T - T F F
as many F moves as possible:
T F T - F T F T F -
as many T moves as possible:
T F - F T - F T F T
as many F moves as possible:
F - T F T F F T - T
as many T moves as possible:
F F - T T
and I think this works in general. But it isn't what they actually say.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ 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
Allow me grab this opportunity to suggest that whenever you could contribute to the OEIS to, well, do just that. If editing OEIS sequences appears tedious/daunting (in fact it is not), I'll offer every help I can. Best regards, jj * Andy Latto <andy.latto@pobox.com> [Apr 11. 2016 14:31]:
On Sun, Apr 10, 2016 at 8:28 PM, James Propp <jamespropp@gmail.com> wrote:
There's still the question of optimality. Last I checked, Andy Latto proposed an argument that I found unconvincing. Were other people convinced? If so, could someone explain to me why you should never jump a frog over a frog or a toad over a toad?
If you jump a frog over a frog, then you have two consecutive frogs, with the space behind them. any Toads that still need to pass these frogs will never be able to, so you had better only do this, if at all, at the very end, after all toads have passes all frogs. Since solutions can be time reversed, reversing the directions that toads and frogs move, the same argument shows that if you jump a frog over a frog, you had better do this only at the very beginning, before any frogs have jumped over any toads. (or to put it another way, if you jump a frog over a frog at the very end, after all the toads have passed over all the frogs, you can only do this from a position that is impossible to reach). So jumping frog over frog, or toad over toad, will always get you stuck.
(I hadn't included this in my argument, because I hadn't realized it was legal to jump a frog over a frog, but now see that it makes no difference whether it's legal).
Andy
Jim Propp [...]
See http://nrich.maths.org/content/00/12/game1/frogs/index.html#/student for a well-done implementation of the toads and frogs puzzle. Jim On Wednesday, April 13, 2016, Joerg Arndt <arndt@jjj.de> wrote:
Allow me grab this opportunity to suggest that whenever you could contribute to the OEIS to, well, do just that.
If editing OEIS sequences appears tedious/daunting (in fact it is not), I'll offer every help I can.
Best regards, jj
* Andy Latto <andy.latto@pobox.com <javascript:;>> [Apr 11. 2016 14:31]:
On Sun, Apr 10, 2016 at 8:28 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
There's still the question of optimality. Last I checked, Andy Latto proposed an argument that I found unconvincing. Were other people convinced? If so, could someone explain to me why you should never jump a frog over a frog or a toad over a toad?
If you jump a frog over a frog, then you have two consecutive frogs, with the space behind them. any Toads that still need to pass these frogs will never be able to, so you had better only do this, if at all, at the very end, after all toads have passes all frogs. Since solutions can be time reversed, reversing the directions that toads and frogs move, the same argument shows that if you jump a frog over a frog, you had better do this only at the very beginning, before any frogs have jumped over any toads. (or to put it another way, if you jump a frog over a frog at the very end, after all the toads have passed over all the frogs, you can only do this from a position that is impossible to reach). So jumping frog over frog, or toad over toad, will always get you stuck.
(I hadn't included this in my argument, because I hadn't realized it was legal to jump a frog over a frog, but now see that it makes no difference whether it's legal).
Andy
Jim Propp [...]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (6)
-
Andy Latto -
Fred Lunnon -
Gareth McCaughan -
James Propp -
Joerg Arndt -
Tom Karzes