Cayley 2020 Q5
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.
Cayley Olympiad 2020, Question 5. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: 76
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.
Solution © UK Mathematics Trust, from the Cayley Olympiad 2020 solutions.