Find all integer sequences $a_1 , a_2 , \ldots , a_{2024}$ such that $1\le a_i \le 2024$ for $1\le i\le 2024$ and $$i+j|ia_i-ja_j$$for each pair $1\le i,j \le 2024$.
Problem
Source: 2024 Korea Summer Program Practice Test Junior P2
Tags: number theory
12.08.2024 17:20
Only sol is $a_i = i$. This clearly works. Let $a_n = f(n)$, where $f$ is from $\{1,2,\ldots, 2024\}$ to itself. We have \[ m + n \mid m f(m) - n f(n) \]for any integers $1 \le m,n \le 2024$. Now $m + n \mid m f(m) - n f(n) + f(n) (m + n) = m f(m) + m f(n)$. Thus, if $\gcd(m,n) = 1$, we have that $m+n\mid f(m) + f(n)$. Setting $n = m + 1$ and $m \le 2023$ gives that $2m + 1 \mid f(m) + f(m+1)$ for any $m \le 2023$. Setting $m = 2023$ there gives that $4047 \mid f(2023) + f(2024)$. Since $f(2023) + f(2024) \le 4048$, we have $f(2023) + f(2024) = 4047$, so $\{f(2023), f(2024)\} = \{2023, 2024\}$. Case 1: $f(2023) = 2024$ and $f(2024) = f(2023)$ If $\gcd(m,2023) = 1$, then $m + 2023 \mid f(m) + 2024$. Setting $m = 5$ gives that $2028 \mid f(5) + 2024$. However, $f(5) + 2024 < 2 \cdot 2028$, so $f(5) + 2024 = 2028$ and $f(5) = 4$. Now if $\gcd(m,2024) = 1$, then $m + 2024 \mid f(m) + 2023$. Setting $m = 5$ gives that $2029 \mid 2023 + 4 = 2027$, absurd. Case 2: $f(2023) = 2023$ and $f(2024) = 2024$ If $\gcd(m,2023) = 1$, we have that $m + 2023 \mid f(m) + 2023$. However, $f(m) + 2023 \le 4047 < 2(m + 2023)$, so $f(m) + 2023 = m + 2023 \implies f(m) = m$. Hence $f(2017) = 2017$. Now we can also get that $1, 2, 3, 4, 5, 6$ are relatively prime to $2023$, so they are all fixed points. If $\gcd(m,2017) = 1$ (any $m \in \{1,2,\ldots, 2024\}$ not equal to $2017$), we have $m + 2017 \mid f(m) + 2017$. For $m \ge 7$, the RHS is less than $2(m + 2017)$, so it must be $m + 2017$, implying $f(m) = m$ and therefore $f$ is fixed.
12.08.2024 21:13
The only solution is $a_i=i$ for all $i$, $1\leq i\leq 2024$, which obviously works. For relatively prime $i$ and $j$ the assertion rewrites as $$i+j|ia_i-ja_j\iff i+j|i(a_i+a_j)\iff i+j|a_i+a_j$$Thus we have that $a_i+a_j\geq i+j$ for all relatively prime $i$ and $j$. Thus $a_{2k-1}+a_{2k}\geq 4k-1$ for all $k$, $1\leq k\leq 1012$. Summing all the inequalities gives that each must have been an equality so $a_{2k-1}+a_{2k}=4k-1$ and inducting from $k=1$ gives $\{a_{2k-1},a_{2k}\}=\{2k-1,2k\}$. If $a_1\neq 1$ testing both $(a_1,a_2,a_3,a_4)$ as $(2,1,3,4)$ and $(2,1,4,3)$ fail. So $a_1=1$. Thus for all $j$, $1\leq j\leq 2024$ we have that $1+j|1+a_j$ thus $j\leq a_j$ which implies the desired result.