Toads$-$and$-$Frogs is a two$-$player game$2$ played on a finite one$-$dimensional array of squares,

each of which may be occupied by a toad $($T $)$ or a frog $($F $).$ Toads move to the left and

frogs move to the right, either by moving into an adjacent vacant square or by jumping over

a creature of the other kind into a vacant square. Unlike pegs in the Peg Jumping game,

creatures that are jumped over remain in their squares. The two players, Left and Right,

alternate moves of toads and frogs respectively, until one player is unable to move and loses.

For example, with starting position F F F xxT T T $,$ Left must move to F F F xT xT T $,$ Right

must move to F F xF T xT T $,$ and then Left has two possible moves, jumping to F F T F xxT T

or moving to F F xF T T xT $.$

$($a$)$ Determine the winner of the game starting at F F xT T under optimal play. $($This is

easy as no player ever has more than one choice.$)$

$($b$)$ Determine the winner of the game starting at F F xxT T under optimal play.

$($c$)$ Determine the winner of the game starting at F F xxxT T under optimal play.

Note: Your solutions must provide justifications as to why they are correct

Note: Parts a and b worth $5$ points together. Easier

Note: Part $($c$)$ Worth $5$ points. Do NOT try $($c$)$ unless you have plenty of spare time.

Solution:

$($a$)$

$($b$)$

$($c$)$

$2$This game, like several others in this section, comes from the book Winning Ways by Berlekamp, Conway,

and Guy.

$9$