Let $n\ge 2$ be an integer. A sequence $\alpha = (a_1, a_2,..., a_n)$ of $n$ integers is called Lima if $\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 $a_i - a_j$ with $a_i> a_j$ is $1$. One operation consists of choosing two elements $a_k$ and $a_{\ell}$ from a sequence, with $k\ne \ell $ , and replacing $a_{\ell}$ by $a'_{\ell} = 2a_k - a_{\ell}$ . Show that, given a collection of $2^n - 1$ Lima sequences, each one formed by $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)$ and $(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.
Problem
Source: 2020 IberoAmerican p3
Tags: combinatorics
18.11.2020 05:32
Almost trivially, Limality is preserved under operation. I claim every Lima sequence can always be formed from a single Lima sequence with elements only in $\{0, 1\}$ and no others (The sequence is "Lima-reduced"). If this claim is true, we are done by Pigeonhole. In particular, it is necessary for the Lima sequence, if it exists, to be the only corresponding Lima sequence due to parity preservation, so it remains to prove achievability. We denote the described operation as $\mathcal{Q}(l, k)$ We will prove achievability through monovariance. Assume there are more than two values in the sequence. Define a monovariant to be the sum of the absolute values of all elements in the sequence. This monovariant will decrease in all the below cases or cause the sequence to become Lima-reduced. Denote $U$ as the index of any element with the minimal value, and denote $V$ as the index of any element with the maximal value. Denote $X$ as the index of any element with the second most minimal value, and denote $Y$ as the index of any element with the second most maximal value. Abbreviate $Z$ as performing the operations $\mathcal{Q}(p, q)$, where $p$ is every element equal to $-1$ and $q$ is any element equal to $0$. If $|\{a_i | a_i <0\}|=1$, $|\{a_j | a_j >0\}|=1$, and $|\{k | a_k =0\}|\geq1$, then perform $\mathcal{Q}(i, k)$ for all such i and any k, the monovariant does not decrease, but this state cannot repeat twice in a row, so the monovariant decreases by the next iteration or the sequence becomes Lima-reduced. If $|\{a_i | a_i <0\}|=1$, $|\{a_j | a_j >0\}|=1$, and $|\{k | a_k =0\}|=0$, then the sequence was not Lima. If $|\{a_i | a_i <0\}|=0$, $|\{a_j | a_j >0\}|=1$, and $|\{k | a_k =0\}|\geq1$, then the sequence is Lima-reduced. If $|\{a_i | a_i <0\}|=0$, $|\{a_j | a_j >0\}|=1$, and $|\{k | a_k =0\}|=0$, then the sequence was not Lima. If $|\{a_i | a_i <0\}|=1$, $|\{a_j | a_j >0\}|=0$, and $|\{k | a_k =0\}|\geq1$, then the sequence is Lima-reduced after $Z$. If $|\{a_i | a_i <0\}|=1$, $|\{a_j | a_j >0\}|=0$, and $|\{k | a_k =0\}|=0$, then the sequence was not Lima. If $|\{a_i | a_i <0\}|=0$, $|\{a_j | a_j >0\}|=0$, and $|\{k | a_k =0\}|\geq1$, then the sequence was not Lima. If $|\{a_i | a_i <0\}|=0$, $|\{a_j | a_j >0\}|=0$, and $|\{k | a_k =0\}|=0$, then the sequence was not Lima. If $|\{a_i | a_i <0\}|\geq 2$, then perform $\mathcal{Q}(U, X)$. If $|\{a_j | a_j >0\}|\geq 2$, then perform $\mathcal{Q}(V, Y)$. Simple iterate the above operations until the sequence is Lima-reduced. Since the monovariant is finite, strictly decreases unless the sequence becomes Lima-reduced, but must be positive, eventually the sequence will become Lima-reduced under these operations.Thus, we are done.
28.01.2023 18:33
Very similar idea as Inconsistent. We first make several observations. Let $\alpha$ be a Lima sequence. Let $\alpha'$ be any sequence obtained by performing an operation on $\alpha$. If $p > 1$ divides all terms in $\alpha'$, then $p$ also divides all terms in $\alpha$. Hence, limacity is preserved under all operations. Next, note that operations do not change the parity of any term in a sequence. Hence, sequences different modulo $2$ are not equivalent under operations. Main Idea: If we can show that there are at most $2^n - 2$ equivalence classes under operations, we'd be done. Note that there are exactly $2^n - 2$ Lima sequences modulo $2$. We seek to prove that Lima sequences equivalent modulo $2$ are always equivalent. It suffices to prove that $\alpha$ and $\alpha \pmod 2$ are equivalent through a finite number of operations. We want to find a sequence of operations that strictly decreases a monovariant of $\alpha$. Let's define this monovariant. Denote the signature of $\alpha$ to be: \[\mathrm{sig}(\alpha) = \left\lvert a_1 - \frac{1}{2} \right\rvert + \left\lvert a_2 - \frac{1}{2} \right\rvert + \cdots + \left\lvert a_n - \frac{1}{2} \right\rvert.\]Let $U = \{a \in \alpha \mid a > 1\}$ and $V = \{a \in \alpha \mid a < 0\}$. The reduction process is as follows. If $\lvert U \rvert \geq 2$, flip the largest term in $U$ over the smallest term in $U$, decreasing the signature by at least $1$. Similarly, if $\lvert V \rvert$, flip the smallest term in $V$ over the largest term. Only the edge cases remain. Suppose no operation on $\alpha$ decreases its signature. Edge Case 0. If $\lvert V \rvert = 1$. Let $V = \{v\}$. If $0 \in \alpha$, flipping $v$ over $0$ decreases the signature of $\alpha$, impossible. Hence, $0 \notin \alpha$. Similarly, we cannot allow $1 \in \alpha$ and $\lvert U \rvert = 1$ simultaneously. If $1 \in \alpha$, the only difference is $1 - v \geq 2$. Hence, $\alpha$ is not Lima. If $\lvert U \rvert = 1$, let $u \in U$. The only difference is $u - v \geq 3$, and hence $\alpha$ is not Lima. Edge Case 1. If $\lvert U \rvert = 1$. The proof is analogous to Edge Case 0. After we run out of operations, the sequence has no terms greater than $1$ or less than $0$. Hence, this new sequence is $\alpha \pmod 2$. We are done.