Good set of cells

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

Good set of cells

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 Vietnam IMO TST - Problem 5

The post below has been deleted. Click to close.

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

311 posts

#1 h Mar 26, 2025, 7:30 AM

Y by

There is an $n \times n$ grid which has rows and columns numbered from $1$ to $n$ ; the cell at row $i$ and column $j$ is denoted as the cell at $(i, j)$ . A subset $A$ of the cells is called good if for any two cells at $(x_1, y), (x_2, y)$ in $A$ , the cells $(u, v)$ satisfying $x_1 < u \leq x_2, v<y$ or $x_1 \leq u < x_2, v>y$ are not in $A$ . Determine the minimal number of good sets such that they are pairwise disjoint and every cell of the board belongs to exactly one good set.

This post has been edited 1 time. Last edited by wassupevery1, Mar 26, 2025, 3:57 PM

Z K Y

The post below has been deleted. Click to close.

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

33 posts

#2 h Mar 27, 2025, 2:18 PM

Y by

There is a construction for $f(2n)=f(2n+1)=n+1$ , which looks like this:
$n=5$
1 2 2 3 3
1 1 2 2 3
3 1 1 2 2
3 3 1 1 2
2 3 3 1 1
$n=6$
1 2 2 3 3 4
1 1 2 2 3 3
4 1 1 2 2 3
3 4 1 1 2 2
3 3 4 1 1 2
2 3 3 4 1 1

It is enough to prove that the size of a good set is at most $2n-1$ for a $n \times n$ table.
If we add $m$ cells on the $k$ -th column, we restrict at least $k-1$ new cells in each of the next columns. So if we mark $a_i$ =#of cells in the $i$ -th column, we know that $(a_1-1)+(a_2-1)+...+(a_{n-1}-1)+a_n\leq n$ which gives the desired result and we are done.

Z K Y

The post below has been deleted. Click to close.

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

5 posts

#3 h Mar 27, 2025, 3:31 PM

Y by

So, I'll provide a sketch for this problem.

We'll transform this problem into a coloring problem (define that a $m\times n$ grid is a grid with $m$ columns and $n$ rows). Trying to construct such a satisfied grid with $n=2,3,4,5,6,7,8,...$ gives us the minimum number of good sets is by $\left\lfloor\frac{n}{2}\right\rfloor+1.$ So we'll prove that one color cannot exist more than $2n-1$ times on a $n\times n$ grid. We'll prove by induction on $m$ that a color cannot exist more than $m+n-1$ times on a $m\times n$ grid. If this statement is true with $m=\overline{1,k},$ We'll prove that this statement is also true with $m=k+1.$ Consider a $k+1\times n$ grid, and assume that there is a color $(A)$ that exists $m+k+1$ times. There will exist two cells that are in the same column, if between these cells, there a $x$ rows, then we can remove them and have a $k+1-x\times n$ grid. There are a maximum $x$ cells that have color $A$ between these $x$ rows. So with the $k+1-x\times n$ grid, there are at least $k+1-x$ cells that have the color of $A$ unless $k=0.$ That is a contradiction if $k\ne 0,$ so that $k=0$ or two cells in the same column is adjacent. So that there are $2$ cells in the same column and they need to be adjacent. We claim that if $2$ cells in the same row are adjacent. So by construction, we point out the contradiction.

In conclusion, a color cannot exist more than $m+n-1$ times on a $m\times n$ grid. So a color cannot exist more than $2n-1$ times on a $n\times n$ grid. From this, if there are not more than $\left\lfloor\frac{n}{2}\right\rfloor$ colors on the grid, the number of cells on the grid will be at most $(2n-1)\left\lfloor\frac{n}{2}\right\rfloor<n^2.$ This is a contradiction. So the minimum number of good sets is $\left\lfloor\frac{n}{2}\right\rfloor+1.$ The construction of this problem is not hard, just use induction and my claim.

This post has been edited 1 time. Last edited by weamher, Mar 27, 2025, 3:49 PM
Reason: typo

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a