GO Classes Scholarship 2023 | Test | Question: 13

Answer 1

The recurrence relation for $\text{T}_{n}$ will be:
$$
\text{T}_{n}=2 \text{T}_{n-1}+2 \text{T}_{n-3}
$$
So, Since initial conditions are already given,
$$
\text{T}_{4}=28 ; \text{T}_{5}=66 ; \text{T}_{6}=156 ; \text{T}_{7}=368.
$$

Watch Complete Recurrence Relations in Discrete Mathematics  Complete Playlist to understand the concept:

https://youtube.com/playlist?list=PLIPZ2_p3RNHhhTH0o1JBMgscMUvxs4E_4

Comments

Since, base cases are already given we'll directly move to discuss what will happen at $n^{th}$ position.

There are only two cases possible for $n^{th}$ position –

Case $1$ :– Parked car is not a truck.

Two options are available for $n^{th}$ position ie sedan or SUV can be parked at $n^{th}$ position. Now for the remaining $(n-1)$ positions we can park in $T_{n-1}$ ways.

$\therefore$ Number of ways to park = $2 * T_{n-1}$.

Case $2$ :– Parked car is a truck.

Truck takes $n^{th}$ and $(n-1)^{th}$ position. Now as per given conditions we cannot park another truck at $(n-2)^{th}$ position. Like case $1$, two options are available for $(n-2)^{th}$ position ie sedan or SUV can be parked at $(n-2)^{th}$ position. Now for the remaining $(n-3)$ positions we can park in $T_{n-3}$ ways.

$\therefore$ Number of ways to park = $2 * T_{n-3}$.

Therefore, recurrence relation for $T_n$ is $2 * T_{n-1} + 2 * T_{n-3}$.

Answer 2

Let me try to explain this : 

_ _ _ _ nth: this is what we want to find.

---

T(n) → Truck at nth place: 

                    → Now we don't want a truck to be there at n-2th place because (n -2, n - 1) will be occupied by that truck

                    → So, we have 2 options: ………. SUV(n-2) (Truck at nth & n-1th place) or ………………….sedan(n-2) (Truck at nth & n - 1th place) that’s why we say { 2* T(n – 3)}

       → No truck at nth place: Whatever be the arrangement of everything beyond the nth place 

                     → …...sedan (SUV) or …….SUV (sedan) that’s we say { 2 * T(n-1) } 

Which will result in total of T(n) = 2*T(n-1) + 2*T(n-3).

Comments

@Udhay_Brahmi bro there is a typo 

So, we have 2 options: ……….sedan SUV (Truck at nth & n+1th place) or ………………….SUV sedan (Truck at nth & n + 1th place) that’s why we say { 2* T(n – 3)}                                                                                                                                                                       

                                                                                                    *  here it should be n-1                                                          *  here it should be n-1

---

@Udhay_Brahmi in the second line u took last place as nth place and not (n+1)^th place

 

---

Which line ??

---

@Udhay_Brahmi this one

---

@jiren : Why do we take (n +1) instead of n ?

Our main concern is to calculate T(n) not T(n+1) ??

 

---

U took right

Truck at nth and n+1th place

---

@Udhay_Brahmi your solution is wrong.

First of all we have only $n$ places, and you're using $(n+1)^{th}$.

Now, suppose what you say is True.

Then as per you, $T(1)$ should be $3$ that is either you'll park $sedan$ at $1^{st}$ position or you'll park $SUV$ at $1^{st}$ position or you'll park $truck$ at $n^{th} = 1^{st}$ and $(n+1)^{th} = 2^{nd}$ position.

Which is wrong for all the right reasons.

---

Corrected:  have a look @shishir__roy

---

@Udhay_Brahmi bro correct this line too

From

Now we don't want a truck to be there at n-2th place because (n -2, n - 1) will be occupied by that truck

To

Now we don't want a truck to be there at n-2th place because (n -1, n ) will be occupied by that truck

---

We both are looking differently at this line :

T1 = Truck 1

T2 = Truck 2

WHAT I THINK : CONTRADICTION METHOD

……. T1(n-2), T(n-1) [Truck 2 is not possible here, that's why T1 should not be there at (n-2)]

WHAT YOU THINK : 

……..(T1 not possible here) T2 T2

 

So, we both r right.

 @jiren, have a look & let me know if everything is making sense to u or not ?

---

@Udhay_Brahmi bro what about Nth position

why u left Nth place 

u said truck is at Nth place so T(n,n-1) should be occupied by truck right

---

@jiren and @Udhay_Brahmi since both of you are very invested in this question, can you guys give the recurrence relation for the above question if the condition that "no two trucks are consecutively parked" is removed and the value of $T_7$.

(No need to write long description, simply stating result would suffice)

This should be a nice exercise for all of us.

---

@shishir__roy bro im getting 409

see this 

---

@jiren nice, I'm also getting same $408$.

just recheck your calculations for $T_7$.

---

@shishir__roy yeah I wrote 71 instead of 70 in T(7) my bad 😅

Answer should be 408