Table with cells

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Table with cells

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: All Russian Olympiad 2017,Day2,grade 9,P8

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4900 posts

#1 h May 3, 2017, 12:30 PM • 8 Y

Y by Davi-8191, Tawan, vsathiam, mijail, itslumi, HWenslawski, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5850 posts

#2 h May 3, 2017, 3:25 PM • 3 Y

Y by Tawan, HWenslawski, Adventure10

The solution to this problem is basically identical to what I posted in this topic: http://artofproblemsolving.com/community/c6h598767p3556556

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1476 posts

math90

#3 h May 4, 2017, 7:48 AM • 16 Y

Y by laegolas, DreamComeTrue, roughlife, Tawan, lifeisgood03, vsathiam, Delray, Wizard_32, Taha1381, meagain, mijail, guptaamitu1, Pitagar, Adventure10, Mango247, math_comb01

This post has been edited 2 times. Last edited by math90, May 4, 2017, 1:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

264 posts

#4 h Sep 10, 2017, 6:42 AM • 2 Y

Y by Davi-8191, Adventure10

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$ .

This post has been edited 1 time. Last edited by phymaths, Sep 10, 2017, 6:43 AM
Reason: Idk

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

348 posts

Delray

#5 h Jan 10, 2018, 5:56 PM • 2 Y

Y by vsathiam, Adventure10

Nothing new here

This post has been edited 2 times. Last edited by Delray, Jan 10, 2018, 5:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

380 posts

#6 h Aug 14, 2020, 10:00 AM • 1 Y

Y by Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

484 posts

554183

#7 h Jul 20, 2021, 11:39 AM • 1 Y

Y by itslumi

........

This post has been edited 10 times. Last edited by 554183, Aug 15, 2022, 7:27 PM
Reason: 10 times the charm

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

656 posts

#8 h Mar 16, 2022, 1:56 PM • 1 Y

Y by Rotten_

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] 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]$
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] 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]$
Then color of $1,3,4,5,6$ must be blue, i.e. we must have
$[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]$

Analogously, if we have a configuration like below such changing color of $2$ from blue to red gives a contradiction.
$[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]$
Then color of $1,3,4,5,6$ must be red, i.e. we must have
$[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]$

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] 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]$
Then color of $4,6$ must be red and of $5$ must be blue ; i.e. we must have
$[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]$

Analogously, if we have a configuration like below such that changing color or $2$ from blue to red gives a contradiction.
$[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]$
Then color of $4,6$ must be red and of $5$ must be blue ; i.e. we must have
$[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]$

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] 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]$
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] 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]$
Actually, the above configuration is for even $n$ . For odd $n$ , we directly get a contradiction. For example,
$[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]$
Now we again return to the main case of $n$ even.
$[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]$
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] 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]$
If we only focus on the green rectangle, then that in itself forces
$[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]$
Again, the green rectangle above is in itself enough to force
$[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]$
Continuing in a similar way me must have
$[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]$
But that's a contradiction!

This finally completes the proof. $\blacksquare$

This post has been edited 2 times. Last edited by guptaamitu1, Aug 8, 2022, 5:20 PM
Reason: fixing Asy

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4 posts

Radin_

#9 h Apr 5, 2025, 1:31 PM

Y by

assume the contrary.

consider the corners of the squares of the grid that are not on the edges of the board (they make up a $99*99$ grid in the interior of the board) we define a graph with the mentioned $99^2$ points as its vertices. we draw an edge between two vertices if on the board they have distance $1$ and the two squares of the grid with corners as the vertices don't have the same color. it is easy to see that each vertex has even degree. if a vertex has degree $0$ then the $4$ square around it have the same color which is a contradiction and if a vertex has degree $4$ then the square around it make a chessboard pattern which is also a contradiction meaning that each vertex has degree $2$ (the all black outline means that this is correct for all of our vertices).

now we know that a graph with all degrees equal to $2$ is the union of some disjoint cycles it is also easy to see that each of our cycles has an even number of vertices (starting from a point on the cycle we must move the same number of edges up as down and also the same number of edges left as right to complete the cycle and get back to our starting point).
so we have a graph with an odd number of vertices that is made up of the union of disjoint even cycles. absurd

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a