Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2005 IMO Shortlist Problems/C3

Problem

(Iran) In an $m \times n$ rectangular board of $\displaystyle 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 coloured black or white. Let $\displaystyle N$ denote the number of colourings of the board such that there exists at least one black path from the left edge of the board to the right edge of the board, and let $\displaystyle M$ denote the number of colourings in which there exist at least two non-intersecting black paths from the left edge to the right edge. Prove that $N^2 \ge M \cdot 2^{mn}$.

This was also Problem 6 of the 2006 German Pre-TST.

Solution

We will call black paths which connect the left edge of the board to the right edge good paths.

Lemma. Consider a board as described in the problem, and let columns run from top to bottom, and rows run from left to right, with $\displaystyle m$ columns and $\displaystyle n$ rows. We say that one path $\displaystyle M_1$ lies below another path $\displaystyle M_2$ if in each column, the highest square of $\displaystyle M_1$ in that column lies below the highest square of $\displaystyle M_2$ in that column. Then there exists a lowest good path, which we define as a good path that lies below all other good paths.

Proof. Let $M_1, \ldots, M_k$ be all the good paths, with loops removed (i.e., each square appears in a path at most once—this can be done by replacing all sequences of squares of the form $ABC \cdot A$ by $\displaystyle A$). For each $1 \le j \le m-1$, let $\displaystyle Q_j$ be the lowest square in column $\displaystyle j$ that is in one of the loopless good paths, say $\displaystyle M_i$. Since $\displaystyle M_i$ contains no loops, $\displaystyle Q_j$ must be at the bottom of a subcolumn $\displaystyle T$ of black squares such that the square at the top of $\displaystyle T$ is adjacent to a square in column $\displaystyle j+1$. It follows that there exists a shortest subcolumn $\displaystyle T'$ of black squares (possibly of length 1) such that the square at the top of $\displaystyle T'$ is adjacent to some square in column $\displaystyle i+1$. Then the squares in the union of all such subcolumns constitute a good path which lies below all others. ∎

Now, consider two boards. We color the first one so that there are two non-intersecting good paths, and color the second one in any way. There are $M \cdot 2^{mn}$ such boards. Let $\displaystyle M'$ be a lowest good path on the first board. We transpose $\displaystyle M'$ and all squares below $\displaystyle M'$ with the corresponding squares on the second board and thus obtain two boards, each with a good path. This process is injective, for we can reverse our procedure by transposing the lowest good path of the second board, and all squares below it, with the corresponding squares of the first board. Since there are $\displaystyle N^2$ ordered pairs of boards such that each has a good path, it follows that $M \cdot 2^{mn} \le N^2$, as desired.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_IMO_Shortlist_Problems/C3&oldid=15229"