4. Baron Munchausen placed a horse in some cells of an $N \times N$ board. He claims that no one will find two different $4 \times 4$ squares on this board (with sides along the grid lines) with the same number of horses. For what largest $N$ can his words be true?

#
# Solution:

Answer: $N=7$.

The number of knights in a $4 \times 4$ square can range from 0 to 16, i.e., there are 17 possible variants. The number of $4 \times 4$ squares on an $N \times N$ board is $(N-3)^{2}$ (since the top-left cell of the square can occupy positions from the far left to the fourth from the right horizontally, and the same vertically). To avoid repetitions, the number of squares must be no more than 17, i.e., $(N-3)^{2} \leqslant 17$. Therefore, $N$ cannot be greater than seven, since then $(N-3)^{2} \geqslant(8-3)^{2}=25>17$.

For $N=7$, an example can be constructed as shown on the right (knights are placed in the shaded cells, and the number of knights in each square is indicated in the top-left cell of each $4 \times 4$ square).

| 16 | 15 | 14 | 13 |  |  |  |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 12 | 11 | 10 | 9 |  |  |  |
| 8 | 7 | 6 | 5 |  |  |  |
| 4 | 3 | 2 | 1 |  |  |  |
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |