MathDB
Colorings of a rectangle - prove N^2 >= M * 2^(mn)

Source: IMO Shortlist 2005 Combinatorics problem C3; 2nd German pre-TST 2006, problem 3

December 29, 2006
combinatoricsrectanglematrixcountinggraph theoryIMO ShortlistHi

Problem Statement

Consider a m×nm\times n rectangular board consisting of mnmn unit squares. Two of its unit squares are called adjacent if they have a common edge, and a path is a sequence of unit squares in which any two consecutive squares are adjacent. Two parths are called non-intersecting if they don't share any common squares. Each unit square of the rectangular board can be colored black or white. We speak of a coloring of the board if all its mnmn unit squares are colored. Let NN be the number of colorings of the board such that there exists at least one black path from the left edge of the board to its right edge. Let MM be the number of colorings of the board for which there exist at least two non-intersecting black paths from the left edge of the board to its right edge. Prove that N2≥M⋅2mnN^{2}\geq M\cdot 2^{mn}.
Back to ProblemsView on AoPS