We call a path of black squares which connects both sides of the board good. First, it is necessary to show that if there is a good path, then there exists such a lowest good path $M'$ such that in each column of the board, the highest square of $M'$ in that column is at least as low as the highest square in any other such path in that column. This is not hard. Now, we consider two boards, one with two disjoint good paths, and one colored any way we like. There are $M \cdot 2^{mn}$ such boards. Now, we transpose the lowest good path on the first board, and all squares beneath it, with the corresponding squares on the second board. We thus obtain two boards, each with a good path. This process is injective, for we can reverse it by transposing the lowest good path on the second board, and all squares beneath it, with the corresponding squares on the first board. Thus $M \cdot 2^{mn}$ is at most the number of pairs of boards such that each board has a good path, and this latter number is $N^{2}$. $\blacksquare$

Some extensions: 1. The inequality is strict. 2. Let $ n,$ the length, be fixed and let $ m$ vary, and put $ p_m = \tfrac{N(m,n)}{2^{mn}}.$ Then $ p_1 < p_2 < p_3 < p_4 < \cdots$ 3. \[ \frac {M}{2^{mn}} \leq p_{m} p_{m - 1} - \sum_{i < m} p_i (p_i - p_{i - 1}) < p_m^2 \]

Define a good path to be a path of black squares from the left edge to the right edge of the $m\times n$ grid. Define the set $A$ such that \[A = \{ (p,q) | p,q \quad \text{are colourings with at least one good path} \}\] Define the set $B$ such that \[B = \{ (p,q) | p \quad \text{is a colouring with at least two non-intersecting good paths and} \quad q \quad \text{is any colouring} \}\] It is clear that $|A| = N^2$ and $|B| = M \cdot 2^{mn}$. Now we construct an injection $f : B \rightarrow A$ as follows. Let $(r,s)$ be such that $(r,s) \in B$. Since $r$ has two non-intersecting good paths, we can construct two new grid colourings as follows: 1. Partitions $r$ into two sub-grids $a$ and $b$ such that the bottom square in each column of $a$ is the corresponding square in the uppermost good path in $r$. 2. Partitions $s$ into two sub-grids $c$ and $d$ such that the shape of $c$ is the same as the shape of $a$ and the shape of $d$ is the same as the shape of $b$. 3. Switches the positions of $a$ and $c$ to form the two new grids $a \cup d$ and $c \cup b$. Let $f(r,s)=(a \cup d, c \cup b)$. Now note that $f$ is injective since it can easily be verified that $f(f(r,s))=(r,s)$. Since there exists an injection $f : B \rightarrow A$, it follows that $|A| \ge |B|$ and that $N^2 \ge M \cdot 2^{mn}$. $\blacksquare$

Can someone check my solution? It feels fine, but there might be holes in it. Let $\nu$ denote colorings with contain at least one black path connecting the left and right edges of the board. Note that $N^2\ge M\cdot2^{mn}$ rearranges to $\frac{N}{2^{mn}}\ge \frac{M}{N}$. We may interpret the left side of the inequality to be the probability that $\nu$ occurs given that each square is equally likely to be black or white. Similarly, the right side is the probability that two non-intersecting paths occurs given a random $\nu$. Lemma: Define $n$ of a not necessarily continuous or rectangular board $B$ as the number of columns in the smallest rectangular board that contains $B$. If square(s) are added to $B$ given that $n$ does not change, the probability that $\nu$ occurs does not decrease. This can be seen by noting that $\nu$ of $B$ are unaffected, but some colorings that contain a path may gain a path. If we take remove the shortest path in each $\nu$ and splice the top and bottom sections together (i.e. translate the bottom section up a unit), we obtain a $(m-1)\times n$ board that may contain holes. $\nu$ in this new board $B$ corresponds to colorings on the original board that have two colorings with intersections of at most one continuous square and $P(\nu | B)\ge \frac{M}{N}$. According to the lemma, we may add squares to $B$, including a whole row, to obtain the $m \times n$ board to obtain $\frac{N}{2^{mn}}\ge P(\nu | B)\ge \frac{M}{N}$. $\blacksquare$

