This problem is proposed by me (Zixiang Zhou, Canada)! My original solution writeup is below: Define a good parallelogram to be a parallelogram composed of two isosceles right-angled triangles glued together: [asy][asy] usepackage("tikz"); label(" \begin{tikzpicture} \fill[purple] (0,0)--(0,1)--(1,2)--(1,1)--cycle; \fill[purple] (2,0)--(3,1)--(4,1)--(3,0)--cycle; \fill[purple] (5,1)--(5,2)--(6,1)--(6,0)--cycle; \fill[purple] (7,1)--(8,1)--(9,0)--(8,0)--cycle; \end{tikzpicture} "); [/asy][/asy] Consider the problem of packing the maximum number of good parallelograms into an $N \times N$ grid. It suffices to prove that we must leave an area of at least $N$ empty, as given any partition into $k$ rightdown or rightup paths, we can find a corresponding packing of good parallelograms leaving an area of $k$ empty: [asy][asy] usepackage("tikz"); label(" \begin{tikzpicture} \fill[yellow] (0,0) rectangle (1,1); \fill[yellow] (0,1) rectangle (1,2); \fill[yellow] (0,2) rectangle (1,3); \fill[yellow] (0,3) rectangle (1,4); \fill[red] (0,4) rectangle (1,5); \fill[orange] (1,0) rectangle (2,1); \fill[green] (1,1) rectangle (2,2); \fill[green] (1,2) rectangle (2,3); \fill[yellow] (1,3) rectangle (2,4); \fill[red] (1,4) rectangle (2,5); \fill[orange] (2,0) rectangle (3,1); \fill[green] (2,1) rectangle (3,2); \fill[blue] (2,2) rectangle (3,3); \fill[yellow] (2,3) rectangle (3,4); \fill[red] (2,4) rectangle (3,5); \fill[orange] (3,0) rectangle (4,1); \fill[green] (3,1) rectangle (4,2); \fill[blue] (3,2) rectangle (4,3); \fill[blue] (3,3) rectangle (4,4); \fill[blue] (3,4) rectangle (4,5); \fill[orange] (4,0) rectangle (5,1); \fill[orange] (4,1) rectangle (5,2); \fill[orange] (4,2) rectangle (5,3); \fill[orange] (4,3) rectangle (5,4); \fill[blue] (4,4) rectangle (5,5); \draw (0,0) grid (5,5); \end{tikzpicture} "); label(" \begin{tikzpicture} \filldraw[color=black,fill=yellow,thick] (1,0)--(0,1)--(0,2)--(1,1)--cycle; \filldraw[color=black,fill=yellow,thick] (1,1)--(0,2)--(0,3)--(1,2)--cycle; \filldraw[color=black,fill=yellow,thick] (1,2)--(0,3)--(0,4)--(1,3)--cycle; \filldraw[color=black,fill=yellow,thick] (0,4)--(1,4)--(2,3)--(1,3)--cycle; \filldraw[color=black,fill=yellow,thick] (1,4)--(2,4)--(3,3)--(2,3)--cycle; \filldraw[color=black,fill=red,thick] (0,5)--(1,5)--(2,4)--(1,4)--cycle; \filldraw[color=black,fill=red,thick] (1,5)--(2,5)--(3,4)--(2,4)--cycle; \filldraw[color=black,fill=blue,thick] (2,3)--(3,3)--(4,2)--(3,2)--cycle; \filldraw[color=black,fill=blue,thick] (3,3)--(3,4)--(4,3)--(4,2)--cycle; \filldraw[color=black,fill=blue,thick] (3,4)--(3,5)--(4,4)--(4,3)--cycle; \filldraw[color=black,fill=blue,thick] (3,5)--(4,5)--(5,4)--(4,4)--cycle; \filldraw[color=black,fill=green,thick] (2,3)--(1,2)--(1,1)--(2,2)--cycle; \filldraw[color=black,fill=green,thick] (1,1)--(2,2)--(3,2)--(2,1)--cycle; \filldraw[color=black,fill=green,thick] (2,1)--(3,2)--(4,2)--(3,1)--cycle; \filldraw[color=black,fill=orange,thick] (1,1)--(2,0)--(3,0)--(2,1)--cycle; \filldraw[color=black,fill=orange,thick] (2,1)--(3,0)--(4,0)--(3,1)--cycle; \filldraw[color=black,fill=orange,thick] (3,1)--(4,0)--(5,0)--(4,1)--cycle; \filldraw[color=black,fill=orange,thick] (4,1)--(4,2)--(5,1)--(5,0)--cycle; \filldraw[color=black,fill=orange,thick] (4,2)--(4,3)--(5,2)--(5,1)--cycle; \filldraw[color=black,fill=orange,thick] (4,3)--(4,4)--(5,3)--(5,2)--cycle; \draw (0,0) rectangle (5,5); \end{tikzpicture} ",(5,0),E); [/asy][/asy] To show that a packing of good parallelograms must leave an area of $N$ empty, note that it is possible to draw a $\backslash$ or a $/$ in each cell such that it does not intersect any of the good parallelograms. Now, view these segments as mirrors, and consider a laser fired from each of the $4N$ boundary edges, bouncing along these mirrors until it exits at some other edge. It is well known that this forms a bijection between the boundary edges and these laser beams altogether visit every triangular region at most once. Consider such a pair of boundary edges. There are several cases: If this is a pair of a vertical and a horizontal edge, then there must be at least one empty triangle within this beam, so there is an empty area of at least $0.5$ corresponding to this pair. If this is a pair of boundary edges from the same side of the $N \times N$ square, then there must be at least two empty triangles within this beam, so there is an empty area of at least $1$ corresponding to this pair. If this is a pair of boundary edges from opposite sides of the $N \times N$ square, then there might be no such empty area corresponding to this pair. Note that the beams do not intersect, so if case (2) occurs, then all such pairs are from vertical edges or all such pairs are from horizontal edges. WLOG let case (2) occur $t$ times and only for vertical edges. Then out of the remaining boundary edges, there are $2N$ horizontal boundary edges and $2N-2t$ vertical boundary edges. It follows that there must be at least $t$ pairs connecting a horizontal boundary edge to another horizontal boundary edge on the same side of the $N \times N$ square. Thus, the empty area is at least \[ 1(t)+0.5(2N-2t) = N \]as required.

