Find all integer sequences a1,a2,…,a2024 such that 1≤ai≤2024 for 1≤i≤2024 and i+j|iai−jajfor each pair 1≤i,j≤2024.
Problem
Source: 2024 Korea Summer Program Practice Test Junior P2
Tags: number theory
12.08.2024 17:20
Only sol is ai=i. This clearly works. Let an=f(n), where f is from {1,2,…,2024} to itself. We have m+n∣mf(m)−nf(n)for any integers 1≤m,n≤2024. Now m+n∣mf(m)−nf(n)+f(n)(m+n)=mf(m)+mf(n). Thus, if gcd, 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_jThus 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.