IMO 3J, Mock Exam 1

We proceed by mathematical induction on $N$. Suppose the statement holds for $N-1$. Consider the path $P$ containing the topmost-leftmost cell. If $P$ is a right-up path, then all cells of $P$ lie in the topmost row or in the rightmost column. This means that when we remove the topmost row or the rightmost column, the remaining $(N-1) \times (N-1)$ grid together with the corresponding partition on it still satisfies the conditions of the problem, so by the induction hypothesis it is partitioned into at least $N-1$ paths, and hence the original $N \times N$ grid is partitioned into at least $N$ pieces.
Thus we only need to consider the case where $P$ is a right-down path. The key observation here is: if $P$ contains the bottommost-rightmost cell, then the two regions separated by $P$ can be merged into a single $(N-1) \times (N-1)$ grid (as shown in the figure below), so by the induction hypothesis the sub-grid has at least $N-1$ paths, and therefore the original $N \times N$ grid has at least $N$ paths.

Now suppose $P$ is a right-down path that does not contain the bottommost-rightmost cell. We will construct, according to the following procedure, a right-down path $Q$ from the topmost-leftmost cell to the bottommost-rightmost cell. Let $Q_0 = P$. For each $i \ge 0$, consider the bottommost-rightmost cell $q_i$ of $Q_i$, let the cells to its right and below it be $r_i$ and $d_i$, and let the paths containing them be $R_i$ and $D_i$ respectively.
Depending on the case, we add different cells to $Q_i$ to expand it into $Q_{i+1}$ (if multiple cases apply simultaneously, we may choose any one of them):
(a) If $R_i(D_i)$ is a right-down path, then we add to $Q_i$ the portion of $R_i(D_i)$ from $r_i(d_i)$ to its endpoint;
(b) If $R_i$ is a right-up path whose starting point is $r_i$, then we add to $Q_i$ the cells of $R_i$ lying in the same row as $r_i$;
(c) If $D_i$ is a right-up path whose ending point is $d_i$, then we add to $Q_i$ the cells of $D_i$ lying in the same column as $d_i$;
(d) If none of the above hold, then it must be that $R_i = D_i$, in which case we add $d_i$ and the cell to its right to $Q_i$.
We repeat this operation until no further expansion is possible. It is clear that the resulting expanded $Q$ is a right-down path from the topmost-leftmost cell to the bottommost-rightmost cell, so the two regions separated by $Q$ can be merged into a single $(N-1) \times (N-1)$ grid. However, unlike the discussion for $P$, $Q$ is not one of the paths in the original partition, so $Q$ may split some original path $X$ into two pieces.
We now show that being split into two pieces cannot actually occur, so that we may proceed with the same argument as for $P$. Consider the intersection point $x$ of $X$ and $Q$:
- If $x$ arises from case (a) above, then $Q$ contains the latter half of $X$, so after removing $Q$, $X$ remains a single right-down path;
- If $x$ arises from case (b) or (c) above, then $Q$ contains the former half or the latter half of $X$, so after removing $Q$, $X$ remains a single right-up path;
- If $X$ arises from case (d) above, then since $X \cap Q$ consists of exactly two cells, we see that after removing $Q$, the two pieces into which $X$ is split will rejoin exactly into a single right-up path.
Hence the situation of splitting into two pieces described above cannot occur, so by the induction hypothesis and the same argument as for $P$, we know that the original $N \times N$ grid must be partitioned into at least $N$ paths. This completes the proof.