MathDB
Problems
Contests
National and Regional Contests
Korea Contests
Korea Winter Program Practice Test
2020 Korean MO winter camp
#1
#1
Part of
2020 Korean MO winter camp
Problems
(1)
Subset sum problem
Source: 2020 Korean MO winter camp Test 1 P1
9/7/2020
Call a positive integer challenging if it can be expressed as
2
a
(
2
b
+
1
)
2^a(2^b+1)
2
a
(
2
b
+
1
)
, where
a
,
b
a,b
a
,
b
are positive integers. Prove that if
X
X
X
is a set of challenging numbers smaller than
2
n
(
n
2^n (n
2
n
(
n
is a given positive integer) and
∣
X
∣
≥
4
3
(
n
−
1
)
|X|\ge \frac{4}{3}(n-1)
∣
X
∣
≥
3
4
(
n
−
1
)
, there exist two disjoint subsets
A
,
B
⊂
X
A,B\subset X
A
,
B
⊂
X
such that
∣
A
∣
=
∣
B
∣
|A|=|B|
∣
A
∣
=
∣
B
∣
and
∑
a
∈
A
a
=
∑
b
∈
B
b
\sum_{a\in A}a=\sum_{b \in B}b
∑
a
∈
A
a
=
∑
b
∈
B
b
.
combinatorics