# Coloring the numbers 1 and to including 10 with constraint

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

• No. What if, say $2,6$ are red and the rest are not? – Tavish Jul 4 '20 at 18:53
• 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. – Calvin Lin Jul 4 '20 at 19:16
• @CalvinLin I will do that, thanks! – 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$$.
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\ .$$