Iberoamerican Mathematical Olympiad

Solution:

There must be at least $n - k$ rows without a coin and at least $n - k$ columns without a coin. Let $r_1, r_2, \ldots, r_{n-k}$ be cells in the top row without a coin which are also in a column without a coin. Let $r_1, c_2, c_3, \ldots, c_{n-k}$ be cells in the first column without a coin which are also in a row without a coin. Each of the $2n - 2k - 1$ $r_i$ and $c_j$ are on a different positive diagonal, so we must have $k \geq 2n - 2k - 1$ and hence $k \geq (2n - 1)/3$.

Let $(i, j)$ denote the cell in row $i$, column $j$. For $n = 3m - 1$, put coins in $(m, 1), (m-1, 2), (m-2, 3), \ldots, (1, m)$ and in $(2m-1, m+1), (2m-2, m+2), \ldots, (m+1, 2m-1)$. It is easy to check that this works. For $n = 3m$, put an additional coin in $(2m, 2m)$, it is easy to check that works. For $n = 3m + 1$ we can use the same arrangement as for $3m + 2$.