0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Where does the number $4(2^2)$ come from? $\endgroup$ – Y. Forman Feb 6 '18 at 15:03
  • $\begingroup$ @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? $\endgroup$ – Noy Perel Feb 6 '18 at 15:06
  • $\begingroup$ Have you checked the result? My instinct tells me that it might be incorrect ;) I mean, compare $4^5$ with your final result... $\endgroup$ – 57Jimmy Feb 6 '18 at 15:10
  • $\begingroup$ @NoyPerel See the first bullet point in my answer. $\endgroup$ – Y. Forman Feb 6 '18 at 15:12
  • $\begingroup$ @57Jimmy Yeah, it makes no sense then. oops :( $\endgroup$ – Noy Perel Feb 6 '18 at 15:13
1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Noy Perel Feb 6 '18 at 15:39
  • $\begingroup$ @NoyPerel There aren't $6$ ways to have two separate pairs, there are only $4$. $\endgroup$ – Y. Forman Feb 6 '18 at 15:42
  • $\begingroup$ 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? $\endgroup$ – Noy Perel Feb 6 '18 at 15:53
  • 1
    $\begingroup$ @NoyPerel You might also have to fix the three-pairs term, since three pairs can also occur (partially) separately $\endgroup$ – Y. Forman Feb 6 '18 at 15:54
  • 1
    $\begingroup$ @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$ $\endgroup$ – Y. Forman Feb 6 '18 at 18:08
2
$\begingroup$

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

$\endgroup$

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.