Question 167
We consider a $m \times n$ rectangle made of $m n$ unit squares. Two of its unit squares are said to be adjacent if they have a common side edge, and a path is a sequence of unit squares in which two consecutive elements are adjacent.
Each unit square of the rectangle can be colored either white or black. If all squares are colored, the rectangle is colored.
Let $N$ be the number of all such colorings for which there is at least one black path from the left to the right side edge of the rectangle. Furthermore, let $M$ be the number of all colorings for which there are at least two black paths from the left to the right side edge of the rectangle that do not contain a common square.
Prove that $N^{2} \geq M \cdot 2^{m n}$.
Each unit square of the rectangle can be colored either white or black. If all squares are colored, the rectangle is colored.
Let $N$ be the number of all such colorings for which there is at least one black path from the left to the right side edge of the rectangle. Furthermore, let $M$ be the number of all colorings for which there are at least two black paths from the left to the right side edge of the rectangle that do not contain a common square.
Prove that $N^{2} \geq M \cdot 2^{m n}$.