- #1
heartless
- 220
- 2
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,
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,
Last edited: