The question: Consider the colors red, green, blue. In how many ways can we color the numbers 1 up to including 10 such that:

  1. 2 consecutive numbers dont have the same color
  2. odd numbers cant be red.

My approach: I am going to partition this problem. An even number can be red or not red.
Suppose that 2,4,6,8,10 are red. Then we have $2^5$ different colorings ( odd numbers can be blue v green)
Suppose 2,4,6,8 are red and 10 is not red. Then we have $2^5$ different options again (1,3,5,7,9 are green v blue, 10 is fixed)
Suppose 2,4,6 are red and 8,10 are not red then $2^4$ options
Suppose 2,4 are red and 6,8,10 are not red, then $2^3$ options
Suppose 2 is red, other even numbers not red, then $2^2$ options
Lastly suppose not one even number is red, then $2$ options (1 is blue v green, the others are fixed)
Conclusion: there are $2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1$ different ways (since all the options are different).

Is my approach correct? Thanks in advance

  • $\begingroup$ No. What if, say $2,6$ are red and the rest are not? $\endgroup$ – Tavish Jul 4 '20 at 18:53
  • $\begingroup$ After accounting for the error that Tavish pointed out, i believe that you are on the right track. This casework does yield a solution, though there is a way to combine/simplify all of the casework. If you're stuck on how this can be done, fix up your approach and then mention me. $\endgroup$ – Calvin Lin Jul 4 '20 at 19:16
  • $\begingroup$ @CalvinLin I will do that, thanks! $\endgroup$ – StudDC Jul 4 '20 at 19:28

Let fix the color of 10 to red. If the count of the other red numbers is $n$ there are $2^{n+1}$ ways to color the rest $9-n$ numbers. Taking into account that there are $\binom4n$ ways to choose which of four even numbers are red the overall count is: $$ \sum_{n=0}^4\binom4n2^{n+1}=2(2+1)^4=2\cdot3^4. $$ If we now let the color of 10 to be not red the above number have to be doubled since there is only one alternative (the color "opposite" to the color of 9), i.e. the final answer is $4\cdot3^4$.

  • $\begingroup$ hi, I was wondering how you got to the idea of fixing the color of 10 to red $\endgroup$ – StudDC Jul 5 '20 at 7:26
  • 1
    $\begingroup$ As I start to solve the problem I soon recognized that I need to consider the number 10 differently from the other 4 even numbers and my first intention was to remove it to be able to treat all even numbers in a symmetric way. While writing the answer I decided to fix the color of 10 instead of removing it, as it is equivalent but requires probably less words. $\endgroup$ – user Jul 5 '20 at 7:44

We have to construct admissible words containing $k\geq1$ pairs from the alphabet $\{BR, GR, BG, GB\}$. Denote by $r_k$ the number of such words ending with $R$, and by $x_k$ the number of such words ending with $B$ or $G$. We then have $$r_1=x_1=2\ .$$ I claim that $$r_k=x_k=2\cdot 3^{k-1}\qquad(k\geq1)\ .\tag{1}$$ This follows at once from the recursion $$\left.\eqalign{r_{k+1}=2 r_k+x_k\cr x_{k+1}=2 r_k+x_k\cr}\right\}\qquad(k\geq1)\ .\tag{2}$$ For the proof of $(2)$ note that after an $R$ we can write any pair, but after a $B$ (resp., $G$) we can just write $GR$ or $GB$ (resp., $BR$ or $BG$).

From $(1)$ we conclude that $$n_5:=r_5+x_5=4\cdot 3^4\ .$$


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.