1
$\begingroup$

In how many ways can the four walls of a room be painted with three colours so that no two adjacent walls have the same colour ?


I specifically want to use inclusion exclusion principle. So according to me it should be $$3^4-4\times 3^3+4\times 3^2-3 $$ which is $6$. The correct answer is $18$. Am making a mistake in applying the principle ? I thought like this - Total ways to colour - ways to colour two adjacent walls with same colour + ways to colour three adjacent walls with same colour - ways to colour all four walls with same colour.

$\endgroup$
  • $\begingroup$ Do you have to use all $3$ colors, or is it OK to use only $2$ of them? $\endgroup$ – barak manos Apr 3 '16 at 12:08
  • $\begingroup$ Can use two colours. But haven't these cases been calculated $\endgroup$ – mathemather Apr 3 '16 at 12:19
4
$\begingroup$

If you insist on using the inclusion exclusion principle you can argue as follows:

Denote the vertical edges of the room by $e_i$ $(1\leq i\leq4)$. There are $3^4$ colorings with no restrictions. There are ${4\choose1}\cdot 3^3$ colorings with at least one illegal edge $e_i$, ${4\choose2}\cdot 3^2$ colorings with at least two illegal edges $e_i$, $e_j$, $i<j$, then ${4\choose3}\cdot3^1$ colorings with at least three illegal edges $e_i$, $e_j$, $e_k$, $i<j<k$, and finally ${4\choose4}\cdot 3$ colorings with all four edges certified illegal. The total number of legal colorings then comes to $$3^4-{4\choose1}\cdot 3^3+{4\choose2}\cdot 3^2-{4\choose3}\cdot3^1+{4\choose4}\cdot 3=18\ .$$

$\endgroup$
2
$\begingroup$

A coloring such as AABB has been subtracted twice: once for the pair AA and once for the pair BB. If you add back all such colorings (3 choices of colors X 2 pairs of opposite walls X 2 ways of coloring = 12), you get the correct answer.

$\endgroup$
1
$\begingroup$

See if we use $3$ colours then any one of the two pairs of opposite should have same colour . now total ways of doing so are. Lets use a colour. Say green is used at $1,3$ wall so we have two ways to use $Red,blue$ colours so for $1$ colour used twice its $2$ ways hence for $3$ its $6$ ways. Again think of green used at wall no $2,4$ so again we have $2$ ways to use $red,blue$ so again these are $6$ ways. So total ways are $12$ now using $2$ colours. Lets use green at $1,3$ so now ways of using red are $1$ and same for blue. So for $1$ colour fixed we can use two 1 out of $2$ colours for remaining walls in two ways ie $GRGR,GBGB$ .( assuming walls are identical) . so total ways where $2$ colours are ised is $6$ hence total ways are $6+6+6=18$

$\endgroup$
  • $\begingroup$ I want to use principle of inclusion and exclusion. $\endgroup$ – mathemather Apr 3 '16 at 13:01
  • $\begingroup$ I am not getting why you added ways to colour $3$ adjacent walls with same colour $\endgroup$ – Archis Welankar Apr 3 '16 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.