The following stronger problem is from the solution given in the book The IMO Compendium, which is much easier to solve Consider two rectangular $m \times n $ boards , each of them consists of $mn$ squares.Color all squares of the boards such that there are $k$ '' fixed squares'' in each board, placed in similar positions, which are always colored using same color and there exists a black path from left to right of both the boards .The two paths can not intersect in any of the fixed $k$ squares. Suppose that the two boards can be colored in total $f(k_p) $ ways. Show that $2^k f(k_p) \le N^2$ Solution: Induction on $k$. The case $k=0$ is trivial. Assume that it is true for a couple of board having $k-1$ fixed squares i.e we have $2^k f({k-1}_q) \le N^2$. We add another fixed point. We have to show that $2^k f(k_p) \le N^2$. It suffices to show that $f({k-1}_q) \le 2 f(k_p)$, which is true because we can always change the color of the newly added ''fixed'' point in (at least) one of the boards. Now if we take $k=mn$, we get $f(mn_p) = M $, so $N^2 \ge M \cdot 2^{mn}$

Boy Soprano II wrote: We call a path of black squares which connects both sides of the board good. First, it is necessary to show that if there is a good path, then there exists such a lowest good path $M'$ such that in each column of the board, the highest square of $M'$ in that column is at least as low as the highest square in any other such path in that column. This is not hard. Now, we consider two boards, one with two disjoint good paths, and one colored any way we like. There are $M \cdot 2^{mn}$ such boards. Now, we transpose the lowest good path on the first board, and all squares beneath it, with the corresponding squares on the second board. We thus obtain two boards, each with a good path. This process is injective, for we can reverse it by transposing the lowest good path on the second board, and all squares beneath it, with the corresponding squares on the first board. Thus $M \cdot 2^{mn}$ is at most the number of pairs of boards such that each board has a good path, and this latter number is $N^{2}$. $\blacksquare$ Hello, I think transposing only the lowest path is sufficient to construct an injection, isn't it?

No. Consider the following 3 by 3 examples: in the first pair, the first grid is all black except the middle square in the bottom row, while the second grid is all white except for the middle square in the bottom row. In the second pair, the first grid has black 1st and 3rd rows, while the second grid has black 2nd row. Both pairs get sent by your proposed map to the pair in which the first grid has first row black and rest white while the second grid has first row white and rest black.

Call a path leeky if goes from the left side to the right side. Also, denote the sets $A,B,C$ to denote the sets of all colorings, those with at least 1 leeky path, and those with at least 2. We will construct an injection $f: (A,C)\to B^2$, which of course will imply the result. First, we claim that for all elements of $B$, there exists a highest leeky path, $l_H$, such that the black squares of any other path are below those of $l_H$ in the same column. Supposing the contrary, then for any path $a$, we can construct a path $b$ where at least one black square is above. If $a$ and $b$ are disjoint, then we must have $b$ is strictly above $a$. Otherwise, they intersect, and we can take a path from their union which ends up being above $a$. Hence, we can always find a path above any path. However, we can't continue picking higher and higher paths, so we have a contradiction, and there must be a highest path. Now, suppose we have a pair of colorings $(P,Q)$, where $P\in A$, $Q\in C$, we can $P$'s highest path and all squares above its lower bound, and swap it with the same region in $Q$. Of course, this mapping is well defined, and brings our pair to an element of $B^2$. Now, to show it's injective, we show that the image of our mapping, $f$, is reversible. Of course, this is not hard, as the highest path of $P$ is now the highest path of $Q'$, so we can just perform the exact same map, except take the highest path of $Q'$ to $P'$. As we have constructed a valid injection, the problem statement is true.

