Problem 2, 2024

A square board of size \(n \times n\) is given, where \(n \geq 2\). The numbers \(1, 2, \dots, n^2\) are written into the \(n^2\) unit cells of the board, one number in each cell, each number used exactly once. Consider all \(2 \times 2\) squares contained entirely inside the board, each of them consisting of four unit cells. For every such square take the largest of the four numbers standing in its cells and write that number down on a sheet of paper. Determine, in terms of \(n\), the smallest possible number of different numbers written on the sheet.