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

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 :)

• Where does the number $4(2^2)$ come from? – BallBoy Feb 6 '18 at 15:03
• @Y.Forman $4C1$ times $2^2$- for each $A_i$ there are 2 choices available (either red or yellow) for each cube in places i, i+1. Is this not correct? – Noy Perel Feb 6 '18 at 15:06
• Have you checked the result? My instinct tells me that it might be incorrect ;) I mean, compare $4^5$ with your final result... – 57Jimmy Feb 6 '18 at 15:10
• @NoyPerel See the first bullet point in my answer. – BallBoy Feb 6 '18 at 15:12
• @57Jimmy Yeah, it makes no sense then. oops :( – Noy Perel Feb 6 '18 at 15:13

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.
• Thank you very much for your help. I still end up with a result that doesn't make sense though so I guess I still haven't grasp the idea. I ended up with the expression $4^5-4(2^2 4^3)+6(2^3 4^2+2^4 4)-4(2^4 4)+2^5$ – Noy Perel Feb 6 '18 at 15:39
• @NoyPerel There aren't $6$ ways to have two separate pairs, there are only $4$. – BallBoy Feb 6 '18 at 15:42
• Thank you! So is it $4^5-4(2^2 4^3)+(6(2^3 4^2)+4(2^4 4))-4(2^4 4)+2^5$ then? – Noy Perel Feb 6 '18 at 15:53
• @NoyPerel You might also have to fix the three-pairs term, since three pairs can also occur (partially) separately – BallBoy Feb 6 '18 at 15:54
• @NoyPerel I may have misled you... of the 6 double pairs, there are 3 consecutive triples and 3 separate pairs. Of the 4 triple pairs, there are 2 consecutive quadruples and 2 triple/double setups. The answer should be $4^5 - 42^24^3 +(32^34^2+32^44)-(22^44+22^5)+2^5$ – BallBoy Feb 6 '18 at 18:08

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