A coloring of all plane points with coordinates belonging to the set $S = \{0, 1, . . . , 99\}$ into red and white colors is said to be reddish if for each $i, j ∈ S$ at least one of the four points $(i, j),(i + 1, j),(i, j + 1)$ and $(i + 1, j + 1) (99 + 1 ≡ 0)$ is colored red. Find the maximal possible number of red points in a reddish coloring which loses its property after recoloring of any red point into white.
Official solution:
It can be readily seen that the coloring of all points $(i, j)$ with $i + j = 0, 1 \pmod 4$ into red and all points $(i, j)$ with $i + j = 2, 3 \pmod 4$ into white is reddish and contains $1002 2 = 5000$ red points. Now suppose that the is a reddish coloring having more than $5000$ red points. Let us take an arbitrary red point. By definitions this red point is the only red point among some collection of four points $(i, j),(i+1, j),(i, j +1),(i+1, j +1)$. Amongst these four points there are exactly two pairs of points distanced 1 and colored differently. Let us connect differently colored points in each of these two pairs by black segments. If we repeat the same procedure for all red points we will draw at least $5001 · 2 = 10002$ black segments. Since by assumption there are less than 5000 white points, there are at least three black segments incident to some white point, say $(l, m)$. W.l.o.g. suppose that black segments connect the point $(l, m)$ with red points $(l−1, m),(l+1, m)$ and $(l, m−1)$.
Now the white point $(l, m)$ and the red point $(l, m − 1)$ can not be connected by black segment since the points $(l −1, m),(l + 1, m)$ are also red. A contradiction shows that the answer is not greater than $5000$.
Can someone please explain last part (italic)? I don't see any contradition from there.
In the following picture, I use blue dots instead of white, since it's against a white background. Black dots represent points that we don't know the color of yet.
Now we ask - why is that lower segment black? Is it black because of the square on the lower left? No, because that square has at least two red dots in it. Is it black because of the square on the lower right? No, because that square has at least two red dots in it as well. There aren't any other unit squares that have that segment as an edge, so the segment can't be black - and there's our contradiction.