The question:
Consider the colors red, green, blue. In how many ways can we color the numbers 1 up to including 10 such that:
- 2 consecutive numbers dont have the same color
- 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
Best Answer
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$.