olymmath

Putnam 2004 A5

  • Session A

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

Curated text Kedlaya Putnam archive. Quoted with source.

Solutions

Human solution Solution 1 by Kiran Kedlaya and Lenny Ng

The terms of the source let olymmath link to this solution but not copy it. Read the solution (Kedlaya Putnam archive).

Similar problems

These problems have the most words in common with this statement.

Locator putnam/2004/a5 · Tag 7548XBX9YP · Edit this page on GitHub · Keys: j next, k previous