2005 IMO Shortlist S04

Consider a $m\times n$ rectangular board consisting of $mn$ 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 $mn$ unit squares are colored.

Let $N$ 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 $M$ 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 $N^{2}\geq M\cdot 2^{mn}$ .

考虑一个由 $mn$ 个单位方块组成的 $m\times n$ 矩形板。如果它的两个单位方块具有公共边，则它们被称为“相邻”，并且“路径”是单位方块的序列，其中任何两个连续的方块都是相邻的。如果两个部分不共享任何公共正方形，则它们被称为“不相交”。

长方形板的每个单位正方形可以是黑色或白色。如果棋盘上所有 $mn$ 单位方块都被着色，我们就说棋盘的“着色”。

令 $N$ 为棋盘的着色数量，使得从棋盘的左边缘到右边缘至少存在一条黑色路径。令 $M$ 为板的着色数量，从板的左边缘到右边缘至少存在两条不相交的黑色路径。

证明 $N^{2}\geq M\cdot 2^{mn}$ 。