2004 Putnam A5

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 $m n / 8$.

$m \times n$ 棋盘的颜色是随机的：每个方格都是

独立地

分配红色或黑色的概率为 $1/2$。我们说两个正方形，

$p$ 和 $q$ 位于同一连通单色区域中，如果存在

一系列相同颜色的方块，从 $p$ 开始，结束

在 $q$ 处，其中序列中的连续方块共享公共边。

表明连接的单色区域的预期数量是

大于 $m n / 8$。