Three sets having the same color

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

Three sets having the same color

G H J

Reveal topic tags

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

Source: Iran 3rd round 2012-Special Lesson exam-Part 2-P3

The post below has been deleted. Click to close.

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

1347 posts

#1 h Sep 15, 2012, 10:47 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

Prove that if $n$ is large enough, then for each coloring of the subsets of the set $\{1,2,...,n\}$ with $1391$ colors, two non-empty disjoint subsets $A$ and $B$ exist such that $A$ , $B$ and $A\cup B$ are of the same color.

Z K Y

The post below has been deleted. Click to close.

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

1354 posts

#2 h Sep 15, 2012, 9:39 PM • 6 Y

Y by ArefS, Adventure10, quantam13, and 3 other users

Consider a complete graph $G$ with vertex $v_1,v_2 , \dots , v_{n+1}$ and for $1 \leq i < j \leq n+1$ color the edge between $v_i , v_j$ with color of $\left \{ i,i+1,\dots , j-1 \right \}$ . Now if $n > R_{1391}$ there is a monochromatic triangle in $G$ , namely $v_x v_y v_z$ for $x<y<z$ . Then these three sets got same color :
$A= \left \{x,x+1,\dots , y-1 \right \}$ , $B= \left \{y,y+1,\dots , z-1 \right \}$ , $A \cup B = \left \{x,x+1,\dots , z-1 \right \}$

Z K Y

The post below has been deleted. Click to close.

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

130 posts

#3 h May 30, 2025, 12:02 PM

Y by

Draw a complete graph on $n+1$ vertices and label them with the integers from $1$ to $n+1$ . For $1\le i<j\le n+1$ , color the edge between $i$ and $j$ the color of the subset $\left \{ i,i+1,\dots , j-1 \right \}$ . For a sufficiently large $n$ , this graph has a monochromatic triangle, say between vertices $a<b<c$ . Then we get that the sets $A= \left \{a,x+1,\dots , b-1 \right \}\text{ and }\{b,b+1,\dots, c-1\}$ are our desired sets.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a