Raoul colored each cell of a $2017 \times 2017$ grid, using $N$ colors. He managed to do so in such a way that for all $1 \leq i<j \leq 2017$ and $1 \leq k<l \leq 2017$, the cells $C_{i, k}, C_{j, k}$ and $C_{j, l}$ are not all of the same color ($C_{a, b}$ denotes the cell in the $a$-th row and $b$-th column). What is the smallest possible value of $N$?
(Solved by Théodore Fougereux, Arthur Léonard, and Timothée Rocquet)

Let's show that Raoul can use 1009 colors (represented by the numbers $1, 2, \ldots, 1009$). For example, the following coloring works:

| 1 | 1 | 2 | 2 | 3 | 3 | $\cdots$ | 1007 | 1008 | 1008 | 1009 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 1 | 2 | 2 | 3 | 3 |  |  |  | 1008 | 1009 | 1 |
| 2 | 2 | 3 | 3 |  |  |  |  |  | 1009 | 1 |
| 2 | 3 | 3 |  |  |  |  |  |  |  | 1 |
| $\vdots$ |  |  |  |  |  |  |  |  |  | $\vdots$ |
| 1008 |  |  |  |  |  |  |  |  |  | 1007 |
| 1008 | 1009 |  |  |  |  |  |  |  | 1007 | 1007 |
| 1009 | 1009 | 1 | $\cdots$ |  |  |  |  | 1007 | 1007 | 1008 |

Conversely, suppose that 1008 colors suffice. By the pigeonhole principle, at least 4036 cells are colored the same color (since $4035 \times 1008 < 2017^2$), say blue.

Moreover, at most 2017 cells are the rightmost blue cells in their row. Therefore, there are at least 4036 - 2017 = 2019 blue cells that have a blue cell to their right in the same row.

Similarly, at most 2017 cells are the topmost blue cells in their column. Therefore, there are at least $4036 - 2017 = 2019$ blue cells that have a blue cell above them in the same column.

By the pigeonhole principle, there must exist a blue cell that has a blue cell to its right and above it, which contradicts the validity of the coloring.