There must be at least $\mathrm{n}-\mathrm{k}$ rows without a coin and at least $\mathrm{n}-\mathrm{k}$ columns without a coin. Let $\mathrm{r}_{1}$, $\mathrm{r}_{2}, \ldots, \mathrm{r}_{\mathrm{n}-\mathrm{k}}$ be cells in the top row without a coin which are also in a column without a coin. Let $\mathrm{r}_{1}, \mathrm{c}_{2}, \mathrm{c}_{3}, \ldots, \mathrm{c}_{\mathrm{n}-\mathrm{k}}$ be cells in the first column without a coin which are also in a row without a coin. Each of the $2 \mathrm{n}-2 \mathrm{k}-1 \mathrm{r}_{\mathrm{i}}$ and $\mathrm{c}_{\mathrm{j}}$ are on a different positive diagonal, so we must have $\mathrm{k} \geq$ $2 n-2 k-1$ and hence $k \geq(2 n-1) / 3$.

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

!