MathDB
Problems
Contests
International Contests
IberoAmerican
2020 IberoAmerican
3
3
Part of
2020 IberoAmerican
Problems
(1)
Lima sequances, gcd {a_i - a_j with a_i> a_j} =1, a'=2a_k-a_l
Source: 2020 IberoAmerican p3
11/17/2020
Let
n
≥
2
n\ge 2
n
≥
2
be an integer. A sequence
α
=
(
a
1
,
a
2
,
.
.
.
,
a
n
)
\alpha = (a_1, a_2,..., a_n)
α
=
(
a
1
,
a
2
,
...
,
a
n
)
of
n
n
n
integers is called Lima if
gcd
{
a
i
−
a
j
such that
a
i
>
a
j
and
1
≤
i
,
j
≤
n
}
=
1
\gcd \{a_i - a_j \text{ such that } a_i> a_j \text{ and } 1\le i, j\le n\} = 1
g
cd
{
a
i
−
a
j
such that
a
i
>
a
j
and
1
≤
i
,
j
≤
n
}
=
1
, that is, if the greatest common divisor of all the differences
a
i
−
a
j
a_i - a_j
a
i
−
a
j
with
a
i
>
a
j
a_i> a_j
a
i
>
a
j
is
1
1
1
. One operation consists of choosing two elements
a
k
a_k
a
k
and
a
ℓ
a_{\ell}
a
ℓ
from a sequence, with
k
≠
ℓ
k\ne \ell
k
=
ℓ
, and replacing
a
ℓ
a_{\ell}
a
ℓ
by
a
ℓ
′
=
2
a
k
−
a
ℓ
a'_{\ell} = 2a_k - a_{\ell}
a
ℓ
′
=
2
a
k
−
a
ℓ
. Show that, given a collection of
2
n
−
1
2^n - 1
2
n
−
1
Lima sequences, each one formed by
n
n
n
integers, there are two of them, say
β
\beta
β
and
γ
\gamma
γ
, such that it is possible to transform
β
\beta
β
into
γ
\gamma
γ
through a finite number of operations.Notes. The sequences
(
1
,
2
,
2
,
7
)
(1,2,2,7)
(
1
,
2
,
2
,
7
)
and
(
2
,
7
,
2
,
1
)
(2,7,2,1)
(
2
,
7
,
2
,
1
)
have the same elements but are different. If all the elements of a sequence are equal, then that sequence is not Lima.
combinatorics