Problem

Source: III Caucasus Mathematical Olympiad

Tags: combinatorics



Given a positive integer $n>1$. In the cells of an $n\times n$ board, marbles are placed one by one. Initially there are no marbles on the board. A marble could be placed in a free cell neighboring (by side) with at least two cells which are still free. Find the greatest possible number of marbles that could be placed on the board according to these rules.