MathDB
Problems
Contests
National and Regional Contests
Korea Contests
Korea National Olympiad
2012 Korea National Olympiad
4
Large subset of pairs satisfying a divisibility condition
Large subset of pairs satisfying a divisibility condition
Source: Korea National 2012 Problem 8
August 19, 2012
modular arithmetic
pigeonhole principle
combinatorics proposed
combinatorics
Problem Statement
Let
p
≡
3
(
m
o
d
4
)
p \equiv 3 \pmod{4}
p
≡
3
(
mod
4
)
be a prime. Define
T
=
{
(
i
,
j
)
∣
i
,
j
∈
{
0
,
1
,
⋯
,
p
−
1
}
}
∖
{
(
0
,
0
)
}
T = \{ (i,j) \mid i, j \in \{ 0, 1, \cdots , p-1 \} \} \smallsetminus \{ (0,0) \}
T
=
{(
i
,
j
)
∣
i
,
j
∈
{
0
,
1
,
⋯
,
p
−
1
}}
∖
{(
0
,
0
)}
. For arbitrary subset
S
(
≠
∅
)
⊂
T
S ( \ne \emptyset ) \subset T
S
(
=
∅
)
⊂
T
, prove that there exist subset
A
⊂
S
A \subset S
A
⊂
S
satisfying following conditions: (a)
(
x
i
,
y
i
)
∈
A
(
1
≤
i
≤
3
)
(x_i , y_i ) \in A ( 1 \le i \le 3)
(
x
i
,
y
i
)
∈
A
(
1
≤
i
≤
3
)
then
p
∤
x
1
+
x
2
−
y
3
p \not | x_1 + x_2 - y_3
p
∣
x
1
+
x
2
−
y
3
or
p
∤
y
1
+
y
2
+
x
3
p \not | y_1 + y_2 + x_3
p
∣
y
1
+
y
2
+
x
3
. (b)
8
n
(
A
)
>
n
(
S
)
8 n(A) > n(S)
8
n
(
A
)
>
n
(
S
)
Back to Problems
View on AoPS