On a contour map of Russia, there are 85 regions. Vovochka wants to paint each region in white, blue, or red so that white and red do not share a common border. At the same time, one or even two colors can be unused. Prove that the number of such coloring options is odd.
Problem 922
Official solution
For each coloring option that includes at least one region in white or red, we can assign a pair: a coloring option where all white regions are repainted red and all red regions are repainted white. In this case, the option will change, but white and red colors will still not be adjacent.
Thus, the number of coloring options that include at least one region in white or red is even, as they all break down into pairs! There is one more option where all regions of Russia are painted blue. Therefore, the total number of colorings is odd.