Putnam 2004, Problem A-5

An $m \times n$ checkerboard is colored randomly: each square is independently assigned red or black with probability $1/2$. We say that two squares, $p$ and $q$, are in the same connected monochromatic region if there is a sequence of squares, all of the same color, starting at $p$ and ending at $q$, in which successive squares in the sequence share a common side. Show that the expected number of connected monochromatic regions is greater than $mn/8$.

Solution:
**First solution:** First recall that any graph with $n$ vertices and $e$ edges has at least $n-e$ connected components (add each edge one at a time, and note that it reduces the number of components by at most 1). Now imagine the squares of the checkerboard as a graph, whose vertices are connected if the corresponding squares share a side and are the same color. Let $A$ be the number of edges in the graph, and let $B$ be the number of 4-cycles (formed by monochromatic $2 \times 2$ squares). If we remove the bottom edge of each 4-cycle, the resulting graph has the same number of connected components as the original one; hence this number is at least
$$mn - A + B.$$

By the linearity of expectation, the expected number of connected components is at least
$$mn - E(A) + E(B).$$

Moreover, we may compute $E(A)$ by summing over the individual pairs of adjacent squares, and we may compute $E(B)$ by summing over the individual $2 \times 2$ squares. Thus
$$E(A) = \frac{1}{2}(m(n-1) + (m-1)n),$$
$$E(B) = \frac{1}{8}(m-1)(n-1),$$
and so the expected number of components is at least
$$mn - \frac{1}{2}(m(n-1) + (m-1)n) + \frac{1}{8}(m-1)(n-1)$$
$$= \frac{mn + 3m + 3n + 1}{8} > \frac{mn}{8}.$$

**Remark:** A "dual" approach is to consider the graph whose vertices are the corners of the squares of the checkerboard, with two vertices joined if they are adjacent and the edge between them does not separate two squares of the same color. In this approach, the 4-cycles become isolated vertices, and the bound on components is replaced by a call to Euler's formula relating the vertices, edges and faces of a planar figure. (One must be careful, however, to correctly handle faces which are not simply connected.)

**Second solution:** (by Noam Elkies) Number the squares of the checkerboard $1, \ldots, mn$ by numbering the first row from left to right, then the second row, and so on. We prove by induction on $i$ that if we just consider the figure formed by the first $i$ squares, its expected number of monochromatic components is at least $i/8$. For $i = 1$, this is clear.

Suppose the $i$-th square does not abut the left edge or the top row of the board. Then we may divide into three cases.

- With probability $1/4$, the $i$-th square is opposite in color from the adjacent squares directly above and to the left of it. In this case adding the $i$-th square adds one component.
- With probability $1/8$, the $i$-th square is the same in color as the adjacent squares directly above and to the left of it, but opposite in color from its diagonal neighbor above and to the left. In this case, adding the $i$-th square either removes a component or leaves the number unchanged.
- In all other cases, the number of components remains unchanged upon adding the $i$-th square.

Hence adding the $i$-th square increases the expected number of components by $1/4 - 1/8 = 1/8$.

If the $i$-th square does abut the left edge of the board, the situation is even simpler: if the $i$-th square differs in color from the square above it, one component is added, otherwise the number does not change. Hence adding the $i$-th square increases the expected number of components by $1/2$; likewise if the $i$-th square abuts the top edge of the board. Thus the expected number of components is at least $i/8$ by induction, as desired.

**Remark:** Some solvers attempted to consider adding one row at a time, rather than one square; this must be handled with great care, as it is possible that the number of components can drop rather precipitously upon adding an entire row.