Problem

Source: 2010 Indonesia TST stage 2 test 5 p2

Tags: combinatorics



A government’s land with dimensions $n \times n$ are going to be sold in phases. The land is divided into $n^2$ squares with dimension $1 \times 1$. In the first phase, $n$ farmers bought a square, and for each rows and columns there is only one square that is bought by a farmer. After one season, each farmer could buy one more square, with the conditions that the newly-bought square has a common side with the farmer’s land and it hasn’t been bought by other farmers. Determine all values of n such that the government’s land could not be entirely sold within $n$ seasons.