MathDB
Problems
Contests
Undergraduate contests
VTRMC
2004 VTRMC
Problem 6
Problem 6
Part of
2004 VTRMC
Problems
(1)
monochromatic Cn in 2-coloring for arbitrary n
Source: VTRMC 2004 P6
8/2/2021
An enormous party has an infinite number of people. Each two people either know or don't know each other. Given a positive integer
n
n
n
, prove there are
n
n
n
people in the party such that either they all know each other, or nobody knows each other (so the first possibility means that if
A
A
A
and
B
B
B
are any two of the
n
n
n
people, then
A
A
A
knows
B
B
B
, whereas the second possibility means that if
A
A
A
and
B
B
B
are any two of the
n
n
n
people, then
A
A
A
does not know
B
B
B
).
combinatorics