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?
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 1 , r 2 , ... , 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 , ... , 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 © John Scholes jscholes@kalva.demon.co.uk 21 January 2004 Last corrected/updated 21 Jan 04