OF A GOLDEN AGE

here is one of the math problems from the putnam exam:

an m x 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.

no responses