This problem is so beautiful it deserves a place in the IMO. So sad it wasn't selected as P3 last year.

Solution with CANBANKAN. WLOG the side lengths of a square cell is 1. Step 1. Converting into covering by parallelogram. For each right-down path, cover the path by parallelograms with sides of length $\sqrt{2}$ having slope 1. For each right-up path, cover the path by parallelograms with sides of length $\sqrt{2}$ having slope $-1$. Note that in each (nontrivial) path we miss exactly area 1. Thus, if we tile by such parallelograms and show that area of at least $N$ is uncovered, we are done. [asy][asy] size(0, 3.5cm); usepackage("amsmath"); int n=6; draw(box((0,0), (n,n)), linewidth(1)); for(int i=1; i<n; ++i){ draw((i,0) -- (i,n), mediumgray); draw((0,i) -- (n,i), mediumgray); } pen p = linewidth(1); draw((1,5) -- (1,1) -- (6,1), p); draw((2,1) -- (2,4) -- (4,4) -- (4,6), p); draw((0,5) -- (4,5), p); draw((2,2) -- (5,2) -- (5,5) -- (6,5), p); draw((3,4) -- (3,3) -- (5,3), p); picture pic; pen f = mediumgray; fill(pic,(0,4)--(0,5)--(1,5)--cycle,f); fill(pic,(5,0)--(6,0)--(6,1)--cycle,f); fill(pic,(1,1)--(2,1)--(1,2)--cycle,f); fill(pic,(4,4)--(4,5)--(3,5)--cycle,f); fill(pic,(0,5)--(0,6)--(1,6)--cycle,f); fill(pic,(4,5)--(4,6)--(3,5)--cycle,f); fill(pic,(2,4)--(3,4)--(2,3)--cycle,f); fill(pic,(4,2)--(5,2)--(5,3)--cycle,f); fill(pic,(3,3)--(4,3)--(3,4)--cycle,f); fill(pic,(6,6)--(5,6)--(6,5)--cycle,f); fill(pic,(2,1)--(3,1)--(2,2)--cycle,f); fill(pic,(6,4)--(6,5)--(5,5)--cycle,f); draw(pic,box((0,0), (n,n)), linewidth(1)); pen p = linewidth(1); draw(pic,(1,5) -- (1,1) -- (6,1), p); draw(pic,(2,1) -- (2,4) -- (4,4) -- (4,6), p); draw(pic,(0,5) -- (4,5), p); draw(pic,(2,2) -- (5,2) -- (5,5) -- (6,5), p); draw(pic,(3,4) -- (3,3) -- (5,3), p); void up(real x, real y) {draw(pic,(x,y) -- (x+1,y+1), p);} void down(real x, real y) {draw(pic,(x+1,y) -- (x,y+1), p);} up(1,0); up(2,0); up(3,0); up(4,0); up(5,0); up(0,0); up(0,1); up(0,2); up(0,3); up(0,4); up(0,5); up(1,5); up(2,5); up(3,5); down(1,1); down(1,2); down(1,3); down(1,4); down(2,4); down(3,4); down(2,1); down(3,1); down(4,1); down(5,1); down(5,2); down(5,3); down(5,4); up(2,3); up(2,2); up(3,2); up(4,2); down(3,3); down(4,3); down(4,4); down(4,5); down(5,5); label("$\implies$", (7,3)); add(shift(8,0)*pic); [/asy][/asy] The remainder of this problem is Iran TST 2013. Step 2. Solving Iran TST 2013. We remove the horizontal/vertical line for a moment. Add in diagonals arbitrarily so that each square has a diagonal. [asy][asy] size(3.5cm,0); int n=6; draw(box((0,0), (n,n)), linewidth(1)); pen p = linewidth(1); void up(real x, real y) {draw((x,y) -- (x+1,y+1), p);} void down(real x, real y) {draw((x+1,y) -- (x,y+1), p);} up(1,0); up(2,0); up(3,0); up(4,0); up(5,0); up(0,0); up(0,1); up(0,2); up(0,3); up(0,4); up(0,5); up(1,5); up(2,5); up(3,5); down(1,1); down(1,2); down(1,3); down(1,4); down(2,4); down(3,4); down(2,1); down(3,1); down(4,1); down(5,1); down(5,2); down(5,3); down(5,4); up(2,3); up(2,2); up(3,2); up(4,2); down(3,3); down(4,3); down(4,4); down(4,5); down(5,5); [/asy][/asy] There are $2N$ connected regions by Euler's formula. Moreover, each region must enter and exit the grid (there cannot be a dead end). Thus each region uses exactly two boundary edges of the square. We relate this back to parallelograms by the following. If a region uses one horizontal and one vertical edge at the boundary, then the area is half-integer, so an area of at least $\tfrac 12$ is uncovered. To see this, split the region into several $1$-$1$-$\sqrt 2$ triangles and walk through them in order. Each transition switch the orientation of the edge (from horizontal to vertical and vice versa), so one must pass through an odd number of triangles, and so the area must be half-integer. If a region uses two segments on the same side of the border, then at least area $1$ in that region is uncovered. To see this, note that if a region is completely covered by parallelograms, then it must keep going up until it reaches opposite side. These two observations are enough to finish the problem: if there are no laser paths from one side of the border to the opposite side of the border, then each region has at least $\tfrac 12$ uncovered area. Otherwise, suppose a laser path connects the top of the border to the bottom of the border, then one cannot have a region from left vertical edge to right vertical edge. Thus, every vertical line segment contribute at least $\tfrac 12$ to the uncovered area. There are $2N$ vertical lines, so we are forced to have uncovered area of at least $2N\cdot\tfrac 12 = N$.

