Question 8
In an $ m \times n $ rectangular board of mn unit squares, adjacent squares are ones with a common edge, and a path is a sequence of squares in which any two consecutive squares are adjacent. Each square of the board can be colored black or white. Let N denote 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, and let M denote the number of colorings in which there exist at least two non-intersecting black paths from the left edge to the right edge. Prove that $ N^2 \geq 2^{mn}M $.