Putnam 2004 A5
Source:
December 11, 2004
Putnamprobabilityinductiongeometryperimeterexpected valuecollege contests
Problem Statement
An checkerboard is colored randomly: each square is independently assigned red or black with probability we say that two squares, and , are in the same connected monochromatic region if there is a sequence of squares, all of the same color, starting at and ending at in which successive squares in the sequence share a common side. Show that the expected number of connected monochromatic regions is greater than