Coloring 1,2,...,n with rules
Source: Bundeswettbewerb Mathematik 2015 - Round 2 - #3
September 4, 2015
Coloringcombinatoricscounting
Problem Statement
Each of the positive integers is colored in one of the colors red, blue or yellow regarding the following rules:
(1) A Number and the smallest number larger than colored in the same color as always have different parities.
(2) If all colors are used in a coloring, then there is exactly one color, such that the smallest number in that color is even.
Find the number of possible colorings.