5. A ladybird is free to fly between the $1 \times 1$ cells of a $10 \times 10$ square grid. She may begin in any $1 \times 1$ cell of the grid. Every second she flies to a different $1 \times 1$ cell that she has not visited before.
Find the smallest number of cells the ladybird must visit, including her starting cell, so that you can be certain that there is a $2 \times 2$ grid of adjacent cells, each of which she has visited.
Solution
Suppose each $1 \times 1$ cell starts coloured white and when the ladybird visits any cell, including the starting cell, a ladybird symbol is marked in that cell.
We will show that is is possible to have an arrangement of 75 ladybird symbols without a completely filled $2 \times 2$ grid anywhere but that as soon as you have any arrangement of 76 ladybird symbols, there must be a completely filled $2 \times 2$ grid somewhere in the arrangement.
It is possible to find many different arrangements of 75 ladybird symbols such that no $2 \times 2$ grid contains 4 ladybird symbols. For example:
Since it is possible to use 75 ladybird symbols and not complete a $2 \times 2$ grid, the smallest number of cells visited that guarantees a completely filled $2 \times 2$ grid somewhere in the $10 \times 10$ grid must be greater than 75 .
We now show that the smallest number to guarantee a complete $2 \times 2$ grid somewhere in the $10 \times 10$ grid is less than or equal to 76 .
Split the $10 \times 10$ grid into 25 separate $2 \times 2$ grids.
The maximum number of symbols that these 25 separate $2 \times 2$ grids can hold without any of them being completely filled is $25 \times 3$, which is 75 ladybird symbols. So any attempt to insert 76 ladybird symbols into the $10 \times 10$ grid must completely fill one of these $2 \times 2$ grids.
Therefore, 76 is the smallest number of cells visited that guarantees a complete $2 \times 2$ grid somewhere.