MathDB
Problems
Contests
National and Regional Contests
Korea Contests
Korea National Olympiad
2023 Korea National Olympiad
8
8
Part of
2023 Korea National Olympiad
Problems
(1)
special number partition
Source: KMO 2023 P8
11/4/2023
For a positive integer
n
n
n
, if
n
n
n
is a product of two different primes and
n
≡
2
(
m
o
d
3
)
n \equiv 2 \pmod 3
n
≡
2
(
mod
3
)
, then
n
n
n
is called "special number." For example,
14
,
26
,
35
,
38
14, 26, 35, 38
14
,
26
,
35
,
38
is only special numbers among positive integers
1
1
1
to
50
50
50
. Prove that for any finite set
S
S
S
with special numbers, there exist two sets
A
,
B
A, B
A
,
B
such that[*]
A
∩
B
=
∅
,
A
∪
B
=
S
A \cap B = \emptyset, A \cup B = S
A
∩
B
=
∅
,
A
∪
B
=
S
[*]
∣
∣
A
∣
−
∣
B
∣
∣
≤
1
||A| - |B|| \leq 1
∣∣
A
∣
−
∣
B
∣∣
≤
1
[*] For all primes
p
p
p
, the difference between number of elements in
A
A
A
which is multiple of
p
p
p
and number of elements in
B
B
B
which is multiple of
p
p
p
is less than or equal to
1
1
1
.
combinatorics