A coloring of all plane points with coordinates belonging to the set $S=\{0,1,\ldots,99\}$ into red and white colors is said to be critical if for each $i,j\in S$ at least one of the four points $(i,j),(i + 1,j),(i,j + 1)$ and $(i + 1, j + 1)$ $(99 + 1\equiv0)$ is colored red. Find the maximal possible number of red points in a critical coloring which loses its property after recoloring of any red point into white.
Problem
Source: Turkey JBMO TST 2015 P8
Tags: combinatorics
MellowMelon
24.06.2016 18:08
The coloring where $(x,y)$ is red if and only if $x+y$ is 0 or 1 mod 4 satisfies the requested property and has 5000 red points. Still working on showing 5001 is impossible.
MellowMelon
25.06.2016 04:02
I think there's got to be a nice way to show 5001 is impossible and I'm still unwilling to admit defeat on finding it, but here is a not-totally-nice way from a fairly obvious idea.
Suppose there are $r$ red squares. Arbitrarily choose $r$ 2 by 2 squares, each containing exactly one red cell and so that each red cell is in one of the squares. These exist by the conditions. In each white cell, write the number of chosen squares that contain it. The average number written in the white cells is $\frac{3r}{10000 - r}$, which is increasing with $r$ and equal to 3 when $r = 5000$. We claim this average cannot be more than 3.
To show this, if a number greater than 3 is written in a white cell, then the number is 4 and it must come in this configuration R2R
242
R2R The R is a red cell and the numbers are what's written in white cells. So we can pair each occurrence of 4 with the white cell with 2 right above it, and the average of this pair is 3. No white cell is a part of two pairs, so by averaging over these pairs and unpaired white cells we get the average of numbers on the whole board is at most 3.
MellowMelon
25.06.2016 04:27
Oh, here's the nice way. For each red cell, there is a 2 by 2 square containing it and 3 other white cells. On that red cell, place a copy of the tile below so that the red coincides and rotated so that the dot is at the center of the chosen 2 by 2 square. [asy][asy]size(30); path p = (0,0)--(1,0)--(1,1)--(0,1)--cycle; fill(p, red); draw(p); draw((1,0)--(1.5,0.5)--(1.5,1)--(1,1)--(1,1.5)--(0.5,1.5)--(0,1)); draw((1.5,1)--(1.5,1.5)--(1,1.5)); dot((1,1));[/asy][/asy] It is easy to check that no two of these tiles will overlap. Since each tile has the same white and red area, there must be at least as many white cells as red cells.