Here is another solution sketch: Induct on $N$. Force a path from bottom left square to top right square, possibly splitting other paths. Remove the path, and glue the parts together to form a $(N-1) \times (N-1)$ square. It turns out the other parts that are split gets glued back.

CANBANKAN wrote: It turns out the other parts that are split gets glued back. Why? It does't seem like to be correct in all cases.

MathGuy1729 wrote:

YaoAOPS wrote: What exactly are red cells here? A red cell is any cell that's not blue (so a path doesn't start there) and the previous square of the path passing through it isn't the cell left to it, so it is reached from above or from below. Quote: And are these diagonals taken from the center of cells? You can look at it that way, doesn't really matter. The important part is that they connect two diagonally adjacent cells. Quote: Why is there an "arrow path" from the first column to the last column Each cell in the first column is blue or red. Now, for every cell in the first column, follow the arrows until possible. This may only end by reaching a blue cell or the last column. However, there are $N$ cells in the first column, at most $N-1$ blue cells, and each blue cell can stop you at most once, so for at least one cell in the first column, you reach the last column. Hope this was helpful.

zhycongcong wrote: CANBANKAN wrote: It turns out the other parts that are split gets glued back. Why? It does't seem like to be correct in all cases. From what I've heard, if you force the path randomly, then no, they don't get glued back, but there is always a way to force the path so that they do end up getting glued. I don't quite remember how exactly that's done, though.

old Iran TST 2013

