TIFR CSE 2019 | Part B | Question: 13

Question

A row of $10$ houses has to be painted using the colours red, blue, and green so that each house is a single colour, and any house that is immediately to the right of a red or a blue house must be green. How many ways are there to paint the houses?

• A. $199$
• B. $683$
• C. $1365$
• D. $3^{10}-2^{10}$
• E. $3^{10}$

Comments

How you approached @vegeta?

---

This is by brute force method to understand the concept 

---

we have to paint 10 houses with three colors red, blue and green. so no two red or blue together 

0 red,  0 blue	All green	10C10 = 1
1 red  OR 1 blue	9 green	10C1 * 2=20
2 red  OR 2 blue	8 green	9C2 * 2=72
3 red  OR 3 blue	7 green	8C3 * 2=112
4 red  OR 4 blue	6 green	7C4 *2=70
5 red  OR 5 blue	5 green	6C5 *2=12
1 red AND 1 blue	8 green	9C1 * 8C1=72
1 red AND 2 blue             OR                1 blue AND 2 red	7 green	8C1 * 7C2 * 2=336
1 red AND 3 blue              OR               1 blue AND 3 red	6 green	7C1 * 6C3 * 2=280
1 red AND 4 blue               OR              1 blue AND 4 red	5 green	6C1 * 5C4 * 2=60
2 red AND 2 blue	6 green	7C2 * 5C2=210
2 red AND 3 blue               OR              2 blue AND 3 red	5 green	6C2 * 4C3 * 2=120
TOTAL	=	1365 Ways

 

Answer 1

Let $T(n)$ denote the number of ways to color $'n'$ houses such that house immediately right to the red or the blue is green.

Consider the first house in the row. It can be either red, green or blue. (Dividing the problem into three cases).

Suppose the first house is painted green so for next house, we don't have any condition, It can be painted by using any of the colors,$(R, G \text{ or } B).$

Hence If the first house is green we can paint the rest of the houses in $T(n-1)$ ways.

Suppose the first house is red, then for the next house we don't have any choice, it must be green.

So, if the first house is red, the number of ways of painting the rest of the houses is $T(n-2).$ (excluding the second house).

Same applies if the first house is blue, in that case also in $T(n-2)$ ways we can paint the houses.

Summing up all the mutually exclusive cases,

1. $T(n) = T(n-1) + T(n-2) + T(n-2).$
2. $T(n) = T(n-1) + 2T(n-2).$

Now consider the base case:

If we have $1$ house to paint it can be either red, green or blue. So $T(1)=3.$

For $2$ houses, $GR, GB, GG, BG  \ \text{ (or) }\  RG$ are the $5$ possible ways. So, $T(2)=5.$$$\begin{array}{|l|l|}\hline T(1) & T(2) & T(3) & T(4) & T(5) & T(6) & T(7) & T(8) & T(9) & T(10) \\\hline 3 & 5 & 11 & 21 & 43 & 85 & 171 & 341 & 683 & 1365 \\\hline\end{array}$$

Option $(C).$

Comments

If there is only one house, shouldn't it be green only. If it is red or blue, there house on the immediate right should be green, but there there is no immediate right.

Using this logic, first house in the sequence must always be green.

---

if there is no house at right, why to worry about its color?

---

Got it! Thanks!

---

$T(n) = \left ( \frac{4}{3} \right )2^n - \left ( \frac{1}{3} \right )\left ( -1 \right )^n$

Answer 2

Notice, that every valid sequence of colorings has atleast $5$ Green houses . Why ?

Suppose there are $5$ houses with green color : $\_G\_G\_G\_G\_G\_$

Now, out of the $6$ newly created spaces, $5$ will be chosen and can be painted either red or blue.

This wouldn't work when the number of green houses is $\leq4$.
 

Now suppose all of the $10$ houses are green

$\implies$ Number of ways= Only $1$ possibility.

$9$ houses are green $=\_G\_G\_G\_G\_G\_G\_G\_G\_G\_$ .

From $10$ available spaces $1$ space is chosen , and colored either red or blue

$\implies$ Number of ways=  $10C_1 \times 2=20 $ possibilities.

 

Similarly,

