## Task A-4.5.

On some fields of a $2017 \times 2017$ board, there is one grasshopper; the other fields are empty. The grasshoppers move on the board, never leaving it, according to the following rules. Each grasshopper moves to an adjacent field every second. Movements are horizontal (to the field to the left or right of the one the grasshopper is on) or vertical (to the field above or below the one the grasshopper is on). A grasshopper that makes a horizontal move in one second must make a vertical move in the next second, and a grasshopper that makes a vertical move in one second must make a horizontal move in the next second.

Determine the smallest number of grasshoppers such that, regardless of their initial arrangement and regardless of their movements, we can be sure that at some point two grasshoppers will be on the same field.
## Solution.

We claim that the smallest number of slugs is equal to $2016^{2}+1$. First, we show that there exists an initial position and movement for $2016^{2}$ slugs such that no two slugs will ever be on the same square at any moment. Place the slugs in the lower left $2016 \times 2016$ square of the board and have them all move in the same pattern: up, right, down, left, up, right... We see that in the first 4 steps, no two slugs will be on the same square, and since the pattern repeats every 4 steps, no two slugs will ever be on the same square.

![](https://cdn.mathpix.com/cropped/2024_05_30_9bdde249022d274b7f19g-31.jpg?height=214&width=217&top_left_y=607&top_left_x=925)

Now, we show that if there are $2016^{2}+1$ slugs on the board, regardless of the initial arrangement and movements, some two will be on the same square at some point.

Color the squares of the board in 4 colors, $A, B, C$, and $D$, such that the squares in odd-numbered rows are alternately colored $A$ and $B$, and the squares in even-numbered rows are alternately colored $C$ and $D$. We will refer to a square colored $A$ as an $A$-square.

| $A$ | $B$ | $A$ | $B$ | $A$ | $B$ | A |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $C$ | $D$ | $C$ | $D$ | $C$ | $D$ | $C$ |
| $A$ | $B$ | $A$ | $B$ | $A$ | $B$ | $A$ |
| $C$ | $D$ | $C$ | $D$ | $C$ | $D$ | $C$ |
| $A$ | $B$ | $A$ | $B$ | $A$ | $B$ | $A$ |

The key facts in the solution are as follows. A slug on a $B$-square or a $C$-square will move to an $A$-square or a $D$-square after one step. Additionally, a slug on an $A$-square will move to a $D$-square after two steps.

There are $2016^{2}+1$ slugs on the board, so we can assume that at least $1008 \cdot 2016 + 1$ of them are on $A$-squares or $D$-squares. Otherwise, at least $1008 \cdot 2016 + 1$ of them are on $B$-squares or $C$-squares, and after one step, a larger number of slugs will be on $A$-squares and $D$-squares. Since the number of $D$-squares is $1008^{2}$, at least $1008^{2} + 1$ slugs are on $A$-squares.

All slugs on $A$-squares will move to $D$-squares after two steps, meaning that at least $1008^{2} + 1$ slugs will be on $1008^{2}$ $D$-squares, i.e., some two slugs will be on the same square.