Problem 44709. Toads and Frogs Puzzle

Created by J. S. Kowontan

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>On a one-dimensional board with n + m + 1 cells, there are n counters in the first n cells representing Toads and m counters in the last m cells representing Frogs. The empty cell is represented by X. For illustration, if n = 4 and m = 3, then the problem is as depicted below:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ T T T T X F F F]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Toads and Frogs take turns moving. Moves consist of sliding a Toad or Frog into the empty cell or jumping over one opposing creature into the empty cell. (Toads cannot jump over themselves and neither can Frogs.) Toads can only move rightward and Frogs can only move leftward.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>What is the total number of moves (i.e. jumps and slides) required for the toads to switch their positions with the frogs as depicted below:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ F F F X T T T T]]></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>ALGORITHM:</w:t></w:r><w:r><w:t> To solve the problem, whenever there is a choice between a slide and a jump, the jump must be made.</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>ILLUSTRATION:</w:t></w:r><w:r><w:t> Consider n = 2 toads and m = 1 frog, then the algorithm could proceed as follows:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ T T X F\n T X T F Slide\n T F T X Jump\n T F X T Slide\n X F T T Jump\n F X T T Slide]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Hence, a total of five moves is required for n = 2 toads and m = 1 frog.</w:t></w:r></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>"}]}

On a one-dimensional board with n + m + 1 cells, there are n counters in the first n cells representing Toads and m counters in the last m cells representing Frogs. The empty cell is represented by X. For illustration, if n = 4 and m = 3, then the problem is as depicted below:<pre> T T T T X F F F</pre>Toads and Frogs take turns moving. Moves consist of sliding a Toad or Frog into the empty cell or jumping over one opposing creature into the empty cell. (Toads cannot jump over themselves and neither can Frogs.) Toads can only move rightward and Frogs can only move leftward.What is the total number of moves (i.e. jumps and slides) required for the toads to switch their positions with the frogs as depicted below:<pre> F F F X T T T T</pre>ALGORITHM: To solve the problem, whenever there is a choice between a slide and a jump, the jump must be made.ILLUSTRATION: Consider n = 2 toads and m = 1 frog, then the algorithm could proceed as follows:<pre> T T X F
 T X T F Slide
 T F T X Jump
 T F X T Slide
 X F T T Jump
 F X T T Slide</pre>Hence, a total of five moves is required for n = 2 toads and m = 1 frog.

On a one-dimensional board with n + m + 1 cells, there are n counters in the first n cells representing Toads and m counters in the last m cells representing Frogs. The empty cell is represented by X. For illustration, if n = 4 and m = 3, then the problem is as depicted below:

T T T T X F F F

Toads and Frogs take turns moving. Moves consist of sliding a Toad or Frog into the empty cell or jumping over one opposing creature into the empty cell. (Toads cannot jump over themselves and neither can Frogs.) Toads can only move rightward and Frogs can only move leftward.

What is the total number of moves (i.e. jumps and slides) required for the toads to switch their positions with the frogs as depicted below:

F F F X T T T T

*ALGORITHM:* To solve the problem, whenever there is a choice between a slide and a jump, the jump must be made.

*ILLUSTRATION:* Consider n = 2 toads and m = 1 frog, then the algorithm could proceed as follows:

T T X F
 T X T F   Slide
 T F T X   Jump
 T F X T   Slide
 X F T T   Jump
 F X T T   Slide

Hence, a total of five moves is required for n = 2 toads and m = 1 frog.

Solve

Solution Stats

33 Solutions
17 Solvers

Last Solution submitted on Mar 16, 2023

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Christian Schröder on 27 Feb 2023 at 9:46

Your description of the game is at odds with your example. In particular, you write that "Toads and Frogs take turns moving", but in your example, in the 3rd and 4th moves, the toads move twice in a row.

Perhaps this is because there is no valid move for the frogs after the third move. However, when moves are skipped when there is no valid move, the game will generally end in unwinnable situations where neither frogs nor toads can make further progress.

Finally, you say that "whenever there is a choice between a slide and a jump, the jump must be made". Assuming that this only refers to the player whose turn it is, this isn't possible: if it's (say) the toads' turn, then a jump is only possible if the board looks like [ ... T F X ... ], and no slide is then possible.

It would be nice if you could clarify what rules are actually supposed to be used for the game.

Problem Recent Solvers17

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 44709. Toads and Frogs Puzzle

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers17

Suggested Problems

More from this Author18

Problem Tags

Community Treasure Hunt

Problem 44709. Toads and Frogs Puzzle

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers17

Suggested Problems

More from this Author18

Problem Tags

Community Treasure Hunt

Players