connected set in grid

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

connected set in grid

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: China High School Mathematics Olympics 2024 A P3

The post below has been deleted. Click to close.

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

343 posts

#1 h Sep 8, 2024, 5:06 AM

Y by

Given a positive integer $n$ . Consider a $3 \times n$ grid, a set $S$ of squares is called connected if for any points $A \neq B$ in $S$ , there exists an integer $l \ge 2$ and $l$ squares $A=C_1,C_2,\dots ,C_l=B$ in $S$ such that $C_i$ and $C_{i+1}$ shares a common side ( $i=1,2,\dots,l-1$ ).

Find the largest integer $K$ satisfying that however the squares are colored black or white, there always exists a connected set $S$ for which the absolute value of the difference between the number of black and white squares is at least $K$ .

This post has been edited 6 times. Last edited by David-Vieta, Sep 8, 2024, 5:53 AM

Z K Y

The post below has been deleted. Click to close.

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

861 posts

#2 h Sep 8, 2024, 8:26 AM • 1 Y

Y by David-Vieta

Should swap position with P1 :oops:

:oops:

Answer
Construction
Proof
General case $m\times n$ should be super hard.

Z K Y

The post below has been deleted. Click to close.

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

1 post

#3 h Sep 19, 2024, 7:22 AM

Y by

Yeah, but it's easy to falsify when proving the construction

Z K Y

The post below has been deleted. Click to close.

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

19 posts

#4 h Oct 2, 2024, 10:32 AM

Y by

make a graph.

Z K Y

The post below has been deleted. Click to close.

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

196 posts

SBYT

#5 h Jan 18, 2025, 12:48 PM

Y by

EthanWYX2009 wrote:

General case $m\times n$ should be super hard.

Yes, $m\times n$ is super hard,but I wonder the answer for $3m\times n$ .
I've found that the answer for $6\times n(n\ge 6)$ and $9\times n(n\ge 9)$ are $2n-1$ and $3n-1$ .

Z K Y

The post below has been deleted. Click to close.

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

3 posts

zmm

#6 h Apr 28, 2025, 3:52 AM

Y by

SBYT wrote:

EthanWYX2009 wrote:

General case $m\times n$ should be super hard.

Yes, $m\times n$ is super hard,but I wonder the answer for $3m\times n$ .
I've found that the answer for $6\times n(n\ge 6)$ and $9\times n(n\ge 9)$ are $2n-1$ and $3n-1$ .

$3m\times n$ . is also hard, I can‘t prove it. And $9\times n(n\ge 9)$ I only get $3n-2$ . Construction

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a