too many equality cases

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

too many equality cases

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2023 ISL C6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

388 posts

#1 h Jul 17, 2024, 12:12 PM • 5 Y

Y by OronSH, Therealway, CatinoBarbaraCombinatoric, ohiorizzler1434, Rounak_iitr

Let $N$ be a positive integer, and consider an $N \times N$ grid. A right-down path is a sequence of grid cells such that each cell is either one cell to the right of or one cell below the previous cell in the sequence. A right-up path is a sequence of grid cells such that each cell is either one cell to the right of or one cell above the previous cell in the sequence.

Prove that the cells of the $N \times N$ grid cannot be partitioned into less than $N$ right-down or right-up paths. For example, the following partition of the $5 \times 5$ grid uses $5$ paths.
$[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); [/asy]$
Proposed by Zixiang Zhou, Canada

This post has been edited 8 times. Last edited by Scilyse, Jan 23, 2025, 12:41 PM
Reason: add "proposed by"

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1 post

#2 h Jul 17, 2024, 12:13 PM • 26 Y

Y by OronSH, math90, ehuseyinyigit, peace09, YaoAOPS, Jalil_Huseynov, InternetPerson10, CyclicISLscelesTrapezoid, awesomeguy856, L567, carefully, khina, Seicchi28, ihatemath123, IAmTheHazard, PEKKA, Supercali, GeoKing, MathGuy1729, lethan3, EpicBird08, allin27x, SHZhang, Sedro, CatinoBarbaraCombinatoric, MonoVictor

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] 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]$
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] 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]$
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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

242 posts

#4 h Jul 17, 2024, 1:48 PM • 1 Y

Y by Rounak_iitr

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1595 posts

#5 h Jul 17, 2024, 1:48 PM • 4 Y

Y by OronSH, ehuseyinyigit, GeoKing, D.C.

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] 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]$
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] 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]$

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$ .

This post has been edited 3 times. Last edited by MarkBcc168, Jul 17, 2024, 3:08 PM
Reason: I hate aops displaystyle

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#6 h Jul 17, 2024, 2:05 PM • 3 Y

Y by ehuseyinyigit, jameskuang1112, everythingpi3141592

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

42 posts

#7 h Jul 17, 2024, 9:59 PM • 4 Y

Y by IAmTheHazard, YaoAOPS, CyclicISLscelesTrapezoid, akirakira

One more solution sketch

This post has been edited 1 time. Last edited by MathGuy1729, Jul 18, 2024, 10:55 AM
Reason: Clarification

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6 posts

#8 h Jul 18, 2024, 9:47 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1546 posts

#9 h Jul 18, 2024, 10:00 AM

Y by

MathGuy1729 wrote:

One more solution sketch

Questions

This post has been edited 1 time. Last edited by YaoAOPS, Jul 18, 2024, 10:00 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

42 posts

#10 h Jul 18, 2024, 10:51 AM • 1 Y

Y by YaoAOPS

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

42 posts

#11 h Jul 18, 2024, 11:05 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1546 posts

#12 h Jul 18, 2024, 1:26 PM

Y by

quick sketch of above

We local spam. First thing is that we can extend a
path into the corner of another path and then propagate all the effects in the direction of that corner.

Then use this process to force the bottom row to be covered by two paths (if there is one path we win and get our L). Then one of these paths can only have two segments. Call the length of the horizontal segment A and the vertical segment B, also use A and B as their name. Wlog let this path be oriented right down.

We now force A to either be 0 or B to be n. In the first case we can extend this to an entire L. In the second we can flip the steps of A and B and move all the squares in an A-1 by B-1 region.

So we now try to extend the length of B. The issue we run into is when right above the vertical segment B there's a horizontal segment part of path P which goes rightward.

We claim inductively on the length of B that for all the edges of P that are either directly above B or directly to the right of that edge, we can get a bunch of right down pieces below those edge which don't immediately go right. Call such a piece good. This allows us then to extend all of those good pieces and push the entire horizontal segment of A up if it's right up, or replace it entirely if it's right down. Either way, B increases.

