How many ways are there to build a tower of 5 cubes height, out of red, yellow, blue, and green cubes, such that:

Question

How many ways are there to build a tower of 5 cubes height, out of red, yellow, blue, and green cubes, such that at least one of each pair of adjacent cubes is green or blue?

Hey everyone. I first thought about solving this using a recursion relation but then realised it might be better to solve it using the Inclusion-Exclusion principle.

My attempt: Define $A_i$ - there is no blue/green cube among the pair of cubes: cube $i$ and cube $i+1$. $1\le i\le 4$

We are looking for $|\bigcap_{i=1}^4 \overline {A_i}|=|\overline {\bigcup_{i=1}^4 A_i}| $

$|\overline{\bigcup_{i=1}^4 A_i}| $= $4^5-4(2^2)+6(2^3)-4(2^4)+2^5$

where $4^5$ is the number of ways to build the tower without any restraints, etc. Is this correct, am I doing something wrong? Edit: Yes this is indeed not correct and yes I am indeed wrong :)

Thanks in advance.

Answer 1

The approach is good, but two things should be fixed:

• The number of ways to color cubes outside of $i,i+1$ is not considered. E.g., you claim there are $2^2$ ways to color cases where $i,i+1$ are not green/blue. There are $2$ choices for each of cubes $i,i+1$ but also four choices for each of the other three cubes, so there should be $2^24^3$ ways of coloring this case.
• There are two ways in which two pairs of cubes can be colored without green/blue: three consecutive cubes colored not green/blue (your $+6\dots$ term), and two separate pairs colored without green/blue. You don't account for the second type.

Answer 2

Here is another approach: Denote by $a_n$ the number of admissible towers of height $n$. Then we have the recursion $$a_0=1, \quad a_1=4,\qquad a_n=2a_{n-1}+4a_{n-2}\quad(n\geq2)\ .$$ (In order to build an admissible tower of height $n$ begin with a blue or a green cube, and erect on it an admissible tower of height $n-1$; or begin with a red or a yellow cube, top it by a blue or a green cube, and erect on them an admissible tower of height $n-2$.)

The recursion can be solved using the "Master Theorem". One obtains $$a_n={5+3\sqrt{5}\over 10}\bigl(1+\sqrt{5}\bigr)^n +{5-3\sqrt{5}\over 10}\bigl(1-\sqrt{5}\bigr)^n\ .$$ In particular $a_5=416$.