2005 IMO Shortlist Problems/C3
(Iran) In an rectangular board of 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 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 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 .
This was also Problem 6 of the 2006 German Pre-TST.
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 columns and rows. We say that one path lies below another path if in each column, the highest square of in that column lies below the highest square of 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 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 by ). For each , let be the lowest square in column that is in one of the loopless good paths, say . Since contains no loops, must be at the bottom of a subcolumn of black squares such that the square at the top of is adjacent to a square in column . It follows that there exists a shortest subcolumn of black squares (possibly of length 1) such that the square at the top of is adjacent to some square in column . 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 such boards. Let be a lowest good path on the first board. We transpose and all squares below 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 ordered pairs of boards such that each has a good path, it follows that , as desired.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.