Leap Frogs

This seminar is based around one of the animated mathematical problems contained in the “Bright Sparks” component of the site.  These animated problems are based on a mathematical idea and are aimed at extending bright students.  In this seminar we will talk about the mathematics behind Leap Frogs games so that you can help your students if they need it.  

We suggest that you take one of two approaches here.  If you know this problem well, move straight on to ‘B.  Frogs – The Seminar’.  Otherwise you should at least skim through ‘A.  Frogs – The Game’. 

Section A. looks at the basic game and how it is played.  Then it moves into counting the number of moves that are required to mover the frogs where they want to go.  We look at some alternative ways of arriving at a formula for the general pattern and we finish by justifying this pattern. 

On the other hand, section B, lays out the steps you might take and content you might use in a seminar on frogs.  The point that we want to make here is that there is a lot more to this problem than you might expect. 

At the end of this seminar you will find Copymasters for overhead slides that you might find useful. 

A.  Frogs – The Game

1.  Introduction: Frogs is based on a game where 3 frogs on one side of a set of lily pads are trying to interchange places with three frogs on the other side.  You can see this in the picture below.  (It’s also available as Copymaster 1.)

image.

There are essentially two key steps in the overall problem.  First, you have to master the sequence of moves that get the frogs interchanged.  Second, you have to determine the number of moves needed for any number of frogs.  This is quite enough for the average class.  However, if you have a really capable student in your class, they might ask how do you know that this is indeed the fewest number of moves?  And if they don’t ask it then you should ask them

2.  The sequence of moves: First you have to know what moves are possible.  Well, you must keep moving the frogs forward; you can move a frog onto an empty lily pad if there is one in front of it; and you can jump over a frog if there is an empty space on the other side of the frog that is being jumped. 

Below is a sequence of moves that will get six frogs (three on each side) where they want to go.  (GF stands for Green Frogs and BF for Brown Frogs.)

GF3  GF2  GF1          BF1  BF2  BF3

GF3  GF2  GF1  BF1          BF2  BF3

GF3  GF2           BF1  GF1 BF2  BF3

GF3           GF2  BF1  GF1 BF2  BF3

GF3  BF1  GF2           GF1 BF2  BF3

GF3  BF1  GF2  BF2  GF1          BF3

GF3  BF1  GF2  BF2  GF1  BF3         ­

GF3  BF1  GF2  BF2           BF3  GF1

GF3  BF1            BF2  GF2 BF3  GF1

          BF1   GF3  BF2  GF2 BF3  GF1

BF1            GF3  BF2  GF2 BF3  GF1

BF1  BF2   GF3           GF2 BF3  GF1

BF1  BF2   GF3  BF3  GF2          GF1

BF1  BF2   GF3  BF3          GF2  GF1

BF1  BF2            BF3  GF3 GF2  GF1

BF1  BF2   BF3           GF3 GF2  GF1

If you have four frogs on either side the sequence of moves is very similar.  The basic idea is to set up a situation where the green frogs, say, can provide a way of letting the brown frogs jump over them in succession.  There is one key idea here that has to be kept in mind.  That is, that you never want to be in a position where two frogs of the same colour are next to each other.  If you reach that state, then the whole jumping business comes to a halt.  So think ahead to make sure that you don’t get two frogs of the same colour next to each other.

3.  The number of moves: The 3-frogs-a-side problem is non-trivial.  It is not something that most students can solve immediately.  When they do manage to get the frogs interchanged it is well worth asking them to do it again to make sure that they really know the pattern of moves.  The challenge then is to predict the number of moves that it takes to complete the problem with any number of frogs on each side.  To do this it may help to construct a table such as the one below.

no.  of frogs a side

  1

  2

  3

  4

  5

  6

  7 

  8

 

  n

no.  of moves

  3

  8

15

24

35

     

  

   

 

  ?

You might like to fill in the entries for 6, 7 and 8 frogs-a-side or, at the very least, guess what these values might be.

This will be an unusual pattern especially for primary and intermediate students.  It might help to look at it another way.  How many positions (rather than moves) are there during the jumping? If you look at the sequence of moves we gave for three frogs a side above, this will be 16.  The initial position, before any frogs have moved, will be counted as one of the positions.  This leads to a more manageable pattern.  To help to see this, construct a table similar to the one above.  Here we add one to every entry in the second row of the table above.  Is the pattern clearer?

no.  of frogs a side

  1

  2

  3

  4

  5

  6

  7

  8

 

  n

