Editorialist: Anubhav Dhar
Problem Link: ZIO 2007 Problem 4
Quick Explanation:
-
Let ans_N denote the number of possible orderings for N carriages (with ans_0:= 1).
-
After transporting all the carriages, carriage number 1 may be either in the very front, or there might be one carriage or two carriages in front of carriage 1.
- If the carriage number 1 is in the front, there are ans_{N⎯1} orderings.
- If there is a single carriage before the carriage number 1, we will have \sum\limits_{i = 0}^{N⎯2}ans_i orderings.
- If there are two carriages before carriage number 1, there will be another \sum\limits_{i = 0}^{N⎯3}ans_i orderings.
-
So we have
ans_N = \sum\limits_{i = 0}^{N⎯3}ans_i + \sum\limits_{i = 0}^{N⎯2}ans_i + ans_{N⎯1}
\implies ans_N = \sum\limits_{i = 0}^{N⎯3}ans_i + \sum\limits_{i = 0}^{N⎯1}ans_i
Explanation:
Let ans_N denote the number of different orderings if there are N carriages.
Clearly ans_1=1, only one ordering i.e. ( 1 ) is possible.
Also, we have ans_2 = 2, both (1,2) and (2,1) are possible orderings.
Also, for 0 carriages, we have only one possible ordering, simply ( ), hence we may define ans_0 to be equal to 1.
Observations :
-
After transporting all the carriages, carriage number 1 may be either in the very front, or there might be one carriage or two carriages in front of the first carriage. If we assume that there are more than two carriages before carriage number 1, then the siding must have accommodated more than two carriages at some point of time (WHICH IS NOT PERMITTED), which were moved after transporting carriage number 1.
-
If carriage number 1 is in the beginning and there are a total of N carriages, then we can say that the remaining N ⎯ 1 carriages, i.e. carriage 2 to carriage N, can be ordered in ans_{N⎯1} orderings. In other words, the last N⎯1 carriages may be transported from the left side of the siding to the right side in ans_{N⎯1} ways and then, carriage 1 is placed in the beginning of all other carriages. So, in this case, we have ans_{N⎯1} distinct orderings.
-
Now, what if we have one carriage before carriage 1? Let us say we have the j-th carriage in front of carriage 1, where j > 1. So the only way the j-th carriage ended up in front of carriage 1, is that at some point of time, the j-th carriage occupied the siding, and all the carriages from 1 to j⎯1 were transported, in that sequence, using the main track (since the siding is occupied). Therefore, the only possible ordering of the carriages 1 to j⎯1 is (1, 2, 3, … , j⎯2, j⎯1). After these are transported, carriage j, which was occupying the siding till now, must have been placed in front of all the carriages. So the sequence will look something like
( j, 1, 2, … , j⎯2, j⎯1, … )
So, for each j, only the order of the carriages numbered more than j (i.e carriages j+1 to N) matter. Hence, the number of possible orderings are only due the last N⎯ j carriages (i.e. carriages j+1 to N) , which is ans_{N⎯j} orderings. Now, if j = N, there is only one possible ordering that is (N, 1, 2, … , N ⎯ 1), which is equal to ans_0 (Note that the last carriage is N⎯1 and there is nothing AFTER that, so there is only 1 way to arrange). Since j can be any integer between 2 and N, we have to sum up the values of ans_{N⎯j} for all j. So we have
ans_{N⎯2} + ans_{N⎯3} + \dots + ans_1 + ans_0
Which is,
\sum\limits_{i = 0}^{N⎯2}ans_i -
Now, what if we have two carriages before carriage 1? Notice that these two carriages must have been occupying the siding, when carriage 1 was being transported. Now, we are only allowed to place two consecutive carriages in the siding. So, Let us say we have the j-th and the j+1-th carriage in front of carriage 1, where 1 < j < N. Similar to the previous case, the only way these carriages ended up in front of carriage 1, is that at some point of time, both of these carriages occupied the siding, and all the carriages from 1 to j⎯1 were transported, in that sequence, using the main track (since the siding was already occupied) and again, the only possible ordering of the carriages 1 to j⎯1 is (1, 2, 3, … , j⎯2, j⎯1). After these were transported, carriages j and j+1, which were in the siding, were placed in front of all the other carriages. So the sequence will look something like
( j, j+1, 1, 2, 3, … , j⎯2, j⎯1, … )
So, for each j, only the order of the carriages numbered more than j+1 (i.e. carriages j+2 to N) matter. Therefore for each j \epsilon \{ 2, 3, ... , N⎯1\} the number of possible orderings are only due to the last N ⎯ j ⎯ 1 carriages (i.e. carriages j+2 to N) , that is ans_{N⎯j⎯1} orderings. Now, if j = N⎯1, there is only one possible ordering that is (N⎯1, N, 1, 2, … , N ⎯ 2), which is equal to ans_0. Since j can be any integer between 2 and N⎯1, we will have to sum up the values of ans_{N⎯j⎯1} for all j. So we have
ans_{N⎯3} + ans_{N⎯4} + \dots + ans_1 + ans_0
Which is,
\sum\limits_{i = 0}^{N⎯3}ans_i
Now, putting all these together we have the total number of possible orderings,
ans_N = \sum\limits_{i = 0}^{N⎯3}ans_i + \sum\limits_{i = 0}^{N⎯2}ans_i + ans_{N-1}
\implies ans_N = \sum\limits_{i = 0}^{N⎯3}ans_i + \sum\limits_{i = 0}^{N⎯1}ans_i
To calculate, we can maintain a table containing ans_k and \sum\limits_{i=0}^{k}ans_i for each k ≥ 0. We can update ans_k using the formula, ans_k = \sum\limits_{i=0}^{k-3}ans_i + \sum\limits_{i=0}^{k-1}ans_i ; and \sum\limits_{i = 0}^{k}ans_i simply by adding ans_k to \sum\limits_{i = 0}^{k⎯1}ans_i. Both of these values are equal to 1 for k = 0.
THE TABLE:
| k | ans_k | \sum\limits_{i=0}^{k}ans_i |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 | 2 |
| 2 | 2 | 4 |
| 3 | 5 | 9 |
| 4 | 11 | 20 |
| 5 | 24 | 44 |
| 6 | 53 | 97 |
| 7 | 117 | 214 |
| 8 | 258 | 472 |
| 9 | 569 | 1041 |
| 10 | 1255 | 2296 |
So for this question, we are told only to report ans8, ans9, ans10.
Therefore we have
Answer for Subtask (a) = ans_8= 258,
Answer for Subtask (b) = ans_9= 569,
Answer for Subtask (c) = ans_{10}= 1255.
.