MathDB
Problems
Contests
National and Regional Contests
China Contests
China National Olympiad
2016 China National Olympiad
4
4
Part of
2016 China National Olympiad
Problems
(1)
Set where no two elements divide each other
Source: China Mathematical Olympiad 2016 Problem 4
12/17/2015
Let
n
≥
2
n \geq 2
n
≥
2
be a positive integer and define
k
k
k
to be the number of primes
≤
n
\leq n
≤
n
. Let
A
A
A
be a subset of
S
=
{
2
,
.
.
.
,
n
}
S = \{2,...,n\}
S
=
{
2
,
...
,
n
}
such that
∣
A
∣
≤
k
|A| \leq k
∣
A
∣
≤
k
and no two elements in
A
A
A
divide each other. Show that one can find a set
B
B
B
such that
∣
B
∣
=
k
|B| = k
∣
B
∣
=
k
,
A
⊆
B
⊆
S
A \subseteq B \subseteq S
A
⊆
B
⊆
S
and no two elements in
B
B
B
divide each other.
number theory