Number of Houses that are Green	Possibilities
10	Only $1$
9	$10C_1 \times 2=20 $
8	$9C_2 \times 2^2=144 $
7	$8C_3 \times 2^3=448$
6	$7C_4 \times 2^4=560$
5	$6C_5 \times 2^5=192$

$\therefore$, Total ways=$1+20+144+448+560+192=1365$ ways.

In short , answer is $\sum_{i=5} ^{10} (i+1)C_{10-i}\times2^{10-i}$

Please comment if there is some confusion or if you notice some error.

Comments

"9 houses are green =_G_G_G_G_G_G_G_G_G_ .From 10 available spaces 1 space is chosen , and colored either red or blue."

What if last house is painted red.. I mean if the configuration is GGGGGGGGGR then it is violating the condition that right of a red painted house must be green.

How to handle this situation? Need help..

---

Last house can be painted red or green , since there is no house after it.

---

Thanks for the reply :) I misinterpreted the question as "after every red or blue house, there must be a green house". I think the correct interpretation is " For every red or blue house if there is a house on right side of it, then it must be green"

Answer 3

 was one of the option

Evaluating similarly, till 6 set and 5 set next, we will get 1365.

Comments

brother please explain a bit

---

These are the possibilities for first 5 houses.

Like if you start with red, next must be Green. After green, next can be RBG.

Same way for starting with green, after green next RBG.

So, you have the total possibilities of first 5 sets for all three colours,  and I just multiplied it with the possibilities in the fifth set results.

---

yes if the option didnt had 1365 than it is clear that the last house cannot be blue or red means it will be green...

and we will have to find the value till T9= 683 answer.

Answer 4

$1)$           

                 ${\color{Blue} {B/}}{\color{Red} {R}}$.                 ${\color{Blue} {B/}}{\color{Red} {R}}$

G ____G____G____G____G____

   ${\color{Blue} {B/}}{\color{Red} {R}}$                     ${\color{Blue} {B/}}{\color{Red} {R}}$               ${\color{Blue} {B/}}{\color{Red} {R}}$

 

$2)$

                 ${\color{Blue} {B/}}{\color{Red} {R}}$.             ${\color{Blue} {B/}}{\color{Red} {R}}$

____G ____G_____G____G____G

${\color{Blue} {B/}}{\color{Red} {R}}$                     ${\color{Blue} {B/}}{\color{Red} {R}}$                ${\color{Blue} {B/}}{\color{Red} {R}}$  

---

So, here total arrangement $2\times 2^{5}=64$

Now, inplace of $B/R$  we can also place Green 

So, total possibility will be $64\times \left (\binom{5}{0}+\binom{5}{1}+\binom{5}{2}+\binom{5}{3}+\binom{5}{4}+\binom{5}{5} \right )=64\times 32=2048$

Comments

@srestha ma'am im having a doubt. We are considering the blank to be either R/B so we are taking $2^5$ , then again if we multiply it with $\binom{5}{0}$ and other terms won't it be counted twice? Like I tried for n=2 the same approach

1. G_ 

2. _G it gives 2x$2^1$ = 4, and if we take combination terms with G's placement, 4x ($\binom{1}{0}$ + $\binom{1}{1}$ ) = 8, but whereas we have just 5 possibility, GB, GR, GG BG, BR ( I guess it's adding GG multiple times)

---

u r tellng ur own stategy of doing

Here, Plz check the pic I have drawn

At first I just G and B/R alternatively

Then secondly I just filled the places of B/R with Green

because GG not make any problem

---

@srestha

Your answer is wrong please update it.

---

this is a WRONG ANSWER, should be updated.

Answer 5

lets break it and make it more simpler...

suppose we had only one house we could have coloured in 3 ways(R|B|G)

now there is restriction if house if of (R|B) than next house should be G.

for two houses it will be : RG|BG|GG|GB|GR = 5ways

for three houses: RG(R|B|G) (3) + BG(R|B|G) (3) + GG(R|B|G) (3) + GBG +GRG = 3+3+3+1+1 =11 ways

similarly, four houses = 21

                five houses = 43

               six houses = 85

                .

               .

                .

              ten houses = 1365 

you can have two recurrence relation : 2Tn-2 + Tn-1 

                                                              or  2Tn-1 + (-1)^(n+1)

 

Answer 6

Complete brute force technique for better understanding !