Maths Olympiad Prep

Library / /52 of 63

Combinatorics Difficulty 8.7 Shortlist Prove it Turkey

Some unit squares of the grid 2013×20132013 \times 2013 are marked so that any sub-square 19×1919 \times 19 of the grid consisting of unit squares has at least 21 marked unit squares. What is the minimal possible number of marked unit squares?

Solution

The answer is 233625233625.

Suppose that the centers of unit squares have coordinates (i,j)(i,j), where i=1,2,,2013i = 1,2,\ldots,2013; j=1,2,,2013j = 1,2,\ldots,2013. The unit square with center at (i,j)(i,j) will be denoted by u(i,j)u(i,j). Let the marked unit squares be:
u(19k,19l+1)u(19k, 19l + 1), u(19k,19l+2)u(19k, 19l + 2), where 1k1051 \le k \le 105, 0l1050 \le l \le 105 and
u(m,19n)u(m, 19n), where 1m20131 \le m \le 2013, 1n1051 \le n \le 105.
Then it can be readily seen that the total number of marked unit squares is 233625233625, and any sub-square 19×1919 \times 19 has exactly 2121 marked unit squares.
Let k2k \ge 2 be a positive integer. Now by the method of mathematical induction we show that if any 19×1919 \times 19 sub-square of the grid (19k1)×(19k1)(19k-1) \times (19k-1) has at least 2121 marked unit squares, then the total number of marked unit squares is at least M(k)=(k1)(21k1)M(k) = (k-1)(21k-1).

* k=2k = 2. M(2)=41M(2) = 41. Consider two 19×1919 \times 19 squares: the square consisting all u(k,l)u(k,l), where 1k191 \le k \le 19, 1l191 \le l \le 19 and the square consisting all u(k,l)u(k,l), where 19k3719 \le k \le 37, 19l3719 \le l \le 37. Each of these 19×1919 \times 19 squares contains at least 2121 marked unit squares and their intersection is the unit square u(19,19)u(19, 19). Therefore the total number of marked unit squares is at least 21+211=4121 + 21 - 1 = 41. Done.

* Suppose the statement is correct for a ((19k1)×(19k1))((19k-1) \times (19k-1)) grid AA and consider a ((19(k+1)1)×(19(k+1)1))((19(k+1)-1) \times (19(k+1)-1)) grid BB. Suppose that AA consists of all unit squares u(i,j)u(i,j), where 1i19k+181 \le i \le 19k+18, 1j19k+181 \le j \le 19k+18 and BB consists of all unit squares u(i,j)u(i,j), where 1i19k+181 \le i \le 19k+18, 1j19k+181 \le j \le 19k+18.
Let 19×1919 \times 19 squares UsU_s, s=1,2,,ks = 1,2,\ldots,k; consist of all unit squares u(i,j)u(i,j), where 19ki19k+1819k \le i \le 19k+18, 19s18j19s19s-18 \le j \le 19s and 19×1919 \times 19 squares VtV_t, t=1,2,,kt = 1,2,\ldots,k; consist of all unit squares u(i,j)u(i,j), where 19t18i19t19t-18 \le i \le 19t, 19kj19k+1819k \le j \le 19k+18. Note that the squares UkU_k and VkV_k share a unit square u(19k1,19k1)u(19k-1, 19k-1), all other pairs of UsU_s and VtV_t squares do not share any unit square. Therefore, since the union of kk UsU_s and kk VtV_t squares is a subset of the set BAB-A, the set BAB-A contains at least 212k1=42k121 \cdot 2k-1 = 42k-1 marked squares. Thus, by inductive hypothesis BB contains at least =(k1)(21k1)+42k1=((k+1)1)(21(k+1)1)=(k-1)(21k-1)+42k-1 = ((k+1)-1)(21(k+1)-1). Done. Since M(106)=233625M(106) = 233625 the solution is completed.

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.