Brian’s Pegboard II

The Problem

Brian has a pegboard with 16 pegs in a 4 by 4 square array (see the diagram).

He also has a piece of string that he wants to put from the top left hand peg A, to the neighbouring peg B, so that it touches all of the other pegs on the way. If the string is never put diagonally between the pegs, how many different ways can Brian string up his pegboard?

Teaching sequence

1. Introduce the idea of a pegboard. Let the class play with one or do some work on one so that they are familiar with the apparatus.
2. Introduce the problem. You might do the problem Pegboard I, Level 3 with them as an introduction. Otherwise start work on the current problem to give them an idea of what has to be done.
3. Let the students work in their groups to solve the problem. You may need to help them to see how to be systematic. If most of the class can only use guess and check, then it is worth gathering them all together to discuss how they might be systematic.
4. Check the progress of each group. Give assistance where needed. Any group that finishes early can try the Extension problem.
5. Get the students to report back to the whole class.
6. Give them time to write up their method of solution.

Extension

Suppose that P is the bottom right hand peg. How many ways can Brian join the string from peg A to peg P so that each peg is used and so that the string is always vertical or horizontal between neighbouring pegs?

Solution

First of all it might be useful if the class has tried Brian’s Pegboard I first (see Statistics, Level 3). It will help them to see how to tackle problems like this. It should be said, though, that one obvious way to begin this problem is to use guess and check. This will lead to a few ideas that can then be woven into a more systematic approach.

The one thing that is worth remembering from that problem is there is only one thing that can happen at the corner squares, other than A.

The secret here is to be systematic. Starting from A we know that we have to go to E, otherwise we hit B and we have finished without most of the pegs on the board. So we have the situation below. (Brian – can you replace the X with circles).

Now there are two ways that Brian might move away from E. He could either go to F or to I. Let’s treat each of these separately. These can be thought of as two branches of a tree diagram.

Case 1, E to F: From the diagram we see that EF forces BC. After all we can’t go in to B from F because we haven’t joined all of the pegs up at this stage. We are also forced to join I to J.

At this point Brian has the following position:

Now notice that J can’t be joined to N. This forces NO to be joined.

At this point there are two possibilities for F. It can join G or J. In each case there is only one stringing that Brian can make. So Case 1 gives us the two possibilities below.

Case 2, E to I:

At this point we can either get into B via C or F. So this gives us two subcases.

Again we can think of this as being two more branches of the earlier tree diagram

Case 2.1, CB:

Now F cannot join B so F has to join both G and J. But there are still two choices for G. It can either go to H or to K. Brian would then get the two situations below in this subcase.

Case 2.2, FC: Using all the old types of argument, this gives the two further stringings below.

Brian can string his pegboard up in six ways.

Solution to the extension:

This is a little sneaky. There is no way that we (or Brian) can join A to p going through all of the other pegs and keeping the string horizontal or vertical between pegs. There are many ways to show this but the quickest is probably to colour the pegs as if they were squares on a chessboard. We show this in the diagram by using xs and os. Now when we join two pegs with string, we are always joining a x to a o. To get from A to P we have to start and end with a x and we have to pass through 16 pegs altogether. You can’t have an alternating sequence of eight xs and eight os that ends in an x!

This raises the question as to which pegs you can string to A and in how many ways you can do it.