I think I have a different solution. Let there be a partition with $M$ parts. We'll show that $M\geq N$ must hold. We'll need the following lemma Lemma: It is possible to enumerate the the paths with numbers from $1$ to $M$ such that in each for every pair of paths, say with numbers $a$ and $b$ ($a>b$), the path $b$ doesn't "lies over" the path $a$. Here "lying over" means, that for any column intersecting both paths the the $a$ path lies over the $b$ path in that column. proof: It is kind of annoying to explain, so I'll keep it short. the proof goes more or less as follows. It doesn't matter with which numbers we enumerate, be it $1, 2, ..., M$ or some other set of distinct real numbers, so we'll enumerate with real numbers. We start with the observation that path A lies over path B if in at least one column which they both intersect A lies over B (it follows from the property of the paths). Now we finally start enumerating. We start with the left-most column. We enumerate the paths crossing it with some real numbers in the right order. Now we go to the next column. The new paths that cross this column we enumerate with real numbers accordingly. and so on. Because of the property already mentioned this enumeration works. Now convert the real numbers into $1, 2, ..., M$. Assume $M<N$. Now we draw the paths in the order $1, 2, ... M$ step by step. We will prove the following. Right after the $i-1$-th step of the procedure, the $i$-th row from below is going to have atleast $n-i+1$ cells which are not yet occupied by paths for $M+1\geq i\geq 1$(the $0$-th step is the beginning). If we use this fact for $i=M$, then there would be at least 1 cell that is not occupied by the paths and we are done, contradiction. Now it remains to prove this fact. For $i=1$ it is obvious. Assume it is proven for $i$. Let $a_1, a_2, ..., a_{n-i+1}$ be the unoccupied cells in the $i$-th row. We now draw in the $i$-th path. Let $b_k$ be the cell right above $a_k$. Then it is not hard to see, be the enumeration criterion, that if the last path contains $b_k$ it must also contain $a_k$ (otherwise look at the path containing $a_k$). Now we are done if only one $b_k$ is in the last path. If there would be two, for example $b_i$ and $b_j$ then $a_i, a_j, b_i, b_j$ would all be contained in the path, the impossibility of which is easily seen. Now we are done.

Posted an incoherent sketch in post #9. Here's it fully texed out with too many diagrams. Call a path which would go $3$ of the corners of the board (and thus consists of two directions) an amogus. We will induct down on $N$ by forcing amogii. Call the orientation of a path whether it goes right-up or right-down. First, note that if we have the end of a piece $A$ extending into a corner $B$, we can actually the end of the piece and repeatedly move corners as necessary. [asy][asy] int W=5; int H=3; int T=7; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dashed ); draw( (i+T,0)--(i+T,H), rgb("333333")+dashed ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dashed ); draw( (0+T,i)--(W+T,i), rgb("333333")+dashed ); } label("$\mapsto$", (6, 1.5)); pen p1 = blue+white+white; pen p2 = green+white+white; filldraw((0,0)--(0,1)--(2,1)--(2,0)--cycle, p1); filldraw((2,0)--(2,3)--(3,3)--(3,1)--(5,1)--(5,0)--cycle, p2); filldraw((3,1)--(5,1)--(5,2)--(4,2)--(4,3)--(3,3)--cycle, p2); filldraw((T+0,0)--(T+0,1)--(T+3,1)--(T+3,0)--cycle, p1); filldraw((T+2,1)--(T+2,3)--(T+3,3)--(T+3,2)--(T+4,2)--(T+4,1)--(T+5,1)--(T+5,0)--(T+3,0)--(T+3,1)--cycle, p2); filldraw((T+3,2)--(T+3,3)--(T+5,3)--(T+5,1)--(T+4,1)--(T+4,2)--cycle, p2); label("$A$", (1.5, 0.5)); label("$B$", (2.5, 0.5)); label("$C$", (3.5, 1.5)); label("$A$", (T+2.5, 0.5)); label("$B$", (T+3.5, 1.5)); label("$C$", (T+4.5, 2.5)); [/asy][/asy] This means that if any path has an end in the bottom row, we can extend this end as much as we want in a certain direction. If we can cover the entire bottom row with such a path, we can then further extend to get an amogus. This means we can induct on $N$ and finishes. Else, the best we can do is $2$. Label these two pieces $T_0$ and $L_0$ where $T_0$ goes through the bottom left corner and $L_0$ the bottom right. These two pieces must have opposite orientations, so one of the two most two edges in the path, WLOG let it be $L_0$. [asy][asy] int W=8; int H=6; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dashed ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dashed ); } pen p1 = orange+white+white; pen p2 = blue+white+white; pen p3 = green+white+white; pen p4 = red+white+white; filldraw((0,0)--(2,0)--(2,3)--(1,3)--(1,1)--(0,1)--cycle, p1); filldraw((2,0)--(2,5)--(3,5)--(3,1)--(8,1)--(8,0)--cycle, p1); label("$T_0$", (1.5,2.5)); label("$L_0$", (2.5,4.5)); [/asy][/asy] Our next goal is to force $L_0$ to consist of either just a horizontal piece, just a vertical piece, or extend to the top of the board. In the first two cases, we can extend to get an amogus. In the third case, we can swap the order of the two edges in $L_0$ to make it go through two corners (which preserves other paths), and then extend to get an amogus. The issue we run into when trying to extend the vertical part of $L_0$ is that we hit a path above which we can't immediately cut through. Call this path the bar $B$. Call a path which goes right-down and has a vertical end below the bar, an cutter. We also consider $1 \times 1$ paths cutters. Call the edge between $B$ and $L_0$, and all horizontal edges of the same height touching $L_0$, the pushzone of the bar. [asy][asy] int W=8; int H=6; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dashed ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dashed ); } pen p1 = orange+white+white; pen p2 = blue+white+white; pen p3 = green+white+white; pen p4 = red+white+white; filldraw((0,0)--(2,0)--(2,3)--(1,3)--(1,1)--(0,1)--cycle, p1); filldraw((2,0)--(2,5)--(3,5)--(3,1)--(8,1)--(8,0)--cycle, p1); filldraw((1,5)--(1,6)--(8,6)--(8,4)--(7,4)--(7,5)--cycle, p3); draw((2,5.05)--(7,5.05), red); draw((1,5.05)--(2,5.05), purple); label("$T_0$", (1.5,2.5)); label("$L_0$", (2.5,4.5)); label("$B$", (1.5, 5.5)); [/asy][/asy] We also allow for some number of strictly vertical paths between $T_0$ and $L_0$, labelled $C_1, \dots, C_k$ from left to right. This serves as a bounded monovariant. Claim: Given $L_0$, we can get cutters under all of the pushzone right of the edge between $B$ and $L_0$ (the red edges in the above diagram), or win by getting a amogus, potentially getting more vertical paths. Proof. We induct on the distance between the pushzone and the bottom edge of the board. If the distance is $0$, we can get an amogus and terminate. Else, starting from $L_0$, we look at the paths containing the cells right of the top cell of $L_0$ one by one. Suppose we get a few cutters $L_1, \dots, L_n$ before hitting a noncutter. Then consider the first cell which is not in a cutter (if they are all cutters, we are done). First suppose the path $S$ containing it is also right-down. [asy][asy] int W=8; int H=6; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dashed ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dashed ); } pen p1 = orange+white+white; pen p2 = blue+white+white; pen p3 = green+white+white; pen p4 = red+white+white; filldraw((0,0)--(2,0)--(2,3)--(1,3)--(1,1)--(0,1)--cycle, p1); filldraw((2,0)--(2,5)--(3,5)--(3,1)--(8,1)--(8,0)--cycle, p1); filldraw((3,1)--(3,5)--(4,5)--(4,2)--(6,2)--(6,1)--cycle, p2); filldraw((4,2)--(4,5)--(5,5)--(5,3)--(6,3)--(6,2)--cycle, p2); filldraw((1,5)--(1,6)--(8,6)--(8,4)--(7,4)--(7,5)--cycle, p3); draw((2,5.05)--(7,5.05), red); draw((1,5.05)--(2,5.05), purple); filldraw((5,4)--(5,5)--(7,5)--(7,3)--(6,3)--(6,4)--cycle, p4); label("$T_0$", (1.5,2.5)); label("$L_0$", (2.5,4.5)); label("$L_1$", (3.5,4.5)); label("$L_2$", (4.5,4.5)); label("$S$", (5.5,4.5)); label("$B$", (1.5, 5.5)); [/asy][/asy] Then the idea is that we can extend $S$ and induct down. The pushzone of $S$ is chosen by us so that after getting our cutters, we can induct up and $S$ is now a cutter. [asy][asy] int W=8; int H=6; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dashed ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dashed ); } pen p1 = orange+white+white; pen p2 = blue+white+white; pen p3 = green+white+white; pen p4 = red+white+white; filldraw((0,0)--(2,0)--(2,3)--(1,3)--(1,1)--(0,1)--cycle, p1); filldraw((2,0)--(2,4)--(3,4)--(3,1)--(8,1)--(8,0)--cycle, p1); filldraw((3,1)--(3,4)--(4,4)--(4,2)--(6,2)--(6,1)--cycle, p2); filldraw((4,2)--(4,4)--(5,4)--(5,3)--(6,3)--(6,2)--cycle, p2); filldraw((1,5)--(1,6)--(8,6)--(8,4)--(7,4)--(7,5)--cycle, p3); draw((2,5.05)--(7,5.05), red); draw((1,5.05)--(2,5.05), purple); filldraw((2,4)--(2,5)--(7,5)--(7,3)--(6,3)--(6,4)--cycle, p4); label("$T_0$", (1.5,2.5)); label("$L_0$", (2.5,3.5)); label("$L_1$", (3.5,3.5)); label("$L_2$", (4.5,3.5)); label("$S$", (2.5,4.5)); label("$B$", (1.5, 5.5)); [/asy][/asy] Next, suppose $S$ is part of a right-up piece. [asy][asy] int W=8; int H=6; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dashed ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dashed ); } pen p1 = orange+white+white; pen p2 = blue+white+white; pen p3 = green+white+white; pen p4 = red+white+white; filldraw((0,0)--(2,0)--(2,3)--(1,3)--(1,1)--(0,1)--cycle, p1); filldraw((2,0)--(2,5)--(3,5)--(3,1)--(8,1)--(8,0)--cycle, p1); filldraw((3,1)--(3,5)--(4,5)--(4,2)--(6,2)--(6,1)--cycle, p2); filldraw((4,2)--(4,5)--(5,5)--(5,3)--(6,3)--(6,2)--cycle, p2); filldraw((1,5)--(1,6)--(8,6)--(8,4)--(7,4)--(7,5)--cycle, p3); draw((2,5.05)--(7,5.05), red); draw((1,5.05)--(2,5.05), purple); filldraw((5,4)--(5,5)--(7,5)--(7,4)--(6,4)--(6,3)--(5,3)--cycle, p4); label("$T_0$", (1.5,2.5)); label("$L_0$", (2.5,4.5)); label("$L_1$", (3.5,4.5)); label("$L_2$", (4.5,4.5)); label("$S$", (5.5,3.5)); label("$B$", (1.5, 5.5)); [/asy][/asy] Then by repeatedly extending the vertical end of $S$ downward, it allows us to swap the vertical edge of $S$ with $L_n$, then with $L_{n-1}$, all the way down to $L_0$. [asy][asy] int W=8; int H=6; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dashed ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dashed ); } pen p1 = orange+white+white; pen p2 = blue+white+white; pen p3 = green+white+white; pen p4 = red+white+white; filldraw((0,0)--(2,0)--(2,3)--(1,3)--(1,1)--(0,1)--cycle, p1); filldraw((3,0)--(3,4)--(4,4)--(4,1)--(8,1)--(8,0)--cycle, p1); filldraw((4,1)--(4,4)--(5,4)--(5,2)--(6,2)--(6,1)--cycle, p2); filldraw((5,2)--(5,4)--(6,4)--(6,2)--cycle, p2); filldraw((1,5)--(1,6)--(8,6)--(8,4)--(7,4)--(7,5)--cycle, p3); draw((2,5.05)--(7,5.05), red); draw((1,5.05)--(2,5.05), purple); filldraw((2,0)--(2,5)--(7,5)--(7,4)--(3,4)--(3,0)--cycle, p4); label("$T_0$", (1.5,2.5)); label("$L_0$", (3.5,3.5)); label("$L_1$", (4.5,3.5)); label("$L_2$", (5.5,3.5)); label("$S$", (2.5,0.5)); label("$B$", (1.5, 5.5)); [/asy][/asy] Then we can also inductively get cutters below $S$. After getting the cutters, we can cut through $S$, and the vertical component of $S$ becomes a vertical path. This finishes the induction as it gives us more cutters. $\blacksquare$ Now, after getting our cutters $L_0, \dots, L_k$, if $B$ is right up, we can use the process earlier to extend $L_k$, then $L_{k-1}$, till $L_0$ to push $B$ back one. If $B$ is right-down however, things are complicated. If any of $C_1, \dots, C_n$ lie below it, we can just extend them up to get more cutters. If this still doesn't cover all of $B$, then since $T_0$ borders either $C_1$ or $L_0$, to the right, it must also consist of a horizontal and vertical component. We can then extend $T_0$ as well. Now, \underline{run the same process} to get $T_0, \dots$. After doing so, we get cutters under the entirety of $B$'s pushzone, so we can push it up as well. By repeatedly pushing up and adding more vertical paths in between, we eventually force an amogus. Remark (Motivation): The solutions above of this problem I am aware of is this local argument, global arguments considering row by row, and finally global arguments with magical mirror reflections. If anyone knows how in the world the third class of solutions is motivated, please tell me! Anyways the motivation for this solution is noticing that a path touching two distinct edges of the board at a not corner is a win condition.

