Zeeshan Quireshi
C# Be Sharp !
A train with n carriages labelled 1, 2, 3, . . . n, in that order, is standing on a railway
track. The railway track has a short siding that can accommodate upto two carriages.*farm2.static.flickr.com/1307/1381345666_c930e068fe_o.png
As you move the train past the siding from left to right, you can do one of the following
at each step.
(i) Move a carriage from the left side to the right side directly.
(ii) Move one or two carriages into the siding, only if the siding is currently empty.
(iii) Move all the carriages out of siding to the right side.
Depending on the sequence of operations you perform, the carriages in the train may
be reordered. For instance, if you start with five carriages 1, 2, 3, 4, 5, you can reorder
this as 1, 4, 2, 3, 5 by keeping 4 in the siding, sending 2 and 3 to the right, then moving
4 out of the siding and finally moving 1 to the right. Similarly, you can generate the
order 1, 3, 4, 2, 5 by keeping 3, 4 in the siding when you move 2 to the right.
Note that you cannot add a carriage to the siding if it is not empty, even if there is only
one carriage currently in the siding. Similarly, if there are two carriages in the siding,
you cannot remove only one of them and move it to the right—you must remove both.
Thus, for example, you cannot generate the order 3, 1, 4, 2, 5. Since 2 is adjacent to 5,
3, 4 must have gone into the siding together, but they have come out separated by 1,
which is not permitted.
Overall, if one tries out all possible ways of using the siding while moving a train with
five carriages, there are 24 different ways in which the carriages can be reordered.
How many different reorderings can you generate if you have a train with:
(a) 8 carriages
(b) 9 carriages
(c) 10 carriages
PS: I really need a solution to this question , i'm preparing for Computing lympiads n i can't solve this particular question n can't find any source on how to solve it .
Also if you can recomend me any books to learn/practice these type of Problem's itll be very helpful.
track. The railway track has a short siding that can accommodate upto two carriages.*farm2.static.flickr.com/1307/1381345666_c930e068fe_o.png
As you move the train past the siding from left to right, you can do one of the following
at each step.
(i) Move a carriage from the left side to the right side directly.
(ii) Move one or two carriages into the siding, only if the siding is currently empty.
(iii) Move all the carriages out of siding to the right side.
Depending on the sequence of operations you perform, the carriages in the train may
be reordered. For instance, if you start with five carriages 1, 2, 3, 4, 5, you can reorder
this as 1, 4, 2, 3, 5 by keeping 4 in the siding, sending 2 and 3 to the right, then moving
4 out of the siding and finally moving 1 to the right. Similarly, you can generate the
order 1, 3, 4, 2, 5 by keeping 3, 4 in the siding when you move 2 to the right.
Note that you cannot add a carriage to the siding if it is not empty, even if there is only
one carriage currently in the siding. Similarly, if there are two carriages in the siding,
you cannot remove only one of them and move it to the right—you must remove both.
Thus, for example, you cannot generate the order 3, 1, 4, 2, 5. Since 2 is adjacent to 5,
3, 4 must have gone into the siding together, but they have come out separated by 1,
which is not permitted.
Overall, if one tries out all possible ways of using the siding while moving a train with
five carriages, there are 24 different ways in which the carriages can be reordered.
How many different reorderings can you generate if you have a train with:
(a) 8 carriages
(b) 9 carriages
(c) 10 carriages
PS: I really need a solution to this question , i'm preparing for Computing lympiads n i can't solve this particular question n can't find any source on how to solve it .
Also if you can recomend me any books to learn/practice these type of Problem's itll be very helpful.