It’s helpful, before starting this problem in class, to work on it yourself (or with some other teachers), just to get a feel for the likely stumbling blocks. But try not to solve every aspect of it before you start working with students. They learn a lot by watching you work with them.

One thing you’ll want to get straight before bringing this to class is the relationship between the algorithms for generating the trains and the proof that there are 2^n-1 trains of length n. While it’s true that one can prove the formula without an algorithm (we give an example of this in the Results, proofs based on an algorithm are constructive: they show you that something happens by showing you how to make it happen. Read through the Results to see two constructive proofs (based on ways to generate the trains) and one combinatorial proof (that counts the trains without using a method for listing them).

There are several levels of depth in this problem:

1. Obtaining solutions to the direct questions from the exploration. For example, there are 16 trains of length 5.
2. Seeing patterns in these results. For example, the number of trains doubles each time the length of the train goes up by 1.
3. Working with the idea of finding an algorithm and producing successful algorithms. See the Results for examples.
4. Making convincing arguments and dealing with the idea of what constitutes a proof.

In teaching this problem it is important to recognize the level of experience of your students and to establish realistic expectations. But you also want to encourage student attempts to move to the deeper levels when they occur. For example, though many students would have difficulty producing a proof similar to those outlined in the Results, they could be encouraged to try to explain how they knew that their counting method would count every possibility and would not count anything twice. Attempting such explanations in itself helps students grow mathematically and shows them what kind of arguments might be expected in a proof.

Just as there are many levels on which one can approach this problem, there are many ways to approach using it in class. These notes are designed to share ideas and strategies that have worked for teachers in the past.

Day 1

Students of all levels enjoy working on this problem, at least at first, using integer-length rods to build the trains. Cuisenaire rods are ideal. You can also use "Unifix cubes" which snap together to form the lengths necessary. It’s really helpful to have an "overhead companion" for whatever manipulatives you use; there are commercially available transparent plastic Cuisenaire rods, or you can make your own from an overhead transparency and some colored overhead pens.

When using manipulatives in class, many teachers find it’s best to give students five minutes or so just to play with the materials. Letting students play with and explore the materials gets that "out of their systems," so they are then familiar with what they’re using and ready to focus on the problem at hand.

Then get right to the problem. Ask two students to come up to the overhead and to make two different trains of length 5. Beside one of their trains, make a new one that uses the same cars in a different order, and emphasize that this is a different train from the one you started with.

Then turn them loose. If you prefer a little more structure, consider ideas like these:

• You can ask students to organize the rods into piles of equal length, so it will be easy for them to grab rods of the lengths they want.
• Ask students to build a train of rods that has total length 5 on their desks. Give them a minute to complete the task (if some students complete it quickly, ask them to build some other trains with total length 5). Ask students to share their answers, and collect them on the board. Talk about which trains are different--you may have to reiterate that the order of the cars matters.
• Ask the class to predict how many total trains of length 5 are possible. You may want to write some of their predictions on the board to check against later.
• Explain that the first task is for them to find all the possible trains with total length 5. They may want to build them all on the desk, but they should find some way to record the results on paper for future work, for comparing with others, and to turn in. You might ask some students or groups to make their trains on top of an overhead transparency (out of the transparent rods) so you can transfer them to the overhead later.

Most likely, students will think they have found all the possible trains of length 5, but will have an answer like "there are 13 of them." Rather than saying, "You’re missing some, try again," ask them to compare answers with other groups (most likely, the answers will be in the range of 12-16 trains, and students with fewer than 16 will realize they must be missing some). Occasionally, a group of students comes up with more than 16; encourage them to find their duplicates. You can also suggest that they find the total number of trains of length 1, 2, 3, and 4 to see if it follows a pattern, and if their data for length 5 trains fits the pattern.

Leave 5-10 minutes at the end of class to take care of some details:

• Have students share the total number of trains of length 5. They may need to share the exact trains they found in order to figure out which ones are missing from some groups’ lists. The overhead is helpful for this.
• Ask students to explain how they went about the task. How did they organize their trains to make sure that they found them all? How did they know when they were done?
• Ask students to predict how many trains there would be of length 6. Of length 20? Of length n? If students have already solved the problem for smaller numbers of trains, they may have a correct conjecture already. Otherwise, they will be making guesses on just the data for length 5 and will probably not be correct.
• Explain that to finish the project, they need to figure out a formula for how many trains of length n there are, and to find an algorithm for building all of them. Their algorithm for finding all the trains of length n might help them prove that their formula is correct. You may also want to ask for individual write-ups of their in-class work on the length 5 trains.

After Day 1

Where you go after the first day of the project is up to you. Here are some approaches teachers have used in the past:

Finish Individually

Students spend time out of class working on the rest of the project on their own. It’s a good idea to schedule a time to turn in a rough draft. It keeps students focused on the project, rather than leaving everything until the last minute, and lets you see if there are common misconceptions or difficulties that should be dealt with in class.

For example, one teacher found that almost all the students tried to write a direct algorithm (as opposed to recursive) for creating the trains of length n. Their algorithms were quite complicated and hard to follow, and for lengths greater than 4 or 5, produced duplicates or missed trains. In addition, they didn’t give a lot of insight into why the total number of trains of length n would be 2^n-1. The teacher decided to spend a day on the projects in class.

She copied two of the algorithms (removing the students’ names), and asked everyone in class to follow the algorithms exactly to build all the trains of length 6. They then talked about what difficulties they had, what trains were missed, and if they had any duplicates. Then, the teacher worked through the Warm Up Problems on creating numbers using only the digits 1 and 2. She had students work out their own methods and share them. At the end of class, she introduced a tree as a structure for the algorithms many students had just created to solve the problem.

At the end of class, she handed back the rough draft projects, encouraging students to think about a tree-like algorithm for the trains as a way to build up from trains they already knew.

After students turn in their final work on the project as stated, you may want to give them the option of pursuing one of the Extension Problems (or any other extension the class comes up with). If students will not be persisting with an extension to the project, you may want to spend one last day in class, showing a couple of different algorithms (either from students’ work on the project or from the Results, and allowing students to start the investigation of "what if order doesn’t matter." With just a bit of data collection, they will see that patterns are much harder to find in this case. The mathematicians S. Ramanujian and G.H. Hardy worked on this "partition" problem and did indeed produce, using deep methods from number theory, a very complex formula that yielded something close to the number of partitions of n--their formula does not always produce an integer output, but if you round the answer to the nearest integer, you find the number of partitions (see the Resources for more on partitions).

Continuing Group Work

Rather than finishing the work individually, outside of class, you can continue to give students in-class time to work with their groups on this problem and any of the extensions that interest them. Continue to make the Cuisenaire rods available (they are especially helpful for some of the extensions), and ask for occasional write-ups of the work they have completed. The final product can be a group paper or presentation of findings.

Filling In and Coming Back

If you didn’t start the project with the Warm Up Problems, you can take a break from trains, work through the Warm Up Problems in detail--including creating an algorithm to produce all the n-digit numbers that use just 1s and 2s and several proofs that there will be 2ⁿ such numbers.

The Extensions contain some nice activities. The first one may come up while students try to convince each other that they have all the trains of a particular length. Some teachers ask students to fill in a table like this: