Problem 1169

We will demonstrate that such a coloring exists by induction. Let $P_{n}$ be the property "if we place $n$ lines in the plane, then we can color the regions delimited by the lines with two colors in such a way that two adjacent regions are of different colors."

The case $n=1$ is not very complicated: the line separates the plane into two, we color one side red and the other blue.

We assume the property $P_{n}$ and we will place $n+1$ lines in the plane. We start by placing $n$. According to the induction hypothesis, we can color all the regions delimited by these lines in red and blue appropriately. Now place the $(n+1)$-th line, and we will invert all the colors on one side and leave the other side as is. It is easy to convince oneself that the resulting coloring is appropriate.

Solution to Exercise $4$ If $n$ is even, we can easily find a suitable covering. When $n$ is odd, let's show that it is impossible to satisfy the conditions. We color the chessboard with two colors: we color the squares of the first, third, etc. rows blue and the squares of the second, fourth, etc. rows red. There are then $2 n^{2}+n$ red squares and $2 n^{2}+3 n$ blue squares, for a total of $4 n^{2}+4 n$ squares. We will therefore need $2 n^{2}+2 n$ dominoes. There will be $n^{2}+n$ horizontal dominoes and as many vertical ones.

Each vertical domino covers one square of each color. Once the vertical dominoes are placed, there remain $n^{2}$ red squares and $n^{2}+n$ blue squares to be covered by horizontal dominoes. According to the coloring, a horizontal domino covers squares of the same color. Therefore, $n$ must be even. In other words, when $n$ is odd, it will be impossible to cover the chessboard according to the conditions of the statement.

## 2 Advanced: Combinatorics

## 1 First TD