MathDB
Lima sequances, gcd {a_i - a_j with a_i> a_j} =1, a'=2a_k-a_l

Source: 2020 IberoAmerican p3

November 17, 2020
combinatorics

Problem Statement

Let n≥2n\ge 2 be an integer. A sequence α=(a1,a2,...,an)\alpha = (a_1, a_2,..., a_n) of nn integers is called Lima if gcd⁡{ai−aj such that ai>aj 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, that is, if the greatest common divisor of all the differences ai−aja_i - a_j with ai>aja_i> a_j is 11. One operation consists of choosing two elements aka_k and aℓa_{\ell} from a sequence, with k≠ℓk\ne \ell , and replacing aℓa_{\ell} by aℓ′=2ak−aℓa'_{\ell} = 2a_k - a_{\ell} . Show that, given a collection of 2n−12^n - 1 Lima sequences, each one formed by nn 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) and (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.
Back to ProblemsView on AoPS