no.  of positions

  4

  9

16

25

36

     

  

   

 

  ?

This certainly looks as if the number of positions is always a square number but what square number? How does it relate to the number of frogs on each side? It seems to be the number of frogs plus one all squared or (n + 1)2.

This means that for n = 6, we should get (6 + 1)2 = 72 = 49.  It wouldn’t be too difficult to check this.

So now we can go back to the number of moves.  The number of moves is one less than the number of positions so the number of moves with n frogs a side must be (n + 1)2 - 1.  Getting this far is a huge step and is essentially the end point of the Leap Frog game.

4.  Alternatives: Students may well see different ways to get the nth term from the first (or second) table.  For instance, they may well see that to go from the first term to the second term you need to add 5; from the second term to the third term you need to add 7; from the third term to the fourth term you need to add 11; and so on.  The number that you add on each time is odd and it’s the next odd number after the last amount that you added on. 

This method is the iterative method of finding the size of a given term.  Its disadvantage is that it is not as easy to get a general (nth) term using this approach.  So if you are looking for the general term then you may need to look at another option.

Another pattern that some students will see is n2 + 2n, despite the fact that it is not so obvious as the first one.  This seems to work just as well as (n + 1)2 - 1.  Why is this so? Can they both be the same?

Let’s do some algebra.

(n + 1)2 -1 = (n2 + 2n + 1) - 1 = n2 + 2n.

So both expressions are the same.  That’s a relief!

5.  What the Bright Sparks game does: The frogs’ game on the web site goes about the counting in an indirect way.  Every time a student successfully completes a swapping of frogs, a toad appears with a bag of money (see Copymaster 2).  This bag contains as many dollars as there are moves.  The students have to realise the significance of the dollar amount to predict what happens with different numbers of frogs.  They are then asked to enter in the general formula to complete the game.

Note that they are not asked to justify their general formula.  However, they are encouraged to tell someone, their teacher (?) how they arrived at the answer.

The rest of Section A is additional material that you may not want to cover.

6.  A Query: How do you know that there’s not a quicker way? How do you know that 3 frogs can’t be done in fewer than 15 moves?

The thing to note first is that, if nothing else, we have shown that the swapping of frogs can be done in 15 moves or less.  Now let’s see if we have to move 15.

Now no frog leaps a frog of the same colour.  To do this two frogs of the same colour would have to be next to each other.  As you have probably seen this always leads to a problem.  The running of the frogs stops when this happens.

So that means that each frog has to move 4 lily pads forward.  There are 6 frogs so altogether 24 lily pads have to be covered.  (Of course this includes repetitions.)

When two frogs of different colours meet a jump takes place.  This covers two lily pads.  There are 9 ‘meetings’ so there are 9 jumps, which means that 18 lily pads are covered by jumps.

Finally, 24 – 18 = 6.  This means that there are 6 lily pads still to be covered.  They can’t be covered by jumps because we have accounted for all of the jumps.  So they must be simple ‘move forwards one lily pad’. 

OK, then there have to be at least 9 jumps and 6 moves forward to give a total of 15 moves.  And that’s the number of moves we made. 

(If we need to we can apply the same sort of argument to 4 frogs a side or more.  So we can justify the table we produced above.)

B.  Frogs – The Seminar

You can present this in several ways.  You can use the Copymasters at the end of this seminar, you can get hold of some toy frogs so that staff can have hands on experience, you can set up a few computers so that they can work with the Leap Frogs directly, or, if you have a data projector available, you could project it on a screen so you can play it collectively.

  1. Play the game – 3 frogs a side: First get the staff used to the problem by actually doing it.  (If this turns out to be too much of a challenge go to the 2 frogs per side game).
  2. What are the things to avoid? Make sure that they see what problems are caused by having two frogs of the same colour next to each other.
  3. How many moves? When they have got the idea of the problem move onto the counting side.
  4. Play the game – 4 frogs a side: This should lead naturally on to the four frog situation.
  5. What are the things to avoid? Once again two frogs together is bad.
  6. How many moves? You will need to count the number of moves.  It’s a good idea to start to record what you are doing by setting up a table or by some other systematic means.
  7. Play the game – 5 frogs a side: Before they actually do this, ask them to predict how many moves are needed.
  8. The pattern? Discuss how you might describe the pattern. 
  9. Is 15 the smallest? At this point it is up to you to decide whether or not you want to go very deeply into the justification that 3 frogs a side can’t be done in fewer than 15 moves.

Copymasters