MathDB
Problems
Contests
National and Regional Contests
Greece Contests
Greece National Olympiad
2024 Greece National Olympiad
3
3
Part of
2024 Greece National Olympiad
Problems
(1)
Sets, differences and counting
Source: Greece National Olympiad 2024, Problem 3
2/24/2024
Let
n
≥
2
n \geq 2
n
≥
2
be a positive integer and let
A
,
B
A, B
A
,
B
be two finite sets of integers such that
∣
A
∣
≤
n
|A| \leq n
∣
A
∣
≤
n
. Let
C
C
C
be a subset of the set
{
(
a
,
b
)
∣
a
∈
A
,
b
∈
B
}
\{(a, b) | a \in A, b \in B\}
{(
a
,
b
)
∣
a
∈
A
,
b
∈
B
}
. Achilles writes on a board all possible distinct differences
a
−
b
a-b
a
−
b
for
(
a
,
b
)
∈
C
(a, b) \in C
(
a
,
b
)
∈
C
and suppose that their count is
d
d
d
. He writes on another board all triplets
(
k
,
l
,
m
)
(k, l, m)
(
k
,
l
,
m
)
, where
(
k
,
l
)
,
(
k
,
m
)
∈
C
(k, l), (k, m) \in C
(
k
,
l
)
,
(
k
,
m
)
∈
C
and suppose that their count is
p
p
p
. Show that
n
p
≥
d
2
.
np \geq d^2.
n
p
≥
d
2
.
combinatorics