MathDB
Problems
Contests
National and Regional Contests
Hungary Contests
Kürschák Math Competition
2016 Kurschak Competition
2
2
Part of
2016 Kurschak Competition
Problems
(1)
Two-colored transitive digraph has independent cover
Source: Kürschák 2016, problem 2
10/7/2016
Prove that for any finite set
A
A
A
of positive integers, there exists a subset
B
B
B
of
A
A
A
satisfying the following conditions: [*]if
b
1
,
b
2
∈
B
b_1,b_2\in B
b
1
,
b
2
∈
B
are distinct, then neither
b
1
b_1
b
1
and
b
2
b_2
b
2
nor
b
1
+
1
b_1+1
b
1
+
1
and
b
2
+
1
b_2+1
b
2
+
1
are multiples of each other, and [*] for any
a
∈
A
a\in A
a
∈
A
, we can find a
b
∈
B
b\in B
b
∈
B
such that
a
a
a
divides
b
b
b
or
b
+
1
b+1
b
+
1
divides
a
+
1
a+1
a
+
1
.
combinatorics