Discover the Formula for Finding Trains of Any Length | Math Project Help"

[heartless]

Hello math crew!

Here's the problem: http://www2.edc.org/makingmath/mathprojects/trains/trains.asp

just in case somebody doesn't want to click on the above link,

trains:
You can use rods of integer sizes to build "trains" that all share a common length. A "train of length 5" is a row of rods whose combined length is 5. Here are some examples:

Notice that the 1-2-2 train and the 2-1-2 train contain the same rods but are listed separately. If you use identical rods in a different order, this is a separate train.

* How many trains of length 5 are there?
* Come up with a formula for the number of trains of length n. (Assume you have rods of every possible integer length available.) Prove that your formula is correct.
* Come up with an algorithm that will generate all the trains of length n. Now I solved this problem, at least I think I solved it.
A formula for the number of trains of length n will be
a=length of a train
h=how many trains of a given length
2^(a-2) + 2^(a-3) + 2^(a-4)+...+ 2^2 + 2^1 + 2^0 = h
if a > 3
I'm not truly sure, if this formula is right, it works for 4,5,6,7 and seems to work for every length above 7, it doesn't work for lengths 1,2,3 though,
Also I have a problem with an algorithm.
Can anyone help me make one, or at least give some clues ont "how to make a good algorithm?" (eventually you may post some good books on algorithms. I got some books in my eye on algorithms, however still have not enough money or time to read 'em)

thanks for all the help fellows,

 

[AKG]

The formula can be made much simpler. Write out a list of the h values for a = 1, 2, 3, 4, 5, 6, 7, ... There's a very obvious pattern. The idea for the algorithm should follow from the way you think about solving the first problem. Here's a hint: how do you figure out how many ways you can build an n-train if you know how many ways you can build an n-1-train, and n-2-train, ..., a 1-train, (and a 0-train)? Everything about this problem screams "recursion" so your algorithm should be recursive. You should probably end up using some sort of "recursive thinking" to solve the first problem, and you can apply this recursive thinking to figure out your algorithm.

 

[Architeuthis Dux]

Hello!

I am always excited to see people using math to solve problems and come up with formulas and algorithms. It shows that the skills we learn in math class can be applied to real-world situations.

Now, let's take a look at your formula for the number of trains of length n. I can see that you have put a lot of thought into it, but there are a few things we need to consider.

Firstly, let's define a few terms. The formula you have come up with is for the number of "unique" trains of length n, meaning that the order of the rods matters. For example, the train 1-2-2 is different from the train 2-1-2. However, the problem statement doesn't specify that the order matters. So, if we consider the order to be irrelevant, then there would only be one train of length 5 (the 1-1-1-1-1 train), not multiple trains as your formula suggests.

Secondly, your formula seems to work for lengths 4 and above, but as you mentioned, it doesn't work for lengths 1, 2, and 3. This is because for those lengths, there are only a few possible combinations of rods that can make up the train. For example, for a train of length 1, there is only one possible combination (1 rod of length 1). Therefore, your formula needs to be adjusted to account for these special cases.

As for an algorithm, here are some steps you can follow:

1. Start with a train of length n=1, consisting of one rod of length 1.
2. For each additional rod of length 1, add it to the end of the train to create a new train of length n+1.
3. For each additional rod of length 2, insert it at any point in the train to create a new train of length n+1.
4. For each additional rod of length 3, insert it at any point in the train (including between rods) to create a new train of length n+1.
5. Repeat steps 2-4 until you have exhausted all possible combinations of rods for a train of length n.

This algorithm will generate all possible trains of length n, including duplicates. So, you may need to adjust it to remove duplicates if the order of the rods is considered irrelevant.

I hope this helps guide