Its 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 youll 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 2n-1 trains of length n. While its 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
There are several levels of depth in this problem:
- Obtaining solutions to the direct questions from the exploration. For example,
there are 16 trains of length 5.
- Seeing patterns in these results. For example, the number of trains doubles
each time the length of the train goes up by 1.
- Working with the idea of finding an algorithm and producing successful
algorithms. See the Results for examples.
- Making convincing arguments and dealing with the idea of what constitutes
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
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.
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. Its 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
When using manipulatives in class, many teachers find its 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 theyre
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
- 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
- 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, "Youre 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
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:
Students spend time out of class working on the rest of the project
on their own. Its 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
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 didnt give a lot of insight into why the
total number of trains of length n would be 2n-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
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
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 doesnt 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
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 didnt start the project with the Warm Up
, you can take a break from trains, work through the Warm Up Problems in detail--including creating an algorithm to produce all the n
numbers that use just 1s and 2s and several proofs that there will be 2n
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:
|Number of cars in the train || 1 || 2 || 3|| 4 || 5 || 6
| Total length of the train || || || || || ||
| 1 || || || || || ||
| 2 || || || || || ||
| 3 || || || || || ||
| 4 || || || || || ||
| 5 || || || || || ||
| 6 || || || || || ||