Problem 1844

We define a good parallelogram to be a parallelogram composed of two isosceles right-angled triangles glued together as shown below.

Given any partition into $k$ right-down or right-up paths, we can find a corresponding packing of good parallelograms that leaves an area of $k$ empty. Thus, it suffices to prove that we must leave an area of at least $N$ empty when we pack good parallelograms into an $N \times N$ grid. This is actually equivalent to the original problem since we can uniquely recover the partition into right-down or right-up paths from the corresponding packing of good parallelograms.


We draw one of the diagonals in each cell so that it does not intersect any of the good parallelograms. Now, view these segments as mirrors, and consider a laser entering each of the $4 N$ boundary edges (with starting direction being perpendicular to the edge), bouncing along these mirrors until it exits at some other edge. When a laser passes through a good parallelogram, its direction goes back to the original one after bouncing two times. Thus, if the final direction of a laser is perpendicular to its initial direction, it must pass through at least one empty triangle. Similarly, if the final direction of a laser is opposite to its initial direction, it must pass though at least two empty triangles. Using this, we will estimate the number of empty triangles in the $N \times N$ grid.
We associate the starting edge of a laser with the edge it exits at. Then, the boundary edges are divided into $2 N$ pairs. These pairs can be classified into three types:
(1) a pair of a vertical and a horizontal boundary edge,
(2) a pair of boundary edges from the same side, and
(3) a pair of boundary edges from opposite sides.
Since the beams do not intersect, we cannot have one type (3) pair from vertical boundary edges and another type (3) pair from horizontal boundary edges. Without loss of generality, we may assume that we have $t$ pairs of type (3) and they are all from vertical boundary edges. Then, out of the remaining boundary edges, there are $2 N$ horizontal boundary edges and $2 N-2 t$ vertical boundary edges. It follows that there must be at least $t$ pairs of type (2) from horizontal boundary edges. We know that a laser corresponding to a pair of type (1) passes through at least one empty triangle, and a laser corresponding to a pair of type (2) passes through at least two empty triangles. Thus, as the beams do not intersect, we have at least $(2 N-2 t)+2 \cdot t=2 N$ empty triangles in the grid, leaving an area of at least $N$ empty as required.

We apply an induction on $N$. The base case $N=1$ is trivial. Suppose that the claim holds for $N-1$ and prove it for $N \geqslant 2$.
Let us denote the path containing the upper left corner by $P$. If $P$ is right-up, then every cell in $P$ is in the top row or in the leftmost column. By the induction hypothesis, there are at least $N-1$ paths passing through the lower right $(N-1) \times(N-1)$ subgrid. Since $P$ is not amongst them, we have at least $N$ paths.
Next, assume that $P$ is right-down. If $P$ contains the lower right corner, then we get an $(N-1) \times(N-1)$ grid by removing $P$ and glueing the remaining two parts together. The main idea is to extend $P$ so that it contains the lower right corner and the above procedure gives a valid partition of an $(N-1) \times(N-1)$ grid.

We inductively construct $Q$, which denotes an extension of $P$ as a right-down path. Initially, $Q=P$. Let $A$ be the last cell of $Q, B$ be the cell below $A$, and $C$ be the cell to the right of $A$ (if they exist). Suppose that $A$ is not the lower right corner, and that (*) both $B$ and $C$ do not belong to the same path as $A$. Then, we can extend $Q$ as follows (in case we have two or more options, we can choose any one of them to extend $Q$ ).
1. If $B$ belongs to a right-down path $R$, then we add the part of $R$, from $B$ to its end, to $Q$.
2. If $C$ belongs to a right-down path $R$, then we add the part of $R$, from $C$ to its end, to $Q$.
3. If $B$ belongs to a right-up path $R$ which ends at $B$, then we add the part of $R$ in the same column as $B$ to $Q$.
4. If $C$ belongs to a right-up path $R$ which starts at $C$, then we add the part of $R$ in the same row as $C$ to $Q$.
5. Otherwise, $B$ and $C$ must belong to the same right-up path $R$. In this case, we add $B$ and the cell to the right of $B$ to $Q$.
Note that if $B$ does not exist, then case (4) must hold. If $C$ does not exist, then case (3) must hold.
It is easily seen that such an extension also satisfies the hypothesis (*), so we can repeat this construction to get an extension of $P$ containing the lower right corner, denoted by $Q$. We show that this is a desired extension, i.e. the partition of an $(N-1) \times(N-1)$ grid obtained by removing $Q$ and glueing the remaining two parts together consists of right-down or right-up paths.
Take a path $R$ in the partition of the $N \times N$ grid intersecting $Q$. If the intersection of $Q$ and $R$ occurs in case (1) or case (2), then there exists a cell $D$ in $R$ such that the intersection of $Q$ and $R$ is the part of $R$ from $D$ to its end, so $R$ remains a right-down path after removal of $Q$. Similarly, if the intersection of $Q$ and $R$ occurs in case (3) or case (4), then $R$ remains a right-up path after removal of $Q$. If the intersection of $Q$ and $R$ occurs in case (5), then this intersection has exactly two adjacent cells. After the removal of these two cells (as we remove $Q), R$ is divided into two parts that are glued into a right-up path.
Thus, we may apply the induction hypothesis to the resulting partition of an $(N-1) \times(N-1)$ grid, to find that it must contain at least $N-1$ paths. Since $P$ is contained in $Q$ and is not amongst these paths, the original partition must contain at least $N$ paths.