Every cell of $100\times 100$ table is colored black or white. Every cell on table border is black. It is known, that in every $2\times 2$ square there are cells of two colors. Prove, that exist $2\times 2$ square that is colored in chess order.
Problem
Source: All Russian Olympiad 2017,Day2,grade 9,P8
Tags: combinatorics
MellowMelon
03.05.2017 18:25
The solution to this problem is basically identical to what I posted in this topic: http://artofproblemsolving.com/community/c6h598767p3556556
math90
04.05.2017 10:48
We generalize it to $n$ even. Assume for contradiction that there doesn't exist $2\times 2$ square that is colored in chess order.
Call a pair of adjacent squares 'colorful' if it contains squares of both colors. The assumption implies that every $2\times 2$ square contains exactly $2$ colorful pairs. Since there are no colorful pairs in the border, every colorful pair is in exactly two $2\times 2$ squares. Hence there are exactly $(n-1)^2$ colorful pairs in the square. On the other hand, each column starts with a black unit and ends with a black unit. Hence it contains an even number of colorful pairs, and similarly for rows. Hence the total number of colorful pairs is even. But $(n-1)^2$ is odd, contradiction.
phymaths
10.09.2017 09:42
Beautiful Problem! Call a $2\times 2$ square $ good$ if it follows chessboard colouring and $bad$ otherwise. We assume on the contrary that there is no such $good$ square with Squares in chess order. Let us consider number of $black-white$ pairs occurring in adjacent cells. Observe any $bad$ square has $2$ such pairs. Double Counting Number of Such pairs finishes the problem. Therefore we have $99^2\times 2 /2$ such pairs since each pair appears in $2$ bad squares. On the other hand, Notice that Every row and column has to give an Even number of pairs.Since the first and last square in Each row and column have the same colour that is Black.(Borders give $0$ pairs).Thus we have an even number of Pairs. $99^2 $being odd gives us the desired contradiction ! Remark: It works for any even $n$.
Delray
10.01.2018 20:56
Call an edge split if it borders two cells of opposing colors, and call a square whose cells are colored in a chess board fashion to be good. For sake of contradiction, suppose that there are no good squares on the board. It is easy to check that every $2\times2$ square in this case will produce exactly two split edges. There are a total of $99^2$ two by two squares on a $100\times100$ board, so we have $2(99^2)$ total split edges. However each split edge is counted twice, as it is contained within two two by two squares, so we must divide by two, and yielding $99^2$ split edges.
Note however that the first and last cells of each row and column are black. This means that every "block" of consecutive white cells will contribute two split edges. Hence each row and column contributes an even number of split edges. Summing over all rows and columns yields an even total number of split edges. However this contradicts there being $99^2$ split edges, and so we see that it is impossible for there to be no good squares. $\square$
HKIS200543
14.08.2020 13:00
Same solution as posted earlier. Suppose for the sake of contradiction that there is no $2 \times 2$ square coloured in chess order. Call n unit segment a \textit{border} if it is in between two cells of opposite colour. In each $2 \times 2$ square there are precisely two border segments. (We only count internally). Each segment is counted in two distinct $2 \times 2$ squares, so summing over all the $99^2$ $2 \times 2$ squares gives that there are $99^2$ border segments. However, because all the cells are coloured black on the table's border, it follows that each row and column has an even number of border segments. $99^2$ is odd, so contradiction.
554183
20.07.2021 14:39
........
guptaamitu1
16.03.2022 16:56
Here's a different (but longer) solution. Call a coloring with all cells on borders having the same color with no $2 \times 2$ square colored in chess order, bad. Assume contrary that a bad coloring exists. We more generally show contradiction for $2n \times 2n$ table ($n \in \mathbb Z_{>0}$), by induction on $n$. Base case $n=1$ is direct. We do the induction step now. Instead of the colors red, white; we will be considering red and blue. Suppose all cells on the border are red. Among all bad colorings, pick the one (which is $\mathcal P$ say), maximizing the number of green cells on inner (where inner border is shown below in green): [asy][asy] size(200); for(int i=1;i<9;++i){ fill(shift(1,i)*unitsquare,red+white); fill(shift(i,1)*unitsquare,red+white); fill(shift(8,i)*unitsquare,red+white); fill(shift(i,8)*unitsquare,red+white); } for(int i=1;i<10;++i){ draw((1,i)--(9,i)); draw((i,1)--(i,9)); } draw((2.5,2.5)--(7.5,2.5)--(7.5,7.5)--(2.5,7.5)--(2.5,2.5),green+linewidth(0.9)); [/asy][/asy] The $\textbf{Key Claim}$ is that: $$\boxed{\text{All squares in the inner border of } \mathcal P \text{ are blue.}} $$If this is true, we are just done by induction hypothesis. So assume on the contrary that statement isn't true. $\textbf{Claim 1:}$ Suppose we have a configuration like below such that changing color of $2$ from red to blue gives a contradiction. [asy][asy] size(100); for(int i =1;i < 4;++i){ fill(shift(1,i)*unitsquare,red+white); } fill(shift(2,2)*unitsquare,red+white); for(int i=1;i<5;++i){ draw((1,i)--(4,i)); draw((i,1)--(i,4)); } label("$1$",(2.5,1.5)); label("$2$",(2.5,2.5)); label("$3$",(2.5,3.5)); label("$4$",(3.5,1.5)); label("$5$",(3.5,2.5)); label("$6$",(3.5,3.5)); [/asy][/asy] Then color of $1,3,4,5,6$ must be blue, i.e. we must have [asy][asy] size(100); for(int i =1;i < 4;++i){ fill(shift(1,i)*unitsquare,red+white); } fill(shift(2,2)*unitsquare,red+white); fill(shift(2,1)*unitsquare^^shift(2,3)*unitsquare^^shift(3,2)*unitsquare,blue+white); fill(shift(3,1)*unitsquare^^shift(3,3)*unitsquare,blue+white); for(int i=1;i<5;++i){ draw((1,i)--(4,i)); draw((i,1)--(i,4)); } label("$1$",(2.5,1.5)); label("$2$",(2.5,2.5)); label("$3$",(2.5,3.5)); label("$4$",(3.5,1.5)); label("$5$",(3.5,2.5)); label("$6$",(3.5,3.5)); [/asy][/asy] Analogously, if we have a configuration like below such changing color of $2$ from blue to red gives a contradiction. [asy][asy] size(100); for(int i =1;i < 4;++i){ fill(shift(1,i)*unitsquare,blue+white); } fill(shift(2,2)*unitsquare,blue+white); for(int i=1;i<5;++i){ draw((1,i)--(4,i)); draw((i,1)--(i,4)); } label("$1$",(2.5,1.5)); label("$2$",(2.5,2.5)); label("$3$",(2.5,3.5)); label("$4$",(3.5,1.5)); label("$5$",(3.5,2.5)); label("$6$",(3.5,3.5)); [/asy][/asy] Then color of $1,3,4,5,6$ must be red, i.e. we must have [asy][asy] size(100); for(int i =1;i < 4;++i){ fill(shift(1,i)*unitsquare,blue+white); } fill(shift(2,2)*unitsquare,blue+white); fill(shift(2,1)*unitsquare^^shift(2,3)*unitsquare^^shift(3,2)*unitsquare,red+white); fill(shift(3,1)*unitsquare^^shift(3,3)*unitsquare,red+white); for(int i=1;i<5;++i){ draw((1,i)--(4,i)); draw((i,1)--(i,4)); } label("$1$",(2.5,1.5)); label("$2$",(2.5,2.5)); label("$3$",(2.5,3.5)); label("$4$",(3.5,1.5)); label("$5$",(3.5,2.5)); label("$6$",(3.5,3.5)); [/asy][/asy] Proof: We resolve the first only as the other is analogous. The color of $1,3$ must be blue. Now as changing color of $2$ from red to blue gives a contradiction, so $5$ must be blue. Then $4,6$ must be red. $\square$ $\textbf{Claim 2}$: Suppose we have a configuration like below such that changing color of $2$ from red to blue gives a contradiction. [asy][asy] size(100); fill(shift(1,1)*unitsquare^^shift(1,3)*unitsquare^^shift(2,1)*unitsquare^^shift(2,2)*unitsquare^^shift(2,3)*unitsquare,blue+white); fill(shift(1,2)*unitsquare,red+white); for(int i=1;i<5;++i){ draw((1,i)--(4,i)); draw((i,1)--(i,4)); } label("$1$",(2.5,1.5)); label("$2$",(2.5,2.5)); label("$3$",(2.5,3.5)); label("$4$",(3.5,1.5)); label("$5$",(3.5,2.5)); label("$6$",(3.5,3.5)); [/asy][/asy] Then color of $4,6$ must be red and of $5$ must be blue ; i.e. we must have [asy][asy] size(100); fill(shift(1,1)*unitsquare^^shift(1,3)*unitsquare^^shift(2,1)*unitsquare^^shift(2,2)*unitsquare^^shift(2,3)*unitsquare,blue+white); fill(shift(3,1)*unitsquare,red+white); fill(shift(3,3)*unitsquare,red+white); fill(shift(3,2)*unitsquare,blue+white); fill(shift(1,2)*unitsquare,red+white); for(int i=1;i<5;++i){ draw((1,i)--(4,i)); draw((i,1)--(i,4)); } label("$1$",(2.5,1.5)); label("$2$",(2.5,2.5)); label("$3$",(2.5,3.5)); label("$4$",(3.5,1.5)); label("$5$",(3.5,2.5)); label("$6$",(3.5,3.5)); [/asy][/asy] Analogously, if we have a configuration like below such that changing color or $2$ from blue to red gives a contradiction. [asy][asy] size(100); fill(shift(1,1)*unitsquare^^shift(1,3)*unitsquare^^shift(2,1)*unitsquare^^shift(2,2)*unitsquare^^shift(2,3)*unitsquare,red+white); fill(shift(1,2)*unitsquare,blue+white); for(int i=1;i<5;++i){ draw((1,i)--(4,i)); draw((i,1)--(i,4)); } label("$1$",(2.5,1.5)); label("$2$",(2.5,2.5)); label("$3$",(2.5,3.5)); label("$4$",(3.5,1.5)); label("$5$",(3.5,2.5)); label("$6$",(3.5,3.5)); [/asy][/asy] Then color of $4,6$ must be red and of $5$ must be blue ; i.e. we must have [asy][asy] size(100); fill(shift(1,1)*unitsquare^^shift(1,3)*unitsquare^^shift(2,1)*unitsquare^^shift(2,2)*unitsquare^^shift(2,3)*unitsquare,red+white); fill(shift(3,1)*unitsquare,blue+white); fill(shift(3,3)*unitsquare,blue+white); fill(shift(3,2)*unitsquare,red+white); fill(shift(1,2)*unitsquare,blue+white); for(int i=1;i<5;++i){ draw((1,i)--(4,i)); draw((i,1)--(i,4)); } label("$1$",(2.5,1.5)); label("$2$",(2.5,2.5)); label("$3$",(2.5,3.5)); label("$4$",(3.5,1.5)); label("$5$",(3.5,2.5)); label("$6$",(3.5,3.5)); [/asy][/asy] Proof: As changing the color of $2$ from red to blue gives a contradiction, so $5$ must be blue. Then $4,6$ must be red. $\square$ Now we pick a red square on the inner border. Say we have something like [asy][asy] size(300); for(int i=1 ; i<13; ++i){ fill(shift(1,i)*unitsquare,red+white); fill(shift(12,i)*unitsquare,red+white); fill(shift(i,1)*unitsquare,red+white); fill(shift(i,12)*unitsquare,red+white); } fill(shift(2,7)*unitsquare,red+white); for(int i=1 ; i<14 ; ++i){ draw((1,i)--(13,i)); draw((i,1)--(i,13)); } label("$2$",(2.5,7.5)); [/asy][/asy] By maximality assumption on $\mathcal P$, changing color of $2$ from red to blue must give a contradiction. Using Claim 1 and Claim 2 repeatedly implies we must have: [asy][asy] size(300); for(int i=1 ; i<13; ++i){ fill(shift(1,i)*unitsquare,red+white); fill(shift(12,i)*unitsquare,red+white); fill(shift(i,1)*unitsquare,red+white); fill(shift(i,12)*unitsquare,red+white); } fill(shift(2,7)*unitsquare^^shift(5,7)*unitsquare^^shift(6,7)*unitsquare^^shift(9,7)*unitsquare^^shift(10,7)*unitsquare,red+white); fill(shift(4,8)*unitsquare^^shift(5,8)*unitsquare^^shift(8,8)*unitsquare^^shift(9,8)*unitsquare,red+white); fill(shift(4,6)*unitsquare^^shift(5,6)*unitsquare^^shift(8,6)*unitsquare^^shift(9,6)*unitsquare,red+white); fill(shift(2,8)*unitsquare^^shift(3,8)*unitsquare^^shift(6,8)*unitsquare^^shift(7,8)*unitsquare^^shift(10,8)*unitsquare^^shift(11,8)*unitsquare,blue+white); fill(shift(3,7)*unitsquare^^shift(4,7)*unitsquare^^shift(7,7)*unitsquare^^shift(8,7)*unitsquare^^shift(11,7)*unitsquare,blue+white); fill(shift(2,6)*unitsquare^^shift(3,6)*unitsquare^^shift(6,6)*unitsquare^^shift(7,6)*unitsquare^^shift(10,6)*unitsquare^^shift(11,6)*unitsquare,blue+white); for(int i=1 ; i<14 ; ++i){ draw((1,i)--(13,i)); draw((i,1)--(i,13)); } [/asy][/asy] Actually, the above configuration is for even $n$. For odd $n$, we directly get a contradiction. For example, [asy][asy] size(250); for(int i=1 ; i<11 ; ++i){ fill(shift(1,i)*unitsquare,red+white); fill(shift(10,i)*unitsquare,red+white); fill(shift(i,10)*unitsquare,red+white); fill(shift(i,1)*unitsquare,red+white); } fill(shift(2,6)*unitsquare^^shift(5,6)*unitsquare^^shift(6,6)*unitsquare^^shift(9,6)*unitsquare,red+white); fill(shift(4,7)*unitsquare^^shift(5,7)*unitsquare^^shift(8,7)*unitsquare^^shift(9,7)*unitsquare,red+white); fill(shift(4,5)*unitsquare^^shift(5,5)*unitsquare^^shift(8,5)*unitsquare^^shift(9,5)*unitsquare,red+white); fill(shift(2,5)*unitsquare^^shift(3,5)*unitsquare^^shift(6,5)*unitsquare^^shift(7,5)*unitsquare,blue+white); fill(shift(3,6)*unitsquare^^shift(4,6)*unitsquare^^shift(7,6)*unitsquare^^shift(8,6)*unitsquare,blue+white); fill(shift(2,7)*unitsquare^^shift(3,7)*unitsquare^^shift(6,7)*unitsquare^^shift(7,7)*unitsquare,blue+white); for(int i =1 ; i<12; ++i){ draw((1,i)--(11,i)); draw((i,1)--(i,11)); } draw((9,5)--(11,5)--(11,7)--(9,7)--(9,5),linewidth(1.2)+green); [/asy][/asy] Now we again return to the main case of $n$ even. [asy][asy] size(300); for(int i=1 ; i<13; ++i){ fill(shift(1,i)*unitsquare,red+white); fill(shift(12,i)*unitsquare,red+white); fill(shift(i,1)*unitsquare,red+white); fill(shift(i,12)*unitsquare,red+white); } fill(shift(2,7)*unitsquare^^shift(5,7)*unitsquare^^shift(6,7)*unitsquare^^shift(9,7)*unitsquare^^shift(10,7)*unitsquare,red+white); fill(shift(4,8)*unitsquare^^shift(5,8)*unitsquare^^shift(8,8)*unitsquare^^shift(9,8)*unitsquare,red+white); fill(shift(4,6)*unitsquare^^shift(5,6)*unitsquare^^shift(8,6)*unitsquare^^shift(9,6)*unitsquare,red+white); fill(shift(2,8)*unitsquare^^shift(3,8)*unitsquare^^shift(6,8)*unitsquare^^shift(7,8)*unitsquare^^shift(10,8)*unitsquare^^shift(11,8)*unitsquare,blue+white); fill(shift(3,7)*unitsquare^^shift(4,7)*unitsquare^^shift(7,7)*unitsquare^^shift(8,7)*unitsquare^^shift(11,7)*unitsquare,blue+white); fill(shift(2,6)*unitsquare^^shift(3,6)*unitsquare^^shift(6,6)*unitsquare^^shift(7,6)*unitsquare^^shift(10,6)*unitsquare^^shift(11,6)*unitsquare,blue+white); for(int i=1 ; i<14 ; ++i){ draw((1,i)--(13,i)); draw((i,1)--(i,13)); } draw((2.5,7.5)--(11.5,7.5),green+linewidth(1.2)); [/asy][/asy] Note even if we reverse color of cells on the green line, then the configuration would still be valid. Since one square on inner border changes from red to blue while another changes from blue to red, so this doesn't give a contradiction directly. But at least, because of this we can assume that all cells in the right of inner border are blue, i.e. [asy][asy] size(300); for(int i=2 ; i < 12 ; ++i){ fill(shift(11,i)*unitsquare,blue+white); } for(int i=1 ; i<13; ++i){ fill(shift(1,i)*unitsquare,red+white); fill(shift(12,i)*unitsquare,red+white); fill(shift(i,1)*unitsquare,red+white); fill(shift(i,12)*unitsquare,red+white); } fill(shift(2,7)*unitsquare^^shift(5,7)*unitsquare^^shift(6,7)*unitsquare^^shift(9,7)*unitsquare^^shift(10,7)*unitsquare,red+white); fill(shift(4,8)*unitsquare^^shift(5,8)*unitsquare^^shift(8,8)*unitsquare^^shift(9,8)*unitsquare,red+white); fill(shift(4,6)*unitsquare^^shift(5,6)*unitsquare^^shift(8,6)*unitsquare^^shift(9,6)*unitsquare,red+white); fill(shift(2,8)*unitsquare^^shift(3,8)*unitsquare^^shift(6,8)*unitsquare^^shift(7,8)*unitsquare^^shift(10,8)*unitsquare^^shift(11,8)*unitsquare,blue+white); fill(shift(3,7)*unitsquare^^shift(4,7)*unitsquare^^shift(7,7)*unitsquare^^shift(8,7)*unitsquare^^shift(11,7)*unitsquare,blue+white); fill(shift(2,6)*unitsquare^^shift(3,6)*unitsquare^^shift(6,6)*unitsquare^^shift(7,6)*unitsquare^^shift(10,6)*unitsquare^^shift(11,6)*unitsquare,blue+white); for(int i=1 ; i<14 ; ++i){ draw((1,i)--(13,i)); draw((i,1)--(i,13)); } draw((1,5)--(13,5)--(13,7)--(1,7)--(1,5),green+linewidth(1.2)); [/asy][/asy] If we only focus on the green rectangle, then that in itself forces [asy][asy] size(300); for(int i=2 ; i < 12 ; ++i){ fill(shift(11,i)*unitsquare,blue+white); } for(int i=1 ; i<13; ++i){ fill(shift(1,i)*unitsquare,red+white); fill(shift(12,i)*unitsquare,red+white); fill(shift(i,1)*unitsquare,red+white); fill(shift(i,12)*unitsquare,red+white); } fill(shift(2,5)*unitsquare^^shift(5,5)*unitsquare^^shift(6,5)*unitsquare^^shift(9,5)*unitsquare^^shift(10,5)*unitsquare,red+white); fill(shift(3,5)*unitsquare^^shift(4,5)*unitsquare^^shift(7,5)*unitsquare^^shift(8,5)*unitsquare,blue+white); fill(shift(2,7)*unitsquare^^shift(5,7)*unitsquare^^shift(6,7)*unitsquare^^shift(9,7)*unitsquare^^shift(10,7)*unitsquare,red+white); fill(shift(4,8)*unitsquare^^shift(5,8)*unitsquare^^shift(8,8)*unitsquare^^shift(9,8)*unitsquare,red+white); fill(shift(4,6)*unitsquare^^shift(5,6)*unitsquare^^shift(8,6)*unitsquare^^shift(9,6)*unitsquare,red+white); fill(shift(2,8)*unitsquare^^shift(3,8)*unitsquare^^shift(6,8)*unitsquare^^shift(7,8)*unitsquare^^shift(10,8)*unitsquare^^shift(11,8)*unitsquare,blue+white); fill(shift(3,7)*unitsquare^^shift(4,7)*unitsquare^^shift(7,7)*unitsquare^^shift(8,7)*unitsquare^^shift(11,7)*unitsquare,blue+white); fill(shift(2,6)*unitsquare^^shift(3,6)*unitsquare^^shift(6,6)*unitsquare^^shift(7,6)*unitsquare^^shift(10,6)*unitsquare^^shift(11,6)*unitsquare,blue+white); for(int i=1 ; i<14 ; ++i){ draw((1,i)--(13,i)); draw((i,1)--(i,13)); } draw((1,4)--(13,4)--(13,6)--(1,6)--(1,4),green+linewidth(1.2)); [/asy][/asy] Again, the green rectangle above is in itself enough to force [asy][asy] size(300); for(int i=2 ; i < 12 ; ++i){ fill(shift(11,i)*unitsquare,blue+white); } for(int i=1 ; i<13; ++i){ fill(shift(1,i)*unitsquare,red+white); fill(shift(12,i)*unitsquare,red+white); fill(shift(i,1)*unitsquare,red+white); fill(shift(i,12)*unitsquare,red+white); } fill(shift(2,4)*unitsquare^^shift(3,4)*unitsquare^^shift(6,4)*unitsquare^^shift(7,4)*unitsquare^^shift(10,4)*unitsquare,blue+white); fill(shift(4,4)*unitsquare^^shift(5,4)*unitsquare^^shift(8,4)*unitsquare^^shift(9,4)*unitsquare,red+white); fill(shift(2,5)*unitsquare^^shift(5,5)*unitsquare^^shift(6,5)*unitsquare^^shift(9,5)*unitsquare^^shift(10,5)*unitsquare,red+white); fill(shift(3,5)*unitsquare^^shift(4,5)*unitsquare^^shift(7,5)*unitsquare^^shift(8,5)*unitsquare,blue+white); fill(shift(2,7)*unitsquare^^shift(5,7)*unitsquare^^shift(6,7)*unitsquare^^shift(9,7)*unitsquare^^shift(10,7)*unitsquare,red+white); fill(shift(4,8)*unitsquare^^shift(5,8)*unitsquare^^shift(8,8)*unitsquare^^shift(9,8)*unitsquare,red+white); fill(shift(4,6)*unitsquare^^shift(5,6)*unitsquare^^shift(8,6)*unitsquare^^shift(9,6)*unitsquare,red+white); fill(shift(2,8)*unitsquare^^shift(3,8)*unitsquare^^shift(6,8)*unitsquare^^shift(7,8)*unitsquare^^shift(10,8)*unitsquare^^shift(11,8)*unitsquare,blue+white); fill(shift(3,7)*unitsquare^^shift(4,7)*unitsquare^^shift(7,7)*unitsquare^^shift(8,7)*unitsquare^^shift(11,7)*unitsquare,blue+white); fill(shift(2,6)*unitsquare^^shift(3,6)*unitsquare^^shift(6,6)*unitsquare^^shift(7,6)*unitsquare^^shift(10,6)*unitsquare^^shift(11,6)*unitsquare,blue+white); for(int i=1 ; i<14 ; ++i){ draw((1,i)--(13,i)); draw((i,1)--(i,13)); } [/asy][/asy] Continuing in a similar way me must have [asy][asy] size(300); for(int i=2 ; i < 12 ; ++i){ fill(shift(11,i)*unitsquare,blue+white); } for(int i=1 ; i<13; ++i){ fill(shift(1,i)*unitsquare,red+white); fill(shift(12,i)*unitsquare,red+white); fill(shift(i,1)*unitsquare,red+white); fill(shift(i,12)*unitsquare,red+white); } fill(shift(2,4)*unitsquare^^shift(3,4)*unitsquare^^shift(6,4)*unitsquare^^shift(7,4)*unitsquare^^shift(10,4)*unitsquare,blue+white); fill(shift(4,4)*unitsquare^^shift(5,4)*unitsquare^^shift(8,4)*unitsquare^^shift(9,4)*unitsquare,red+white); fill(shift(2,5)*unitsquare^^shift(5,5)*unitsquare^^shift(6,5)*unitsquare^^shift(9,5)*unitsquare^^shift(10,5)*unitsquare,red+white); fill(shift(3,5)*unitsquare^^shift(4,5)*unitsquare^^shift(7,5)*unitsquare^^shift(8,5)*unitsquare,blue+white); fill(shift(2,3)*unitsquare^^shift(5,3)*unitsquare^^shift(6,3)*unitsquare^^shift(9,3)*unitsquare^^shift(10,3)*unitsquare,red+white); fill(shift(3,3)*unitsquare^^shift(4,3)*unitsquare^^shift(7,3)*unitsquare^^shift(8,3)*unitsquare,blue+white); fill(shift(2,2)*unitsquare^^shift(3,2)*unitsquare^^shift(6,2)*unitsquare^^shift(7,2)*unitsquare^^shift(10,2)*unitsquare,blue+white); fill(shift(2,7)*unitsquare^^shift(5,7)*unitsquare^^shift(6,7)*unitsquare^^shift(9,7)*unitsquare^^shift(10,7)*unitsquare,red+white); fill(shift(4,2)*unitsquare^^shift(5,2)*unitsquare^^shift(8,2)*unitsquare^^shift(9,2)*unitsquare,red+white); fill(shift(4,8)*unitsquare^^shift(5,8)*unitsquare^^shift(8,8)*unitsquare^^shift(9,8)*unitsquare,red+white); fill(shift(4,6)*unitsquare^^shift(5,6)*unitsquare^^shift(8,6)*unitsquare^^shift(9,6)*unitsquare,red+white); fill(shift(2,8)*unitsquare^^shift(3,8)*unitsquare^^shift(6,8)*unitsquare^^shift(7,8)*unitsquare^^shift(10,8)*unitsquare^^shift(11,8)*unitsquare,blue+white); fill(shift(3,7)*unitsquare^^shift(4,7)*unitsquare^^shift(7,7)*unitsquare^^shift(8,7)*unitsquare^^shift(11,7)*unitsquare,blue+white); fill(shift(2,6)*unitsquare^^shift(3,6)*unitsquare^^shift(6,6)*unitsquare^^shift(7,6)*unitsquare^^shift(10,6)*unitsquare^^shift(11,6)*unitsquare,blue+white); for(int i=1 ; i<14 ; ++i){ draw((1,i)--(13,i)); draw(( i,1)--(i,13)); } draw((4,1)--(6,1)--(6,3)--(4,3)--(4,1),green+linewidth(1.2)); draw((8,1)--(10,1)--(10,3)--(8,3)--(8,1),green+linewidth(1.2)); [/asy][/asy] But that's a contradiction! This finally completes the proof. $\blacksquare$