Find all sets of positive integers $\{x_1, x_2, \dots, x_{20}\}$ such that $$x_{i+2}^2=lcm(x_{i+1}, x_{i})+lcm(x_{i}, x_{i-1})$$for $i=1, 2, \dots, 20$ where $x_0=x_{20}, x_{21}=x_1, x_{22}=x_2$.
Problem
Source: All-Russian 2021/10.2
Tags: number theory
19.04.2021 21:51
Again, application of well-known techniques from lots of other competitions. Claim. For every $i$, $gcd(x_{i+1}, x_{i})\geq 2$. Obviously, there exists $i$ so that $x_i$ is divisible by prime $p$, since otherwise $x_i=1$ for all $i$, which does not satisfy the given. Because $x_{i+3}^2=lcm(x_{i+2}, x_{i+1})+lcm(x_{i+1}, x_{i})$ and $x_{i+2}^2=lcm(x_{i+1}, x_{i})+lcm(x_{i}, x_{i-1})\quad \diamondsuit$, thus $$(x_{i+3}-x_{i+2})(x_{i+3}+x_{i+2})=lcm(x_{i+2}, x_{i+1})-lcm(x_{i}, x_{i-1}).\quad \clubsuit$$As $p\mid x_i$, we get from $\diamondsuit$, $p\mid x_{i+2}$, now from $\clubsuit$, $p\mid x_{i+3}$, inducing all up, we have every $x_i$ divisible by $p$. Therefore, for every $i$, $gcd(x_{i+1}, x_{i})\geq 2$. We sum all the equations up and obtain that $$2\sum_{i=1}^{20} lcm(x_{i+1}, x_{i})=\sum_{i=1}^{20} x_{i}^2\geq \sum_{i=1}^{20}x_i x_{i+1},$$where equality holds if and only if $x_i=x_{i+1}$ for all $i$. Now we rewrite $lcm(x_{i+1}, x_{i})=\frac{x_i x_{i+1}}{gcd(x_{i+1}, x_{i})}$ and as $gcd(x_{i+1}, x_{i})\geq 2$, we conclude that the inequality must hold, therefore all integers are equal. Now, we must have $x_i^2=2x_i\implies x_i=2$. Answer. $\boxed{x_i=2\forall i\in\{1,2,\ldots,20\}}$.
25.04.2021 01:46
It is easy to see that both $x_1$ and $x_2$ cannot both be $1$. Therefore, let one of them be divisible by some prime $p,$ WLOG let it to be $x_2$. It is trivial to see that all the even indices are divisible by $p$. To prove that all the odd indices are divisible by $p,$ notice that for odd $k,$ $x_k^2=\text{lcm}(x_{k-1},x_{k-2})+\text{lcm}(x_{k-2}, x_{k-3}),$ and each of these lcm terms is divisible by $p$. Now notice that by AM-GM(repeated 20 times on consecutive terms) we get that $x_1^2+x_2^2+\cdots +x_{20}^2\geq x_1x_2+\cdots x_{20}x_1$. But adding up all the lcm expressions, we get that this expression is also equal to $2\cdot \sum \text{lcm}(x_k,x_{k+1})$. Notice that because they all share some factor of $p,$ each of the lcms must be less than or equal to $\frac{x_k x_{k+1}}{2},$ with equality holding iff the only prime that divides any number is $2$. Therefore, $2$ is the only factor of every number. This means that of the lcms must be a power of $2,$ and it is easy to see that the sum of two powers of $2$ can be a power of $2$ only if they are the same power of $2$. From here, it is trivial to see the only solution is for all $x_i$ such that $1\leq i\leq 20$ to be $2$.
30.03.2022 18:23
If $x_i=1$ for all $1\le i\le20$, we have a contradiction since the given equality implies $1=2$. So there is some prime $p$ and associated $1\le j\le20$ with $p\mid x_j$. Then $p\mid x_j+x_j$, so: $$p\mid\operatorname{lcm}(x_{j+1},x_j)+\operatorname{lcm}(x_j,x_{j-1})=x_{j+2}^2,$$which implies $p\mid x_{j+2}$. Then by induction $p\mid x_i$ for all $i$ with the same parity as $j$. Also, $p\mid x_{j+2}+x_j$ implies: $$p\mid\operatorname{lcm}(x_{j+2},x_{j+1})+\operatorname{lcm}(x_{j+1},x_j)=x_{j+3}^2,$$so $p\mid x_{j+3}$ and, similarly to before, $p\mid x_i$ for all $i$ with the opposite parity as $j$. Thus $p\mid x_i$ for all $1\le i\le20$. Summing the given equality for $1\le i\le20$ gives: $$\sum_{i=1}^{20}x_i^2=2\sum_{i=1}^{20}\operatorname{lcm}(x_{i+1},x_i).$$Now: $$\sum_{i=1}^{20}x_i^2\ge\sum_{i=1}^{20}x_ix_{i+1}$$by Rearrangement (equality iff $x_i$ is constant) and: $$2\sum_{i=1}^{20}\operatorname{lcm}(x_{i+1},x_i)=2\sum_{i=1}^{20}\frac{x_ix_{i+1}}{\gcd(x_i,x_{i+1})}\le2\sum_{i=1}^{20}\frac{x_ix_{i+1}}p\le2\sum_{i=1}^{20}\frac{x_ix_{i+1}}2=\sum_{i=1}^{20}x_ix_{i+1},$$so: $$\sum_{i=1}^{20}x_ix_{i+1}\le\sum_{i=1}^{20}x_i^2=2\sum_{i=1}^{20}\operatorname{lcm}(x_{i+1},x_i)\le\sum_{i=1}^{20}x_ix_{i+1},$$which is equality. Therefore $x_i=c$ for all $1\le i\le20$ where $c$ is a constant, and we see that $c^2=2c$, so $c=2$. Then the only such set is $\{2\}$.
28.05.2022 10:45
Cute. Let $p$ be any prime dividing $x_1$ (of course all the numbers are $>1$) and because for integers, $a,b \mid \mathrm{lcm}(a,b)$, we have $$p \mid x_1 \mid \mathrm{lcm}(x_1,x_0) + \mathrm{lcm}(x_1,x_2) \mid x_3^2 \implies p \mid x_3$$and $$p \mid x_1,x_3 \mid \mathrm{lcm}(x_2,x_3) + \mathrm{lcm}(x_2,x_1) = x_4^2 \implies p \mid x_4$$and iterating we have $p\mid x_i$ for all $i$. If one number is even then all the numbers are even, if all are odd then the sum of their lcm's are even which is a contradiction which concludes that all the numbers are even. Write $x_i = 2y_i$, we have $$y_i^2 = \dfrac{\mathrm{lcm}(y_{i-2},y_{i-1}) + \mathrm{lcm}(y_{i-2},y_{i-3})}{2} \le \dfrac{y_{i-2}(y_{y-1} + y_{i-3})}{2}$$which after summing yields $\sum y_i^2 \le \sum y_iy_{i+1}$ but applying AM-GM 20 times on the pairs $(y_i , y_{i+1})$ and summing we have the reverse inequality, concluding that all the numbers are equal (this step is also true by the Rearrangement Inequality) and it is easy to see $x_i=2$ works for all $i$.