Let’s look at a couple strategies for solving the Warm Up Problems. These may
give you some ideas for Trains.
Algorithm 1: A Tree Suppose you’re trying to build all the ndigit numbers that use
only 1s and 2s. The idea is to start with onedigit numbers and build up from there. The
one digit numbers are easy: 1 and 2.
To get the 2digit numbers, you can either stick a 1 or a 2 onto the end of the existing
onedigit numbers. To get the 3digit numbers, you can either stick a 1 or a 2 onto the
end of the existing twodigit numbers.
And so on. You can move systematically down this tree. Each time you move to the
left, add a 1 to the end of your number. Each time you move to the right, add a 2 to the
end of your number.
Important things to prove: At any level in the tree, you have all the numbers you
want (there aren’t any missing), and you don’t have any duplications. Also, how does
this algorithm help you find the total number of ndigit numbers using only 1s and
2s?
Algorithm 2: Fill in the Gap Suppose you successfully found all the (n  1)digit
numbers that use only 1s and 2s. Now think about an ndigit number. It must start with
either a 1 or a 2, and then it’s followed by an (n  1)digit number. If you have a
complete list of those, you’re done.
