$\mathrm{ABCD}$ is an $\mathrm{n} \mathrm{x}$ board. We call a diagonal row of cells a positive diagonal if it is parallel to AC. How many coins must be placed on an $\mathrm{n} x \mathrm{n}$ board such that every cell either has a coin or is in the same row, column or positive diagonal as a coin?

## Answer

smallest integer $\geq(2 n-1) / 3$

[so $2 \mathrm{~m}-1$ for $\mathrm{n}=3 \mathrm{~m}-1,2 \mathrm{~m}$ for $\mathrm{n}=3 \mathrm{~m}, 2 \mathrm{~m}+1$ for $\mathrm{n}=3 \mathrm{~m}+1$ ]
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$.

![](https://cdn.mathpix.com/cropped/2024_05_09_1d234a78607cd781abe6g-24.jpg?height=382&width=374&top_left_y=1945&top_left_x=264)