IMO 1996 SL C2

Origin: UKR | Category: Combinatorics

Problem

An $(n-1) \times (n-1)$ square is divided into $(n-1)^2$ unit squares in the usual manner. Each of the $n^2$ vertices of these squares is to be colored red or blue. Find the number of different colorings such that each unit square has exactly two red vertices. (Two coloring schemes are regarded as different if at least one vertex is colored differently in the two schemes.)

Solution

Let the vertices in the bottom row be assigned an arbitrary coloring, and suppose that some two adjacent vertices receive the same color. The number of such colorings equals $2^{,n-2}$. It is easy to see that then the colors of the remaining vertices get fixed uniquely in order to satisfy the requirement. So in this case there are $2^{,n-2}$ possible colorings.

Next, suppose that the vertices in the bottom row are colored alternately red and blue. There are two such colorings. In this case, the same must hold for every row, and thus we get $2^n$ possible colorings.

It follows that the total number of considered colorings is

$$2^{,n-2} + 2^n = 2^{,n+1} - 2.$$