retagged by
4,830 views
20 votes
20 votes

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?

  1. $199$
  2. $683$
  3. $1365$
  4. $3^{10}-2^{10}$
  5. $3^{10}$
retagged by

7 Answers

Best answer
48 votes
48 votes

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).$

edited by
7 votes
7 votes

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.

edited by
1 votes
1 votes

 was one of the option

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

edited by
1 votes
1 votes

$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$

Answer:

Related questions

7 votes
7 votes
2 answers
1
Arjun asked Dec 18, 2018
2,705 views
Consider the integral$$\int^{1}_{0} \frac{x^{300}}{1+x^2+x^3} dx$$What is the value of this integral correct up to two decimal places?$0.00$$0.02$$0.10$$0.33$$1.00$
4 votes
4 votes
2 answers
2
Arjun asked Dec 18, 2018
4,148 views
Which of the following decimal numbers can be exactly represented in binary notation with a finite number of bits ?$0.1$$0.2$$0.4$$0.5$All the above
11 votes
11 votes
5 answers
3
Arjun asked Dec 18, 2018
4,428 views
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?$8$$16$$32$$64$None of the above
5 votes
5 votes
1 answer
4