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

1 votes
1 votes

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)

 

0 votes
0 votes

Let T(n) is the number of ways to color 'n' houses.

 

Task: To find T(10) for 10 houses

1. When one house is painted: no of ways are G or B or R, T(1) -> 3 ways

2. When two houses are painted: no of ways are RG, BG, GB, GG, GR T(2) -> 5 ways 

3When three houses are painted: no of ways are GGB, GGR, GGG, GRG, GBG, RGR, RGB, RGG, BGB, BGR, BGG T(3) -> 11 ways.

 

so, from the above pattern is 3, 5, 11...(till 10th house)

if you look at the pattern you will find it as a famous pattern named Jacobsthal Number 

that is, 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, ……

 

{\displaystyle J_{n}=\left\{\begin{matrix} 0   &   &  if n=0\\1&&ifn=1  \\ J_{n-1} + 2J_{n-2}&&ifn>1  \end{matrix}\right.}

 

so, starting from 3 as the first house and move right till 10th (value) you will find the answer 1365.

therefore by the pattern, we can find the ways to paint 10 houses ie T(10) ways

Answer : T(10) = 1365 ways

edited by
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