Sofía colours $46$ cells of a $9 \times 9$ board red. If Pedro can find a $2 \times 2$ square from the board that has $3$ or more red cells, he wins; otherwise, Sofía wins. Determine the player with the winning strategy.
Problem
Source:
Tags: pigeonhole principle, ceiling function, geometry, rectangle, Argentina
mathtastic
04.01.2015 21:49
Pedro has a winning strategy. Partition the $9\times 9$ board into nine $3\times 3$ non-overlapping boards. By pigeonhole, one of these boards must contain at least $6$ colored squares. We will examine this board in further detail below. [asy][asy]void draw_circ(pair llc, bool is_black){draw(Circle(llc + (0.5, 0.5), .37)); if (is_black) fill(Circle(llc + (0.5, 0.5), .37));}for (int i=0; i<=3; ++i) {draw((i,0)--(i,3));draw((0,i)--(3,i));} draw((1,0)--(2,0)--(2,1)--(3,1)--(3,2)--(2,2)--(2,3)--(1,3)--(1,2)--(0,2)--(0,1)--(1,1)--(1,0), red+linewidth(2)); label("$a_1$", (0,2), NE); label("$a_2$", (1,2), NE); label("$a_3$", (2,2), NE); label("$a_4$", (0,1), NE); label("$a_5$", (1,1), NE); label("$a_6$", (2,1), NE); label("$a_7$", (0,0), NE); label("$a_8$", (1,0), NE); label("$a_9$", (2,0), NE);[/asy][/asy] Let the value of a square $a_i$ be $1$ if it is colored and $0$ if it is not. The value of a (sub)board is the sum of the values of the squares it contains. We will show that there must exist a $2\times 2$ square with value at least $3$ for all but one possible coloring of the $3\times 3$ subboard. Suppose this $2\times 2$ square does not exist. We have \[\sum_{i=1}^9 a_i\geq 6\] \[a_1+a_2+a_4+a_5\leq 2\] \[a_2+a_3+a_5+a_6\leq 2\] \[a_4+a_5+a_7+a_8\leq 2\] \[a_5+a_6+a_8+a_9\leq 2\] Adding the last four equations gives \[\left(\sum_{i=1}^9 a_i\right)+a_2+a_4+a_6+a_8+3a_5\leq 8.\] But since $\sum_{i=1}^9 a_i\geq 6$ we have \[a_2+a_4+a_6+a_8+3a_5\leq 2.\] It is obvious that the value of $a_5$ must be $0$ since if it was $1$ then $a_2+a_4+a_6+a_8+3a_5> 2$ which we cannot have. Thus at most two of the squares in the set $\{a_2,a_4,a_6,a_8\}$ have value $1$, but if less than two of those squares have value $1$, then it is impossible for $6$ squares in the $3\times 3$ subboard to be colored. Thus exactly two of the squares in the set $\{a_2,a_4,a_6,a_8\}$ have value $1$ and all four corners are colored, but it is obvious that the two squares from the set $\{a_2,a_4,a_6,a_8\}$ cannot be adjacent, so the only way to color $6$ squares on the $3\times 3$ subboard avoiding a $2\times 2$ subboard with value $\geq 3$ is to have two parallel lines that look like this: [asy][asy]void draw_circ(pair llc, bool is_black){draw(Circle(llc + (0.5, 0.5), .37)); if (is_black) fill(Circle(llc + (0.5, 0.5), .37));}for (int i=0; i<=3; ++i) {draw((i,0)--(i,3));draw((0,i)--(3,i));}draw_circ((0, 0), true);draw_circ((0, 1), true);draw_circ((2, 2), true);draw_circ((2, 1), true);draw_circ((0, 2), true);draw_circ((1, 0), false);draw_circ((1, 1), false);draw_circ((1, 2), false);draw_circ((2, 0), true);[/asy][/asy] They can also be rotated, but the two configurations are rotationally equivalent. Also note how since no more squares can be colored, no subboard can contain $7$ colored squares or more. Now, we consider the $3\times 3$ subboard to the right of this one. [asy][asy]void draw_circ(pair llc, bool is_black){draw(Circle(llc + (0.5, 0.5), .37)); if (is_black) fill(Circle(llc + (0.5, 0.5), .37));}for (int i=0; i<=3; ++i) {draw((i,0)--(i,3));draw((0,i)--(6,i));draw((i+3,0)--(i+3,3));}draw_circ((0, 0), true);draw_circ((0, 1), true);draw_circ((2, 2), true);draw_circ((2, 1), true);draw_circ((0, 2), true);draw_circ((1, 0), false);draw_circ((1, 1), false);draw_circ((1, 2), false);draw_circ((2, 0), true); draw((3,0)--(6,0)--(6,3)--(3,3)--(3,0),blue+linewidth(2)); [/asy][/asy] It's easy to see that none of the squares in the left column of this subboard can be colored, and it's easy to see that the maximum number of squares we can color in this subboard is $3$. (Note: it is possible to color $4$, but then the subboard to the right of this one can have value at most $5$ (okay, fine, it can have value $6$ but that is obviously going to guarantee a $2\times 2$ subboard with value $\geq 3$ later because it will have to be oriented sideways.), which gives the three subboards together a value of at most $15$, which is exactly what we will observe otherwise. The argument can be completed for this case separately, but I will not include it here since it is virtually equivalent to the case of $3$, and far more limited.) Thus, out of the remaining seven $3\times 3$ subboards, there must be at least $46-(6+3)=37$ squares colored, so there must be at least two subboards with $6$ squares colored by pigeonhole (since we've already seen no $3\times 3$ subboard can have $7$ colored squares). Each of these $3\times 3$ subboards must be next to a $3\times 3$ subboard with at most $3$ colored squares. Thus we will need at least one more subboard with $3$ colored squares. What will remain is four $3\times 3$ subboards with at least $37-(6+6+3)=22$ colored squares, so by pigeonhole there must be at least two subboards with $6$ squares colored. Since each of these subboards will have to be next to a subboard with at most $3$ squares colored, we will need at least one more subboard with at most $3$ squares colored. What will remain is a single subboard with at least $22-(6+6+3)=7$ squares colored, which, as we have shown already, cannot exist without having a $2\times 2$ subboard with value at least $3$, so Pedro will always win. $\blacksquare$
mathtastic
06.01.2015 01:26
Lemma: If a $3\times 3$ board contains $6$ colored squares, all four corners must be colored. Proof: Label the squares as shown.
Let the value of a square $a_i$ be $1$ if it is colored and $0$ if it is not. The value of a (sub)board is the sum of the values of the squares it contains. Suppose no $2\times 2$ board with value at least $3$ exists. We have \[\sum_{i=1}^9 a_i\geq 6\] \[a_1+a_2+a_4+a_5\leq 2\] \[a_2+a_3+a_5+a_6\leq 2\] \[a_4+a_5+a_7+a_8\leq 2\] \[a_5+a_6+a_8+a_9\leq 2\] Adding the last four equations gives \[\left(\sum_{i=1}^9 a_i\right)+a_2+a_4+a_6+a_8+3a_5\leq 8.\] But since $\sum_{i=1}^9 a_i\geq 6$ we have \[a_2+a_4+a_6+a_8+3a_5\leq 2.\] It is obvious that the value of $a_5$ must be $0$ since if it was $1$ then $a_2+a_4+a_6+a_8+3a_5> 2,$ which we cannot have. Thus at most two of the squares in the set $\{a_2,a_4,a_6,a_8\}$ have value $1$, but if less than two of those squares have value $1$, then it is impossible for $6$ squares in the $3\times 3$ subboard to be colored. Thus exactly two of the squares in the set $\{a_2,a_4,a_6,a_8\}$ have value $1$ and all four corners are colored. $\square$
The even case is trivial after partitioning a $2k\times 2k$ board into $k^2$ $2\times 2$ boards, and noting that each of these can have at most $2$ colored squares
) Proof: We prove the result by induction on $n$. The base case, $n=1$, gives $1\cdot 1=1$, which is obviously correct. Now suppose the result is true for $2k-1$, that is, the maximum number of squares that can be colored on a $(2k-1)\times (2k-1)$ board without having a $2\times 2$ square with value at least $3$ is $(2k-1)\left\lceil\dfrac{2k-1}{2}\right\rceil=(2k-1)(k)$. Now, using this information combined with the first lemma, we must show that the maximum number of squares that can be colored on a $(2k+1)\times (2k+1)$ board without having a $2\times 2$ square with value at least $3$ is $(2k+1)\left\lceil\dfrac{2k+1}{2}\right\rceil=(2k+1)(k+1)$. We do this by partitioning the board into subboards that we can deal with. We can partition it into One $(2k-1)\times (2k-1)$ board $2k-2$ two by two boards One $3\times 3$ board with a missing corner Now we find the maximum number of colored squares that we can place in each of these subboards. By our inductive hypothesis, we can place at most $(2k-1)(k)=2k^2-k$ colored squares in the $(2k-1)\times (2k-1)$ board. Since $2\times 2$ boards can contain at most $2$ colored squares, the $2k-2$ two by two boards can contain at most $4k-4$ colored squares. By the first lemma, if we are to place $6$ colored squares on a $3\times 3$ board, then all four corners must be colored. However, we are missing a corner, so at most $5$ squares can be colored. Combining this information, the maximum number of squares that can be colored on the $2k+1\times 2k+1$ board is $2k^2-k+4k-4+5=2k^2+3k+1=(2k+1)(k+1)=(2k+1)\left\lceil\dfrac{2k+1}{2}\right\rceil$ so the induction is done. $\square$ By the second lemma, the maximum number of colored squares that can be placed on a $9\times 9$ board while avoiding having a $2\times 2$ subboard with at least $3$ squares is equal to $9\left\lceil\dfrac{9}{2}\right\rceil=45$. However, we place $46$ colored squares on the board, so there must exist a $2\times 2$ subboard with at least $3$ colored squares. Thus Pedro has a winning strategy. $\blacksquare$
Dukejukem
06.01.2015 02:31
Here is a generalized solution: We consider the case of an $n \times n$ board. In general, we claim that the maximum number of cells that can be colored red such that there exists no $2 \times 2$ square with three or more red cells is $\frac{n^2}{2}$ for even $n$ and $\frac{n(n + 1)}{2}$ for odd $n.$
First, we consider the case when $n$ is even. If this is so, we can easily partition the board into $\frac{n^2}{4}$ non-overlapping $2 \times 2$ squares (Just start by taking a $2 \times 2$ square in one corner and then keep adding adjacent $2 \times 2$ squares until the entire board is filled). In each of these squares, we can have at most two red cells. Therefore, an upper bound on the number of red cells is $\frac{n^2}{4} \cdot 2 = \frac{n^2}{2}.$
Indeed it is easy to show that this bound is attainable: Just color columns $2, 4, ..., n$ of the board red. Then since each of these $\frac{n}{2}$ columns has $n$ cells, we have a total of $\frac{n}{2} \cdot n = \frac{n^2}{2}$ red cells. In addition, it is easy to see that any $2 \times 2$ square has exactly two red cells. Therefore, we have provided a construction for $\frac{n^2}{2}$ red cells, and we conclude that this is the maximum number that satisfies the desired property. $\blacksquare$
Now, suppose that $n$ is odd. We wish to show that the maximum number of red cells is $\frac{n(n + 1)}{2}.$ First, we provide a construction using this number of cells:
Color columns $1, 3, ..., n$ red. Then there are a total of $\frac{n + 1}{2} \cdot n = \frac{n(n + 1)}{2}$ red cells. In addition, it is easy to see that any $2 \times 2$ square has exactly two red cells. Thus, we have found an explicit construction for an $n \times n$ board with $\frac{n(n + 1)}{2}$ red cells.
Now, suppose, for the sake of contradiction, that there exists an $n \times n$ board with more than $\frac{n(n + 1)}{2}$ red cells. We will show that there exists some $2 \times 2$ square in this board with at least three red cells.
First, remark that columns $1, 3, ..., n$ must have at least, $\frac{n + 3}{2}$ red cells. This is because if remove column $i$ and row $1$ from the $n \times n$ board, where $1 \le i \le n$ is odd, we have divided what remains of the $n \times n$ board into either one or two rectangles with each rectangle having even dimensions. In a similar fashion to what we proved earlier, we can divide each of these rectangles into $2 \times 2$ squares, and conclude that the maximum number of red cells in these rectangles is $\frac{\left(n - 1\right)^2}{2}.$ Since the $n \times n$ board has at more than $\frac{n(n + 1)}{2}$ red cells, there must be at least \[\frac{n(n + 1)}{2} - \frac{\left(n - 1\right)^2}{2} + 1 = \frac{3n + 1}{2}\] red cells in what remains of the board (excluding these one or two rectangles). But what remains of the board is just column $i$ and row $1.$ Therefore, keeping in mind that column $i$ and row $1$ intersect in one cell, it follows by the Pigeonhole Principle that column $i$ must have at least $\frac{n + 3}{2}$ red cells. We will use this result later on.
Now, consider the $2 \times n$ rectangles constituted by columns $1$ and $2$ of the $n \times n$ board, columns $3$ and $4$ of $n \times n$ board, etc., up to columns $n - 2$ and $n - 1$ of the board. We claim that each of these rectangles can have at most $n$ red cells. We prove this as follows:
In each of these $2 \times n$ rectangles, consider the $2 \times (n - 1)$ rectangle obtained by removing the bottom row. In a similar fashion to earlier, we can break up this $2 \times (n - 1)$ rectangle into $\frac{n- 1}{2}$ non-overlapping $2 \times 2$ squares. Since each of these squares can have at most two red cells, we conclude that the $2 \times (n - 1)$ rectangle can have at most $n - 1$ red cells.
Now, either we are done, and the $2 \times n$ rectangle has at most $n$ red cells, or both cells in the bottom row of the $2 \times n$ rectangle are red. If this is the case, then note that neither of the two cells in the second to bottom row of the $2 \times n$ rectangle can be colored red. Then, consider the $2 \times (n - 3)$ rectangle obtained by truncating the bottom three rows of the $2 \times n$ rectangle. By an identical argument to earlier, we conclude that this $2 \times (n - 3)$ rectangle has at most $n - 3$ red cells. Now, adding these $n - 3$ red cells to the two red cells in the bottom row of the $2 \times n$ rectangle, we have $n - 1$ red cells. The only row unaccounted for in the $2 \times n$ rectangle is the third to the bottom. Either this row has two red cells, or we are done (recall that we want to show that there are at most $n$ red cells in the $2 \times n$ rectangle). By continuously applying this argument, we deduce that either we can show the desired result, or in the $2 \times n$ rectangle, the first to the bottom row, third to the bottom row, etc., up to the top row must each have $2$ red cells each, and every other row must have no red cells.
However, if this were the case, then note that each of these columns would have $\frac{n + 1}{2}$ red cells. Since one of these columns is an "odd numbered" column, this contradicts the bound of $\frac{n + 3}{2}$ red cells that we proved earlier. Therefore, we conclude that the case of every other row have $2$ red cells is impossible. It follows that each of these $2 \times n$ rectangles can have at most $n$ red cells.
Now, returning to the main problem, we apply this result to all of the $2 \times n$ rectangles specified earlier. By considering all of these rectangles together, we know that the first $n - 1$ columns of the $n \times n$ board can have at most $\frac{n - 1}{2} \cdot n = \frac{n(n - 1)}{2}$ red cells, where the $\frac{n - 1}{2}$ counts the number of $2 \times n$ rectangles, and $n$ accounts for the maximum number of red cells in each of these rectangles.
Since the last column of the board clearly can have at most $n$ red cells, we find that an upper bound on the number of red cells is \[\frac{n(n - 1)}{2} + n = \frac{n(n + 1)}{2}.\] Since we have already shown that this bound is attainable, we are done. $\square$
Applying this result to the $9 \times 9$ board, we conclude that the maximum number of cells that can be colored red such that there exists no $2 \times 2$ square with at least three red cells is $\frac{9(9 + 1)}{2} = 45 < 46.$ Therefore, it follows that Pedro must win.
Cycle
06.10.2019 16:26
Construct twenty $2\times 2$ squares on the board as shown in the attachment (for visibility, $10$ of these squares are blue and the other $10$ orange). The only cells that are not covered by such a square are the cells marked black. Thus if there are $46$ red cells, at least $41$ of the red cells will lie within a square. Then, by the Pigeonhole Principle, at least one square will contain $3$ red cells, so Pedro always wins.
Attachments:
