$200$ natural numbers are written in a row. For any two adjacent numbers of the row, the right one is either $9$ times greater than the left one, $2$ times smaller than the left one. Can the sum of all these 200 numbers be equal to $24^{2022}$?
Problem
Source: All-Russian 2022 9.3
Tags: number theory
20.04.2022 17:44
For any consecutive numbers $a_i$ and $a_{i+1}$ we have that $a_i \equiv 2a_{i+1} \pmod{17}$. This would imply $a_{200}(2^{200}-1) = a_{200}(2^0+2^1+\ldots+2^{199}) \equiv 24^{2022} \pmod{17}$, which is impossible because the expression in brackets is divisible by $17$.
21.06.2022 11:50
why mod 17 specifically?? any motivation? thanks everyone
21.06.2022 12:47
PRMOisTheHardestExam wrote: why mod 17 specifically?? any motivation? Consider both cases: $a_{i+1} = 9a_{i}$ or $2a_{i+1} = a_{i}$. In first case we have: $2a_{i+1} = 18a_{i}$ which means $2a_{i+1} \equiv a_{i} (mod17)$ which is same as second case . So with this saying, both cases implicates same thing.
01.10.2023 17:40
Answer is no. Notice that $a_i \equiv 2a_{i+1} \pmod {17}$, as a result $a_{200}(2^{200} - 1) \equiv 24^{2022} \pmod {17}$. But $2^{200} - 1$ is divisible by 17, contradiction.
08.02.2024 13:55
The answer is no. Let the numbers be, from left to right, $a_1, a_2, \dots, a_{100}$. Thus we have, for any integer $1 \leq i \leq 99$, that $a_{i + 1} \in \{9a_i, a_i / 2\}$. Note that $a_{i + 1} \bmod{17}$ is the same no matter if we choose it to be $9a_1$ or $a_1 / 2$. Therefore we have \begin{align*} a_1 + a_2 + \dots + a_{200} &\equiv a_1 (1 + 9 + 9^2 + \dots + 9^{199}) \pmod{17} \\ &\equiv a_1 (9^{200} - 1) (9 - 1)^{-1} \\ &\equiv a_1 (9^8 - 1) (15) \\ &\equiv 0\text{.} \end{align*} But $24^{2022} \not\equiv 0 \pmod{17}$, a contradiction.
11.06.2024 04:51
The answer is no. Let the rightmost integer be $a$. Then the sum of the numbers is equivalent to $a + 2a + 2^2a + \dots 2^{99}a \equiv (2^{100} - 1)a \pmod{17}$, but $17 \mid 2^{100} - 1$ so the sum is divisible by $17$, contradiction as $17 \nmid 24^{2022}$.
15.06.2024 22:14
Note that $x_i+9x_i \equiv x_i+\frac{1}{2}x_i \mod{n} \implies 20 \equiv 3 \mod{n} \implies n=17$. That means the sum of all $x_i$ is invariant under mod 17 no matter how the numbers are decided, so we can take $x_{200}+2x_{200}+\cdots+2^{199}x_{200} \equiv x_{200}(2^{200}-1) \equiv 0 \mod{17}$ but $24^{2022} \equiv 9 \mod{17}$ so it is impossible.
06.11.2024 13:15
Oh wow the solutions in the thread are actually so clean, mine’s a lot worse Notice that using the fact that we have each of the numbers $(a_i)_{i=1}^{200}$ being a natural number, they can be factorised as $a_i=\prod_{j=1}^{n}p_j^{e_j^a}$, however since the only prime numbers whose exponents change are exactly $2$ and $3$, $a_i=2^{b_i}3^{c_i}$ for all $i=1,2,\dots,200$. Let $a=a_1$, $b=b_1$. Now consider the number of times $t$ we multiplied by $9$; we must then divide by $2$ $199-t$ times. Hence we have then the product $P$ is then $2^{200a}3^{200b}\left(\frac{3^2}{2}\right)^{t}2^{199}=2^{6066}3^{2022}$. Hence we must have the following hold: \begin{align*} 200a-t&=5867=6000-133\\ 200b+2t&=2022 \end{align*}This reduces down to: \begin{align*} a&=30+\frac{t-133}{200}\\ b&=10-\frac{t-11}{100} \end{align*}hence $t\equiv11\pmod{100}$ and $t\equiv133\pmod{200}$, however this implies $133\equiv11\pmod{100}$, a clear contradiction.
24.11.2024 06:44
The answer is no. Take $\pmod {17}$. This would give $$a_n = 2a_{n+1}\pmod {17}$$always. The sum of all the numbers is therefore $$a_{200}(1+2+\dots+2^{199}) = a_{200}(2^{200}-1),$$which is a multiple of $17$, while $24^{2022}$ is not, done.