MathDB
Problems
Contests
National and Regional Contests
Romania Contests
Romania Team Selection Test
2014 Romania Team Selection Test
2014 Romania Team Selection Test
Part of
Romania Team Selection Test
Subcontests
(5)
5
1
Hide problems
Sets and subsets!
Let
n
n
n
be an integer greater than
1
1
1
and let
S
S
S
be a finite set containing more than
n
+
1
n+1
n
+
1
elements.Consider the collection of all sets
A
A
A
of subsets of
S
S
S
satisfying the following two conditions : (a) Each member of
A
A
A
contains at least
n
n
n
elements of
S
S
S
. (b) Each element of
S
S
S
is contained in at least
n
n
n
members of
A
A
A
.Determine
max
A
min
B
∣
B
∣
\max_A \min_B |B|
max
A
min
B
∣
B
∣
, as
B
B
B
runs through all subsets of
A
A
A
whose members cover
S
S
S
, and
A
A
A
runs through the above collection.
3
5
Show problems
1
5
Show problems
2
5
Show problems
4
3
Hide problems
Number of divisors of a sum of powers
Let
k
k
k
be a nonzero natural number and
m
m
m
an odd natural number . Prove that there exist a natural number
n
n
n
such that the number
m
n
+
n
m
m^n+n^m
m
n
+
n
m
has at least
k
k
k
distinct prime factors.
Nice function
Let
f
f
f
be the function of the set of positive integers into itself, defi ned by
f
(
1
)
=
1
f(1) = 1
f
(
1
)
=
1
,
f
(
2
n
)
=
f
(
n
)
f(2n) = f(n)
f
(
2
n
)
=
f
(
n
)
and
f
(
2
n
+
1
)
=
f
(
n
)
+
f
(
n
+
1
)
f(2n + 1) = f(n) + f(n + 1)
f
(
2
n
+
1
)
=
f
(
n
)
+
f
(
n
+
1
)
. Show that, for any positive integer
n
n
n
, the number of positive odd integers m such that
f
(
m
)
=
n
f(m) = n
f
(
m
)
=
n
is equal to the number of positive integers[color=#0000FF] less or equal to
n
n
n
and coprime to
n
n
n
.[color=#FF0000][mod: the initial statement said less than
n
n
n
, which is wrong.]
Subsets and gcd
Let
n
n
n
be a positive integer and let
A
n
A_n
A
n
respectively
B
n
B_n
B
n
be the set of nonnegative integers
k
<
n
k<n
k
<
n
such that the number of distinct prime factors of
gcd
(
n
,
k
)
\gcd(n,k)
g
cd
(
n
,
k
)
is even (respectively odd). Show that
∣
A
n
∣
=
∣
B
n
∣
|A_n|=|B_n|
∣
A
n
∣
=
∣
B
n
∣
if
n
n
n
is even and
∣
A
n
∣
>
∣
B
n
∣
|A_n|>|B_n|
∣
A
n
∣
>
∣
B
n
∣
if
n
n
n
is odd.Example:
A
10
=
{
0
,
1
,
3
,
7
,
9
}
A_{10} = \left\{ 0,1,3,7,9 \right\}
A
10
=
{
0
,
1
,
3
,
7
,
9
}
,
B
10
=
{
2
,
4
,
5
,
6
,
8
}
B_{10} = \left\{ 2,4,5,6,8 \right\}
B
10
=
{
2
,
4
,
5
,
6
,
8
}
.