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.
Problem
Source: III Caucasus Mathematical Olympiad
Tags: combinatorics
19.06.2018 22:54
first let's show that n(n-1) is an upper bound: for each cell we define its value by how many free cells he has neighboring. it's easy to calculate and get that the sum of the total values is: 4n(n-1). every time we place a marble on a cell, the total went down by at least 4, because if we place a marble on a 2 valued cell, its value is decreasing to 0 and it has at least 2 neighboring cells, so for each one of them the value has been decreased by 1. so the total value decreased by 4 and that's clearly the minimum value taken down when placing a marble. so we can place at most 4n(n-1)/4=n(n-1) marbles on the board. we can do it by buliding an inductive example which is pretty easy, i won't show that here.
13.09.2023 17:21
The number of pairs of empty neighbouring cells initially is $2n(n-1)$ (two ways to choose whether neighbourship by row or by column, $n$ ways to choose the row/column and $n-1$ to choose the pair in the already chosen row/column). Each marble decreases this number by at least $2$ (since the problem condition requires the cell to have at least two empty neighbours), so the amount of marbles at the end can be at most $n^2-n$. For a construction, one can put a marble in all cells except those in the left main diagonal as follows: start from the top right corner, then put in the two cells next to it, then put in the next three cells etc. until you reach the cells just above the left main diagonal; then do the same starting from the lower left corner.
03.06.2024 02:52
Alternative construction: firstly put a marble in the top left $(n-1) \times (n-1)$ table as follows: cell on top left, then on the two cells in the diagonal next to the top, then in the three cells, etc. until reaching the bottom right cell of the $(n-1) \times (n-1)$ table. Then on the last row put consecutively marbles on cells $2$, $4$, $\ldots$ and then do the same for the column (of course, in the common cell of the last row and column we do not put a marble more than once). The total number of marbles is $(n-1)^2 + \frac{n}{2} + \frac{n}{2} - 1 = n^2 - n$ for even $n$ and $(n-1)^2 + 2 \cdot \frac{n-1}{2} = n^2-n$ for odd $n$, i.e. $n^2 - n$ for all $n$.