MathDB
Problems
Contests
National and Regional Contests
Brazil Contests
Brazil Team Selection Test
2014 Brazil Team Selection Test
2014 Brazil Team Selection Test
Part of
Brazil Team Selection Test
Subcontests
(1)
1
2
Hide problems
gcd (5^m + 7^m, 5^n + 7^n) for m,n coprime
For
m
m
m
and
n
n
n
positive integers that are prime to each other, determine the possible values of
gcd
(
5
m
+
7
m
,
5
n
+
7
n
)
\gcd (5^m + 7^m, 5^n + 7^n)
g
cd
(
5
m
+
7
m
,
5
n
+
7
n
)
sum of partitions with repeated elements is 2^{n-1}
Let
n
n
n
be a positive integer. A partition of
n
n
n
is a multiset (set with repeated elements) whose sum of elements is
n
n
n
. For example, the partitions of
3
3
3
are
{
1
,
1
,
1
}
,
{
1
,
2
}
\{1, 1, 1\}, \{1, 2\}
{
1
,
1
,
1
}
,
{
1
,
2
}
and
{
3
}
\{3\}
{
3
}
. Each partition of
n
n
n
is written as a non-descending sequence. For example, for
n
=
3
n = 3
n
=
3
, the list is
(
1
,
1
,
1
)
(1, 1, 1)
(
1
,
1
,
1
)
,
(
1
,
2
)
(1, 2)
(
1
,
2
)
and
(
3
)
(3)
(
3
)
. For each sequence
x
=
(
x
1
,
x
2
,
.
.
.
,
x
k
)
x = (x_1, x_2, ..., x_k)
x
=
(
x
1
,
x
2
,
...
,
x
k
)
, define
f
(
x
)
=
∏
i
=
1
k
−
1
(
x
i
+
1
x
i
)
f(x)=\prod_{i=1}^{k-1} {x_{i+1} \choose x_ i}
f
(
x
)
=
∏
i
=
1
k
−
1
(
x
i
x
i
+
1
)
. Furthermore, the
f
f
f
of partition
{
n
}
\{n\}
{
n
}
is
f
(
(
n
)
)
=
1
f((n)) = 1
f
((
n
))
=
1
. Prove that the sum of all
f
f
f
's in the list is
2
n
−
1
.
2^{n-1}.
2
n
−
1
.