A large square with side $n$ is cut into $n^{2}$ small squares with side 1. We want to color each of the $(n+1)^{2}$ vertices of the small squares in red or blue such that each of the small squares has exactly 2 red vertices. How many possible colorings are there?
The answer is $2^{\mathrm{n}+2}-2$. To show this, we start by coloring the $n+1$ highest vertices. There are $2^{n+1}$ ways to do this.
If there exist two consecutive vertices of the same color on the top row ($2^{n+1}-2$ colorings of the top row), then they fix the colors on the row just below, and so on, which gives $2^{n+1}-2$ colorings.
If the colors on the top row are alternating (2 colorings of the top row), then we are forced to alternate the colors on the row below, and on the following rows... However, at each row, we can choose the color with which we start, which gives $2 \times 2^{n}$ colorings, hence $2^{n+2}-2$ in total.

## Exercises of Group A - Statements and Solutions