Mock 22nd Thailand TMO P4

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

Mock 22nd Thailand TMO P4

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: own

The post below has been deleted. Click to close.

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

41 posts

#1 h Apr 13, 2025, 6:53 PM

Y by

Let $n$ be a positive integer. In an $n\times n$ table, an upright path is a sequence of adjacent cells starting from the southwest corner to the northeast corner such that the next cell is either on the top or on the right of the previous cell. Find the smallest number of grids one needs to color in an $n\times n$ table such that there exists only one possible upright path not containing any colored cells.

This post has been edited 1 time. Last edited by korncrazy, Apr 13, 2025, 6:53 PM

Z K Y

The post below has been deleted. Click to close.

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

1533 posts

#2 h Apr 13, 2025, 8:39 PM

Y by

Very elegant problem.

We ignore when $n = 1$ . We now claim the answer is $n-1$ cells, for which one possible construction is covering all of the northwest to southeast diagonal but one of the corners. We now show this is minimal inductively with base case $n = 2$ . Let the one possible upright path be $\mathcal{P}$ .

First, if the first and last moves in $\mathcal{P}$ are in different directions, then the remaining cells lie in a $n-1 \times n-1$ square $S$ , and the remaining $2n-1$ squares form an $L$ . This $L$ must have a colored cell in it, else we get two paths, so we can induct down on the square to get that this doesn't hold.

Else, suppose that the first and last moves are in different directions. Then $\mathcal{P}$ intersect the southwest northeast diagonal another time at some point $C$ . Then, the path from the starting square to $C$ and from $C$ to the ending square lie in an $a \times a$ and $b \times b$ square for some $a + b = n+1$ . Since $a-1 + b-1 = n+1-2 = n-1 > n-2$ , one of the squares inductively has two paths through it, so we can induct down to finish again.

Z K Y

The post below has been deleted. Click to close.

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

66 posts

#3 h Apr 14, 2025, 4:28 AM

Y by

We claimed that the answer is $n-1$ .
The construction is to block off the second row and only left the intersection of second row and last column uncolored. Obviously, there is one path here.

Hence, suppose some coloring of $n-2$ squares yields a unique path.
Obviously, there are $2$ rows and columns that have no colored square. Denote them as $r_1, r_2$ and $c_1, c_2$ , where $r_1, c_1$ are rows and columns that are closer to the starting square. Consider a unique path $\mathcal{P}$ . This path can be divided into several paths $O \rightarrow \text{ some sequence of squares} Z_1 \rightarrow E_1 \rightarrow \text{sth we dont care} \rightarrow E_2 \rightarrow \text{ some sequence of squares} Z_2 \rightarrow X$ where $E_1$ is the first square that lies on either $r_1$ or $c_1$ in $\mathcal{P}$ . $E_2$ is the last square that lies on either $r_2$ or $c_2$ in $\mathcal{P}$ .
Denote $4$ squares $S_{i,j}$ to be intersection of $r_i$ and $c_j$ .
Comsider the following path $O \rightarrow \text{ some sequence of squares} Z_1 \rightarrow E_1 \rightarrow S_{1,1} \rightarrow S_{1,2} \rightarrow S_{2,2} \rightarrow E_2 \rightarrow \text{ some sequence of squares} Z_2 \rightarrow X$ and $O \rightarrow \text{ some sequence of squares} Z_1 \rightarrow E_1 \rightarrow S_{1,1} \rightarrow S_{2,1} \rightarrow S_{2,2} \rightarrow E_2 \rightarrow \text{ some sequence of squares} Z_2 \rightarrow X$ These $2$ paths also work. Hence, $\mathcal{P}$ isn’t unique, contradiction.

This post has been edited 2 times. Last edited by EeEeRUT, Apr 14, 2025, 4:32 AM

Z K Y

The post below has been deleted. Click to close.

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

5 posts

raghu7

#4 h Apr 14, 2025, 7:57 AM

Y by

Claim: Having less than $n-1$ colored grids in the $n\times n$ table, possess more than one upright path.

Proof

Now, if we have $n-1$ colored grids, then we may arrange them in such a way that they fill up the $2^{nd}$ column from bottom to top but one. This yields exactly one possible "upright path" going straight up from southwest corner and straight to the right to reach the northeast corner as shown in the second image.

Attachments:

This post has been edited 4 times. Last edited by raghu7, Apr 14, 2025, 8:09 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a