MathDB
Problems
Contests
National and Regional Contests
Hungary Contests
Kürschák Math Competition
2008 Kurschak Competition
2008 Kurschak Competition
Part of
Kürschák Math Competition
Subcontests
(3)
3
1
Hide problems
Superposition of two directed graphs
In a far-away country, travel between cities is only possible by bus or by train. One can travel by train or by bus between only certain cities, and there are not necessarily rides in both directions. We know that for any two cities
A
A
A
and
B
B
B
, one can reach
B
B
B
from
A
A
A
, or
A
A
A
from
B
B
B
using only bus, or only train rides. Prove that there exists a city such that any other city can be reached using only one type of vehicle (but different cities may be reached with different vehicles).
2
1
Hide problems
Differences equal to a power of 2
Let
n
≥
1
n\ge 1
n
≥
1
and
a
1
<
a
2
<
⋯
<
a
n
a_1<a_2<\dots<a_n
a
1
<
a
2
<
⋯
<
a
n
be integers. Let
S
S
S
be the set of pairs
1
≤
i
<
j
≤
n
1\le i<j\le n
1
≤
i
<
j
≤
n
for which
a
j
−
a
i
a_j-a_i
a
j
−
a
i
is a power of
2
2
2
, and
T
T
T
be the set of pairs
1
≤
i
<
j
≤
n
1\le i<j\le n
1
≤
i
<
j
≤
n
with
j
−
i
j-i
j
−
i
a power of
2
2
2
. (Here, the powers of
2
2
2
are
1
,
2
,
4
,
…
1,2,4,\dots
1
,
2
,
4
,
…
.) Prove that
∣
S
∣
≤
∣
T
∣
|S|\le |T|
∣
S
∣
≤
∣
T
∣
.
1
1
Hide problems
Upper bound on d(n)
Denote by
d
(
n
)
d(n)
d
(
n
)
the number of positive divisors of a positive integer
n
n
n
. Find the smallest constant
c
c
c
for which
d
(
n
)
≤
c
n
d(n)\le c\sqrt n
d
(
n
)
≤
c
n
holds for all positive integers
n
n
n
.