As a base case, if B = 1 then either we can just immediately delete all of B and win by getting an L.

The idea then is to consider the first non good piece by iteratively going right from the top square in B. If we never hit such a piece, we can eventually push it upward and increase B.

If we hit a right down pieces which is not good, then we can just extend the horizontal part of that piece until it eats a square in B. Then we can inductively delete all of the horizontal piece above our squares and get more good pieces.

If we hit a right up path, then we can extend the downward part of the path until we hit the previous good path if necessary. This allows us to "swap" the right up path to have a longer horizontal component before going down. Repeat this until the vertical component of the path swaps with B, at which point A decreases by 1.

The result of all this is that we eventually get our desired L without increasing our number of pieces, inducting finishes.

This post has been edited 2 times. Last edited by YaoAOPS, Jul 18, 2024, 1:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

290 posts

#13 h Jul 19, 2024, 5:51 AM

Y by

old
Iran TST 2013

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

10 posts

jk2845

#14 h Jul 20, 2024, 2:28 PM • 3 Y

Y by YaoAOPS, math90, akirakira

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.

This post has been edited 1 time. Last edited by jk2845, Jul 20, 2024, 2:29 PM
Reason: minor mistake

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1546 posts

#15 h Jul 20, 2024, 10:39 PM • 1 Y

Y by popop614

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] 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]$
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] 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]$
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] 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]$
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] 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]$
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] 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]$
Next, suppose $S$ is part of a right-up piece.
$[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]$
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] 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]$
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.

This post has been edited 4 times. Last edited by YaoAOPS, Jul 21, 2024, 3:53 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

662 posts

#16 h Jul 22, 2024, 11:23 AM • 1 Y

Y by CatinoBarbaraCombinatoric

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 post has been edited 3 times. Last edited by math_comb01, Jul 22, 2024, 11:27 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bobthesmartypants

4337 posts

bobthesmartypants

#17 h Sep 22, 2024, 3:59 AM • 3 Y

Y by jp62, CatinoBarbaraCombinatoric, jameskuang1112

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] 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]$
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] 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]$
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] 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]$

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] 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]$
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!

This post has been edited 4 times. Last edited by bobthesmartypants, Sep 22, 2024, 3:18 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

126 posts

#18 h Nov 24, 2024, 3:57 AM

Y by

wow this was a great problem(headsolved :showoff:

:showoff:

)

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. The forcing path can be done by slowly bit by bit modifying the paths present so that the number of paths do not decrease. c14f335f

Although my solution was nice, i guess im abit sad that i didnt get the magical parallelogram solution

This post has been edited 28 times. Last edited by quantam13, May 9, 2025, 1:26 PM
Reason: .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1 post

#19 h Apr 21, 2025, 5:18 AM

Y by

MarkBcc168 wrote:

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] 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]$
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] 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]$

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

39 posts

#20 h May 2, 2025, 10:27 AM

Y by

I think this is basically the same as post #7. This is kind of just a sketch.

We may place N-1 X's on the grid that are the origin of the paths, and assume all paths (call them waterfalls) go down and (right or left exclusively) starting from those X's: this is equivalent to the original question.

The basic idea is to track the empty cells, call them 'gaps', in the rows: you can relate gaps to each other through diagonal steps, and show that at least 1 of the paths formed by these gaps survives until the last row, and each gap in that path has to be hit by a distinct waterfall. If there are k waterfalls starting on the top row, then there are N-k gaps on the top row.

Going row by row, all gaps must be hit by a waterfall from the left or right. If the waterfall flows from the left, draw an arrow from the gap going down-left, to create a new gap. Now, this process can only fail N-k-1 times (if an X is blocking the way of the new gap), so there will always be a gap-path going down to the bottom row. Also we can show that a waterfall only hits the gap-path once: Once it hits a gap, its direction is determined, and to hit the gap again, the gap path must cross over the waterfall which is a contradiction. Hence there exists a path of gaps that is N long, but is only hit by N-1 waterfalls, contradiction.

First 45+ mohs question yay.

This post has been edited 1 time. Last edited by mathfun07, May 2, 2025, 10:27 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a