In Nlogonia, buses and minibuses are 18 and 12 meters long, respectively. Buses can only be green; the minibuses can be blue or red. Two vehicles of the same color are indistinguishable. One of the bridges through which you can enter the city is the Bridge of Recorences, which measures n≥0 meters in length, being n a multiple of 6. But this bridge has only one lane. When someone wants to leave Nlogonia, they need to take another bridge. The Bridge of Recorences can only travel on buses and minibuses. To enter the bridge, a vehicle must always wait until there is room for it to fit completely over it. To leave the bridge and enter the city, a vehicle must wait for the authorization of the royal officer, and, when this happens, the vehicle must leave the bridge completely. Every vehicle that is waiting on the bridge must be positioned as far forward as possible. What is the number of different lines, depending on n, that you can have on the bridge when it is congested (i.e. no more vehicle can fit in it)? Find an open formula and a closed formula for this number, explaining all the steps in your deductions. For example, for n = 30, there are 8 possibilities: either there is a bus followed by a blue minibus, or a bus followed by a red minibus, or a blue minibus followed by a bus, or a minibus. red bus followed by a bus, or one of the 4 possibilities for two minibuses (two red; two blue; one blue followed by a red; one red followed by a blue).
My trials:
n=6 f(n) = 0
n = 12 f(n) = 2
n = 18 f(n) = 3
n = 24 f(n) = 5
n = 30 f(n) = 8
n = 36 f(n) = 9
I didnt found yet some form, if someone could help me.
The recurrences are the following:
\begin{array}{|c|c|} \hline \text{length} & \text{number of ways}\\ \hline 6&0\\ 12&2\\ 18&3\\ 24&5\\ 30&8\\ 36&13\\ 42&21\\ \dots&\dots\\ \hline \end{array}
I differ from you in the case of length 36, therefore i'll describe the 13 possibilities. Call the blue and red mini-buses as 0,1 respectively and the bus as 2. Then there are either (i) 3 minibuses (ii) 1minibus and 1buses (iii)2 buses
(i) There are $2^3=8$ ways to arrange the binary digits 0,1 in 3 places. (for each place, pick one of the options)$\{000,001, 010,011,100,101,110,111\}$. (ii) There are 4 ways to pick a minibus and a bus: $\{02,12,20,21\}$ (iii) There is just 1 way to pick 2 buses: $\{22\}$. Giving us 13 ways.
For the case of length 42, we will construct it recursively. Either the last vehicle is a bus or a minibus. If the last vehicle is a bus, we can fill it up it's slot in 1 way (only 1 type of bus). The rest of the 42-18 = 24m can be filled in f(24) = 5 ways. Similarly if the last vehicle is a minibus (in 2 ways), the rest of the 42 - 12 = 30m can be filled in $f(30)=8$ ways, for a total of $2\times8+5 =21$ ways
Thus our recurrence relation is $f(x) = 2f(x-12)+f(x-18)$
which is an alternate expression for the fibonacci series (after dividing the length by 6).