Exercise 3. 2016 points are aligned on a line. In how many ways can they be colored red, green, or blue, so that any two adjacent points are of different colors, and each color is used at least once?
Solution to Exercise 3 Let's first find the number of ways to color such that two neighbors have different colors.

For the first point, we have 3 choices. For the next 2015 points, we have 2 choices (since we must avoid using the color of the previous point). This gives a total of $3 \times 2^{2015}$ choices.

We then need to subtract the colorings that use fewer than 3 colors such that two neighbors have different colors. These colorings alternate between two colors and are therefore determined by the colors of the first two points. There are six in total.

The number we are looking for is $3 \times 2^{2015}-6$.

## COMMON EXERCISES