MathDB
Problems
Contests
National and Regional Contests
Korea Contests
Korea National Olympiad
2020 Korea National Olympiad
3
3
Part of
2020 Korea National Olympiad
Problems
(1)
High school combinatorics
Source: Korea National Olympiad P3
11/24/2020
There are n boys and m girls at Daehan Mathematical High School. Let
d
(
B
)
d(B)
d
(
B
)
a number of girls who know Boy
B
B
B
each other, and let
d
(
G
)
d(G)
d
(
G
)
a number of boys who know Girl
G
G
G
each other. Each girl knows at least one boy each other. Prove that there exist Boy
B
B
B
and Girl
G
G
G
who knows each other in condition that
d
(
B
)
d
(
G
)
≥
m
n
\frac{d(B)}{d(G)}\ge\frac{m}{n}
d
(
G
)
d
(
B
)
≥
n
m
.
combinatorics
graph