Really nice problem! Glad that I was able to find the "magical" solution. Call a parallelogram nice iff it consists of two $45-45-90$ triangles pasted together, cover the right-down and right-up paths with nice parallelograms leaving an isosceles right triangle at borders of the path, it suffices to show that in a tiling of nice parallelograms, at least an area of $n$ is left where the square has dimensions $n \cdot n$, now we can place a mirror inside each cell so that it does not intersect nice parallelograms, it is clear by construction that there are $4n$ boundary edges, fire a laser from each of these boundary edges, it is clear that a laser can't visit a triangle more than once, now we break into cases, If it is a pair of boundary edges on same side of the square, in this case there are at least two empty triangles within the laser beam, yielding area of $1$ If it is pair of boundary edges opposite sides of square then there might not be a triangle, contributing $0$ If it is a pair of horizontal and vertical edge then we must have at least one triangle contributing $1/2$ to our sum. Notice that by construction the beams do not intersect, so if the last case occurs then it must come from vertical edges or horizontal edges, assume last case occurs $p$ times, there $2n$ horizontal boundaries and $2n-2p$ vertical, it follows there are atleast $t$ pairs connecting horizontal boundary to another horizontal one, yielding that the empty area is at least $n$, as desired. Remark 1:[Motivational] There are essentially two ways of approaching this problem, local arguments doing minor optimizations and inducting, and second, global approach by breaking into parallelogram, I went with the global approach, I decided to divide the grid into parallelograms as I noticed that by marking the small isosceles right triangles determines the right up/down path, next the structure of the reduced problem reminded me of MEMO 2015 MellowMelon's solution (apparently doing some physics also helps to motivate the lasers solution), and then the solution was found by some experimenting with where to fire the lasers. Remark 2: (Question) As there are so many equality cases, should there exist an algebraic solution? I tried using generating functions but got nowhere.