Could someone please check if this sol is correct as it seems quite different from the others sol which basically all use inj? We can rearrange the condition as $N\geq \frac{M}{N}\cdot 2^{mn}$. Notice that $\frac{M}{N}$ is equal to $\frac{P(M)}{P(N)}$, where $P(M)$ denotes that the probability of a coloring having two non-intersecting black paths and $P(N)$ denotes the probability of a coloring having at least one black path. Notice then that the equation rearranges to $\frac{N}{2^{mn}}\geq \frac{P(M)}{P(n)}$. The expression on the left is the same as $P(n)$. Hence the problem reduces to proving that $P(M)\leq P(N)^2$. This is obvious, because obviously the probability of just picking two random boards that satisfy the first requirement does not guarantee that it would satisfy the second(stronger) requirement.

Consider a $2m\times n$ rectangular board. Let $A$ be the set of colouring such that there exists a path from the left edge of the left $m\times n$ board to the right edge of it, and a path from the right edge of it to the right edge of the right $m\times n$ board. Let $B$ be the set of colouring such that there exists two non-intersecting black paths from the left edge of the left $m\times n$ board to its right edge. Obviously $|A|=N^2$ and $|B|=M\cdot 2^{mn}$. We now create an injection from $B$ to $A$. Indeed, for each colouring in $B$, there are two paths. Since they do not intersect, one of them must be at the top of the other. We reflect that path with respect to the vertical axis of symmetry of the $2m\times n$ board. That is, for each square in the path we exchange it with the corresponding square across the axis Then the resulting path must be an element of $A$. It is easy to see that this is an injection so we are done.

Consider any pair of boards, one of which is any board and the other is a color with two non-intersecting black paths from the left to the right edge. Since the paths are non-intersecting, if we cut the first board along the top border of the lower path, the upper path is unaffected. $~$ Now, make make the same cut on the other board, which can be any board, and switch the lower sections of the paths. This creates two boards, each with at least one black path. Note that following these rules, there is at most one way to revert two boards with at least one black path into a board with at least two black paths. Thus, we are done.

It suffices to show that there is an injection from every pair of colorings represented in $N^2$ to one represented in $M \cdot 2^{mn}$. Pick two boards, one board one of the $M$ that contain two non-intersecting paths, and another board which is arbitrary. Consider the following transformation, where we take the path through the first board that begins at the highest $y$-coordinate and swap it with the coloring of the corresponding squares in the second grid. This creates two grids, each with at least one crossing. Furthermore, if two pairs of grids mapped to the same grid, then they must have had the same coloring of all the squares that are not part of the topmost path in the first square, and also contained the same topmost path in the first square, thereby rendering the first two squares identical. As the pattern replicated from the second square must also be identical, and the remainders of the second squares are also identical, the other two squares must also be identical; thus, the preimages are also identical as well. Thus, this transformation is an injection onto the $N^2$ boards that have at least one path, so we have $N^2 \geq M \cdot 2^{mn}$, as desired.

Neat problem. We consider the set $S$ of superior pairs of $m \times n$ boards, in which each board contains at least one path, and the set $I$ of inferior pairs of $m \times n$ boards, where the first board contains two disjoint paths and the second board is given any coloring. Note that $|S|=N^2$ and $|I|=M \cdot 2^{mn}$. Thus, it suffices to find an injection that maps $I$ to $S$. Consider any pair $(I_1, I_2)$ in $I$. Note that $I_1$ contains a lowest path. Cut the part of the $I_1$ containing this lowest path such that no cell above the path is included, and call it $I_{1L}$. The remaining portion of $I_1$ can be called $I_{1U}$. Cut out subgrids from $I_2$ with exactly the same patterns, calling the upper portion $I_{2U}$ and the lower portion $I_{2L}$. Consider the map $f: I \to S$ defined by $f(I_1, I_2)=(I_{1U} \cup I_{2L}, I_{2U} \cup I_{1L})$, whence both elements of $f(I_1, I_2)$ are grids with at least one path. Since $f$ is an injection, we have $|I| \le |S|$, as desired.

injection? problem 2022 C5 says hi