, 2018

Solution:

First we show an upper bound. Define a grid point as a vertex of one of the squares in the figure. Construct a graph as follows. Place a vertex at each grid point and draw an edge between two adjacent points if that edge forms a black-white boundary. The condition of there being no $2 \times 2$ checkerboard is equivalent to no vertex having degree more than $2$. There are $101^{2} + 4 \cdot 99^{2} = 49405$ vertices that are allowed to have degree $2$ and $12 \cdot 99 = 1188$ vertices (on the boundary) that can have degree $1$.
This gives us an upper bound of $49999$ edges. We will show that exactly this many edges is impossible. Assume for the sake of contradiction that we have a configuration achieving exactly this many edges.

Consider pairing up the degree $1$ vertices so that those on a horizontal edge pair with the other vertex in the same column and those on a vertical edge pair with the other vertex in the same row. If we combine the pairs into one vertex, the resulting graph must have all vertices with degree exactly $2$. This means the graph must be a union of disjoint cycles. However all cycles must have even length and there are an odd number of total vertices so this is impossible. Thus we have an upper bound of $49998$.

We now describe the construction. The top row alternates black and white. The next $99$ rows alternate between all black and all white. Let's say the second row from the top is all white. The $101^{\text{st}}$ row alternates black and white for the first $100$ squares, is all black for the next $100$ and alternates between white and black for the last $100$ squares. The next $98$ rows alternate between all black and all white (the $102^{\text{nd}}$ row is all white). Finally, the bottom $101$ rows are a mirror of the top $101$ rows with the colors reversed. We easily verify that this achieves the desired.

We illustrate the construction for $300$ replaced by $12$.