Maths Olympiad Prep

Library / /13 of 15

Combinatorics Difficulty 6.7 National olympiad Prove it Bulgaria

Some of the squares of an n×nn \times n table are mined. In each square the number of the mined squares amongst this square and its neighbors (i.e. those which have common side or vertex with it) is written. Is it always possible to determine which squares are mined if:
a) n=2000n = 2000;
b) n=2007n = 2007?

Solution

We denote the rows by i=1,,ni = 1, \dots, n and the columns by j=1,,nj = 1, \dots, n and let a(i;j)a(i; j) be the number written in the square (i;j)(i; j).

a) No! Consider the table AA where the squares (i;j)(i; j) are mined if and only if ij1(mod3)i \equiv j \equiv 1 \pmod 3 and the table BB where the squares (i;j)(i; j) are mined if and only if ij2(mod3)i \equiv j \equiv 2 \pmod 3. Then all numbers written in the squares of AA and BB are equal to 11 and therefore we can not determine which squares are mined.

b) Yes! We first determine the mined squares in the third row. It is easy to see that the number b(j)b(j) of the mined squares amongst (3;j1)(3; j-1), (3;j)(3; j), (3;j+1)(3; j+1) is equal to a(2;j)a(1;j)a(2; j) - a(1; j). We now compare b(1)b(1) and b(2)b(2) and determine if the square (3;3)(3; 3) is mined. Next we compare b(4)b(4) and b(5)b(5) and decide if (3;6)(3; 6) is mined. The same argument shows which squares amongst (3;9)(3; 9), (3;12)(3; 12), ..., (3;2007)(3; 2007) are mined.

We now compare b(2007)b(2007) and b(2006)b(2006) to decide if the square (3;2005)(3; 2005) is mined, then compare b(2004)b(2004) and b(2003)b(2003) to see if (3;2002)(3; 2002) is mined, etc. We finally know which squares amongst (3;1999)(3; 1999), (3;1996)(3; 1996), ..., (3;1)(3; 1) are mined. Now b(1)b(1) shows if (3;2)(3; 2) is mined, then we compare b(3)b(3) and b(4)b(4) to determine if (3;5)(3; 5) is mined, etc., and find which squares amongst (3;8)(3; 8), (3;11)(3; 11), ..., (3;2006)(3; 2006) are mined. Hence we know row 33.

Analogously we can determine the mined squares in the rows 66, 99, 1212, 1515, ..., 20072007. Using similar argument we can determine the mined squares in the rows 20052005, 20022002, 19991999, ..., 44, 11 and the rows 22, 55, 88, ..., 20062006.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.