We claim that the required number is $2016^2 + 1$. Let us first show that we can find an arrangement of $2016^2$ ladybirds and choose their paths so that no two occupy the same square at the same moment in time. We place the ladybirds in the lower left $2016 \times 2016$ square of the board and let them all move in the same manner: up, right, down, left, up, right... We see that no two ladybirds will meet after the first 4

seconds. Since we arrive at the initial position after that, we see that no two ladybirds will ever occupy the same square at the same time.

We now show that, if the board contains $2016^2 + 1$ ladybirds, a collision must occur, regardless of the initial arrangement and the ladybirds' paths.

We label the squares with one of the four labels, $A$, $B$, $C$ and $D$, so that the squares in odd rows alternate between labels $A$ and $B$, while the squares in even rows alternate between $C$ and $D$. We will call a square which has been labelled by $A$ an $A$-square.

Two observations are crucial for our solution. A ladybird occupying a $B$-square or a $C$-square will after one second move to an $A$-square or a $D$-square. Similarly, a ladybird which occupies an $A$-square will after two seconds be sitting in a $D$-square.

The board contains $2016^2 + 1$ ladybirds, so we can assume that at least $1008 \cdot 2016 + 1$ of them occupy an $A$- or a $D$-square. If the opposite were true, we would have at least $1008 \cdot 2016 + 1$ on a $B$-square or a $C$-square, so that after one second we would arrive at the desired situation. Since the number of $D$-squares equals $1008^2$, the $A$-squares contain at least $1008^2 + 1$ ladybirds.

All the ladybirds which are now occupying the $A$-squares will after two seconds move to $D$-squares. This means that there will be at least $1008^2 + 1$ ladybirds on $1008^2$ $D$-squares, so that at least two of them will be in the same square.