This is a really beautiful problem, and I think I have something new to add to the discussion with a novel inductive solution. First, let's simplify terminology and call both types of paths zigzags. Consider instead the paths made by the drawn edges inside the grid. I shall call these edge paths, as opposed to grid paths that the problem defines. I claim that in an $N\times N$ grid, there are $T-1$ distinct edge paths, where $T$ is the number of grid paths. Proof: Consider the graph with vertices at the vertices of the grid. Every time we draw an edge path, we add two degree 3 vertices to the graph (here, we consider a degree 4 vertex as two degree 3 vertices; imagine if two opposite edges don't quite align). In that case, how many degree 3 vertices are in the final drawing? [asy][asy] size(4cm); draw((5,-1)--(0,-1)--(0,-2)--(5,-2)--(5,-3)--(0,-3)--(0,-4)--(5,-4),gray+linewidth(0.5)+miterjoin); draw((1,-5)--(1,0)--(2,0)--(2,-5)--(3,-5)--(3,0)--(4,0)--(4,-5),gray+linewidth(0.5)+miterjoin); draw((0,0)--(5,0)--(5,-5)--(0,-5)--cycle,black+linewidth(2.5)+miterjoin); draw((0,-1)--(3,-1)--(3,-2)--(1,-2)--(1,-4)--(4,-4)--(4,-3)--(2,-3)--(2,-2),black+linewidth(2.5)+miterjoin); draw((3,0)--(3,-1),black+linewidth(2.5)+miterjoin); draw((1,-4)--(1,-5),black+linewidth(2.5)+miterjoin); draw((4,-3)--(4,-1)--(5,-1),black+linewidth(2.5)+miterjoin); filldraw((0, -1)--(3, -1)--(3, -2)--(1, -2)--(1, -5)--(0, -5)--cycle,white,white+linewidth(2.5)+miterjoin); draw((0, -1)--(3, -1)--(3, -2)--(1, -2)--(1, -5),black+linewidth(2.5)+miterjoin); draw((1, -5)--(0, -5)--(0, -1),grey+linewidth(1)+miterjoin+dashed); filldraw(circle((3, 0), 0.15)); filldraw(circle((0, -1), 0.15)); filldraw(circle((3, -1), 0.15)); filldraw(circle((5, -1), 0.15)); filldraw(circle((2, -2), 0.15)); filldraw(circle((4, -3), 0.15)); filldraw(circle((1, -4), 0.15)); filldraw(circle((1, -5), 0.15)); [/asy][/asy] Notice that if we remove a single grid path, then two degree 3 vertices reduce to degree 2, all the way until we have a single grid path left over. Thus, the number of degree 3 vertices is exactly $2(T-1)$, implying the number of edge paths is exactly $T-1$. Now, I claim there is a special choice of edge paths that are all zigzags. First, draw the $T-1$ edge paths such that the arms of every degree 3 $\top$ are part of the same path (for a degree 4 $+$ the arms are part of the same path, and the tip and stem are part of two additional paths). Note that this way the only points edge paths turn are at degree 2 vertices. Suppose not all edge paths are zigzags, so there exist some paths containing a $\sqcup$-shaped segment. For every such $\sqcup$ we encounter, there must be a degree 3 node in the center; otherwise, since the turns are degree 2 there is only a single grid path surrounding this edge path, creating a U-shaped grid path which is not allowed. This degree 3 node is the start of a new path; depending on which way the first turn goes, we rewire this node such that the appropriate arm of the $\sqcup$ is attached to this new path. [asy][asy] size(7cm); draw((3,-2)--(3,-3)--(1,-3),black+linewidth(2.5)+miterjoin); draw((0,0)--(0,-2)--(4,-2)--(4,-1),lightred+linewidth(2.5)+miterjoin); draw((4.5,-1.5)--(5.5,-1.5),black,arrow=Arrow); draw((6,0)--(6,-2)--(9,-2),black+linewidth(2.5)+miterjoin); draw((10,-1)--(10,-2)--(9,-2)--(9,-3)--(7,-3),lightred+linewidth(2.5)+miterjoin); [/asy][/asy] This operation strictly decreases the number of $\sqcup$ path segments that exist whilst maintaining the zigzag of the edited path segments. However, it also allows turns to occur at vertices with degree more than 2. This is okay as we see that this degree 3 turn is surrounded on both sides by turns of the correct orientation and thus cannot be part of another $\sqcup$ shaped path. So eventually we will no longer have any $\sqcup$ occurrences. [asy][asy] size(4cm); draw((5,-1)--(0,-1)--(0,-2)--(5,-2)--(5,-3)--(0,-3)--(0,-4)--(5,-4),gray+linewidth(0.5)+miterjoin); draw((1,-5)--(1,0)--(2,0)--(2,-5)--(3,-5)--(3,0)--(4,0)--(4,-5),gray+linewidth(0.5)+miterjoin); draw((0,0)--(5,0)--(5,-5)--(0,-5)--cycle,black+linewidth(2.3)+miterjoin); draw((0,-1)--(3,-1)--(3,-2)--(1,-2)--(1,-4)--(4,-4)--(4,-3)--(2,-3)--(2,-2),black+linewidth(2.3)+miterjoin); draw((3,0)--(3,-1),black+linewidth(2.3)+miterjoin); draw((1,-4)--(1,-5),black+linewidth(2.3)+miterjoin); draw((4,-3)--(4,-1)--(5,-1),black+linewidth(2.3)+miterjoin); draw((0,-1)--(3,-1),lightred+linewidth(2.5)+miterjoin); draw((3,0)--(3,-2)--(1,-2)--(1,-5),lightgreen+linewidth(2.5)+miterjoin); draw((5,-1)--(4,-1)--(4,-4)--(1,-4),lightblue+linewidth(2.5)+miterjoin); draw((2,-2)--(2,-3)--(4,-3),lightcyan+linewidth(2.5)+miterjoin); [/asy][/asy] After establishing all our edge paths are zigzags, we now view them in a different light, as the backbones of a new grid path tiling of an $(N-1)\times (N-1)$ grid! To see this, we simultaneously take every instance of $\top$ and erase the stem. [asy][asy] size(9cm); for(int i=1;i<=4;++i){ draw((i,0)--(i,-5),gray(0.9)+linewidth(0.5)+miterjoin); draw((0,-i)--(5,-i),gray(0.9)+linewidth(0.5)+miterjoin); } draw((0,0)--(5,0)--(5,-5)--(0,-5)--cycle,gray(0.8)+linewidth(2.5)+miterjoin); draw((1,-1)--(2,-1),black+linewidth(3)+miterjoin); draw((3,-1)--(3,-2)--(1,-2)--(1,-4),black+linewidth(3)+miterjoin); draw((2,-3)--(3,-3),black+linewidth(3)+miterjoin); draw((2,-4)--(4,-4)--(4,-1),black+linewidth(3)+miterjoin); draw((5.5,-2.5)--(6.5,-2.5),black,arrow=Arrow); for(int i=1;i<=3;++i){ draw((7+i,-0.5)--(7+i,-4.5),gray+linewidth(0.5)+miterjoin); draw((7,-0.5-i)--(11,-0.5-i),gray+linewidth(0.5)+miterjoin); } draw((7,-0.5)--(11,-0.5)--(11,-4.5)--(7,-4.5)--cycle,black+linewidth(2.5)+miterjoin); draw((7,-1.5)--(9,-1.5)--(9,-0.5),black+linewidth(2.5)+miterjoin); draw((10,-0.5)--(10,-2.5)--(8,-2.5)--(8,-4.5),black+linewidth(2.5)+miterjoin); draw((8,-3.5)--(10,-3.5)--(10,-2.5),black+linewidth(2.5)+miterjoin); draw((7,-1.5)--(9,-1.5)--(9,-0.5),black+linewidth(2.5)+miterjoin); [/asy][/asy] This tiling uses $T-1$ grid paths, but by induction the number of grid paths used must be at least $N-1$. Thus, the number of grid paths $T$ used to tile the $N\times N$ grid must in fact be at least $N$, as desired!

WOW this was a great problem(headsolved ) I wont highlight the details but the main idea was to induct by path manipulation. Force a path between the top left corner and bottom right corner, delete the path, merge the 2 halves and induct Though was quite sad though that i didnt get the magical parrelelogram solution