Is it possible to arrange 1400 positive integer ( not necessarily distinct ) ,at least one of them being 2021 , around a circle such that any number on this circle equals to the sum of gcd of the two previous numbers and two next numbers? for example , if $a,b,c,d,e$ are five consecutive numbers on this circle , $c=\gcd(a,b)+\gcd(d,e)$
Problem
Source: 2021 Iran second round mathematical Olympiad P6
Tags: number theory, combinatorics, greatest common divisor
16.05.2021 15:18
The answer is no. The main idea lies in the following claim. Claim. Suppose $x_1, x_2, ..., x_n$ is one such arrangement (not necessarily containing $2021$) and $\gcd(x_1, x_2, ..., x_n) = 1$. Then, $2 \leq x_i \leq 5$ for all $i$. Proof: Assume WLOG that $x_1$ has the largest value among these numbers. Clearly $x_i \geq 2$ by definition, so it suffices to prove that $x_1 \leq 5$. Since $\gcd(x_{n-1}, x_n) + \gcd(x_2, x_3) = x_1$, one of the terms must be $\geq x_1/2$, so assume $\gcd(x_2, x_3) \geq x_1/2$. Furthermore, notice that if $d \mid x_i, x_{i+1}, x_{i+2}$, then $d \mid x_{i+2} - \gcd(x_i, x_{i+1}) = \gcd(x_{i+3}, x_{i+4}) \implies d \mid x_{i+4}, x_{i+5}$ (here the indices are taken modulo $n$). Thus, by a simple induction, $\gcd(x_1, x_2, x_3)$ divides all the numbers on the circle. This implies $\gcd(x_1, x_2, x_3) = 1$ If $\gcd(x_2, x_3) = x_1/2$, then $\gcd(x_1, x_1/2) = 1 \implies x_1 = 2$, done. If not, then $\gcd(x_2, x_3) > x_1/2$, which implies $x_2 = x_3$ (otherwise one of them is $\geq 2\gcd(x_2, x_3) > x_1$). Now, $\gcd(x_4, x_5) = x_3 - \gcd(x_1, x_2) = x_3 - 1$, and similarly $x_4 = x_5 = x_3 - 1$ if $x_3 > x_1/2 + 1$. However if $x_4 = x_3 - 1$ then $x_3 = \gcd(x_2, x_3) < \gcd(x_2, x_3) + \gcd(x_5, x_6) = x_4$, contradiction, so $x_1/2 < x_3 \leq x_1/2 + 1$. If $x_1 = 2k$ for some $k \in \mathbb{Z^+}$, then $x_2 = x_3 = k+1$ and $\gcd(x_4, x_5) = k$, so $x_4 = 2k$ (since $x_4 \leq x_1$ and $x_4 \neq x_3 - 1$) and $x_5 = k$. Then, notice that $\gcd(x_5, x_6) = x_4 - \gcd(x_2, x_3) = k-1$, so $k - 1 \mid k \implies k = 2 \implies x_1 = 4$, done. Similarly, if $x_1 = 2k + 1$, then $x_2 = x_3 = k+1$ and $x_4 = 2k$ or $3k$. If $x_4 = 3k$ then $3k \leq 2k + 1 \implies k = 1 \implies x_1 = 3$, while if $x_4 = 2k$ then proceed as before and we get $x_1 = 5$. Thus, the claim is proven. $\blacksquare$ Now the rest is clear. Assume on the contrary that there exists such an arrangement. By dividing each number by the GCD of all of them, we obtain an arrangement whose GCD is $1$. Thus, by the claim, every number is between $2$ and $5$ inclusive. However, this means that every number in the original arrangement has a prime factor $2, 3$ or $5$, contradicting the fact that $2021$ has none.
12.02.2022 13:43
My solution The answer is not. Suppose the contrary Let $a_1,a_2,a_3, \ldots , a_{1399}, a_{1400}$ be all the numbers on the circle in the that order. Suppose that $a_{1400}=2021=43 \cdot 47$ CLAIM 1: If there exists an index $i$ such that $gcd(a_i,a_{i+1},a_{i+2}) > 1$, which means there exists a prime $p$ such that $p \mid a_i,a_{i+1},a_{i+2}$, then $p \mid a_i$ $\forall i=1,2,3, \ldots, 1400$ so $p \in \{ 43,47 \}$ We can prove this easily from the conditions of all the numbers on the table that any number on this circle equals to the sum of gcd of the two previous numbers and two next numbers Hence from CLAIM 1, we observe for any $1400$ numbers including $2021$, we can always change these number into $b_1,b_2,b_3, \ldots , b_{1399}, b_{1400}$ such that any $3$ consecutive numbers have $gcd=1$ by divding each number by the common divisors of all the numbers, but not losing the original conditions. Also note that we can't have $2021=gcd(a_1,a_2,a_3, \ldots , a_{1400})$, since then by dividing each number by $2021$, we get a new sequence including number $1$, which gives a contradiction since $1$ can't be the sum of any $2$ positive integer Now suppose that $c= max (b_1,b_2,b_3, \ldots , b_{1400})$, then by the above claim, we have $c \ge 43$. Let $5$ consecutive numbers with $c$ in the middle be $a,b,c,d,e$ in that order CLAIM 2: At least $1$ of $2$ pairs $(a,b),(c,d)$ has $2$ equal numbers Proof Suppose the contrary, that $a \ne b$ and $c \ne d$. Then we have $$ c=(a,b)+(d,e) \le \frac{max(a,b)}{2} + \frac{max(d,e)}{2} \le \frac{c}{2} + \frac{c}{2} =c $$Then the equality holds, means $$ max(a,b)=max(d,e)=c \text{ and } min(a,b)=min(d,e)= gcd(a,b)=gcd(d,e)= \frac{c}{2}$$But this will definitely lead to our contradiction due to the new definition of the sequence $b_n$ ( Since there exists $3$ consecutive numbers with $gcd \ge \frac{c}{2}$) Hence we have at least $1$ of $2$ pairs $(a,b),(c,d)$ has $2$ equal numbers Now suppose that $a=b$ Let $7$ consecutive numbers be $y,x,a,b,c,d,e$ in that order Now from the the definition of the sequence $b_n$, we have $gcd(a,a,c)=gcd(a,c)=1$ and $gcd( a,a,x)=gcd(a,x)=1$. Then we have \[\begin{array}{*{20}{l}} {a = (a,c) + (x,y) = 1 + (x,y) \implies (x,y) = a - 1}\\ {}\\ {\begin{array}{*{20}{l}} {a = (a,x) + (c,d) = 1 + (c,d) \implies (c,d) = a - 1}\\ {}\\ {c = (a,a) + (d,e) = a + (d,e) \implies (d,e) = c - a} \end{array}} \end{array}\]Then $c-a \mid d$ and $a-1 \mid d$. Suppose that we have this system of inequality holds \[\left\{ \begin{array}{l} c - a \le \frac{d}{2} \text{ (1)}\\ a - 1 \le \frac{d}{2} \text{ (2)} \end{array} \right.\]Then $(1)+(2)$ implies that $c \le d+1$, but since $c$ is the maximum value among the $b_n$, we have $d=c$ or $d=c-1$ If $d=c$ then since $gcd(c,d)=a-1=(c,c)=c$, we have $a=c+1$ which contradicts to the maximum of $c$ If $d=c-1$ then since $gcd(c,d)=a-1=(c,c-1)=1$, we have $a=2$. Also from $gcd(d,e)=c-a=c-2=(c-1,e)$, we have $c-2 \mid c-1$ (A contradiction) Thus the system of inequality can't hold, which means at least one of the two (1),(2) is wrong. If (1) is wrong, means $c-a=d$, but since $a-1=gcd(c,d) \mid c-d =a $, we have a contradiction here If (2) is wrong, means $a-1=d$, then from $d=a-1=gcd(c,d)=(c,a-1)$, we have $a-1 \mid c$. But since $(1)$ is true, we have $$ c-a \le \frac{d}{2} \Leftrightarrow c \le a+ \frac{d}{2} = \frac{3d}{2}+1$$Also from $d \mid c$, we have $c=d=a-1$ means $c<a$, a contradiction Thus we can't have an arrangement for $1400$ positive integers around the circle, complete the proof!!!