Ibero 95/B1 solution

10th Iberoamerican 1995

Problem B1

ABCD is an n x n 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 n x 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 ≥ (2n-1)/3
[so 2m-1 for n = 3m-1, 2m for n = 3m, 2m+1 for n = 3m+1]

Solution

There must be at least n-k rows without a coin and at least n-k columns without a coin. Let r₁, r₂, ... , r_n-k be cells in the top row without a coin which are also in a column without a coin. Let r₁, c₂, c₃, ... , 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 ≥ 2n-2k-1 and hence k ≥ (2n-1)/3.

Let (i,j) denote the cell in row i, col j. For n = 3m-1, put coins in (m,1), (m-1,2), (m-2,3), ... , (1,m) and in (2m-1,m+1), (2m-2,m+2), ... , (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.

10th Ibero 1995