Let $n>1$ be a positive integer. Call a rearrangement $a_1,a_2, \cdots , a_n$ of $1,2, \cdots , n$ nice if for every $k = 2 ,3, \cdots , n$, we have that $a_1^2 + a_2^2 + \cdots + a_k^2$ is not divisible by $k$. Determine which positive integers $n>1$ have a nice arrangement.
Problem
Source: RMO KV 2024 Q4
Tags: number theory
03.11.2024 16:04
even $n$ work, the same proof as the rmo 2024 p1. https://artofproblemsolving.com/community/c6h3434792_rmo_2024_q1 the arrangement is $(2,1,4,3,\cdots ,n,n-1)$
05.11.2024 17:03
Note that the given condition for $k = n$ implies that the sum $a_1^2+a_2^2+\ldots+a_n^2$ is not divisible by $n$. However, $a_1, a_2, \ldots, a_n$ is a rearrangement of $1,2, \ldots,n$ so their sum is equal to $1^2 + 2^2 + \ldots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$ which is divisible by $n$ for any $n$ which is $1 \bmod 6$ or $5 \bmod 6$. Thus, there cannot be any nice rearrangement of $1,2, \ldots, n$ for $n \equiv 1,5 \bmod 6$. Now, we consider the sequence $$2,1,3,4,6,5,8,7,9,10,12,11,13 \ldots \text{ i.e. } a_n = \left\{ \begin{array}{cc} n+1 & n \equiv 1,5 \bmod 6\\ n-1 & n \equiv 0,2 \bmod 6\\ n & n \equiv 3,4 \bmod 6\\ \end{array} \right. $$We claim that $a_1, a_2, \ldots, a_n$ is a nice rearrangement of $1,2, \ldots, n$ for $n \not \equiv 1,5 \bmod 6$. So let $n \not \equiv 1,5 \bmod 6$. First, we note that it is indeed a rearrangement of $1,2, \ldots, n$ for these $n$. $\bullet$ For $k \not \equiv 1,5 \bmod 6$, we have $a_1^2 + a_2^2 + \ldots + a_k^2 = \dfrac{k(k+1)(2k+1)}{6}$ which is not divisible by $k$ since $(k+1)(2k+1)/6$ is not an integer. $\bullet$ For $k \equiv 1,5 \bmod 6$, we have $a_1^2 + a_2^2 + \ldots + a_k^2 = \dfrac{k(k+1)(2k+1)}{6} + (k+1)^2 - k^2$ which is $1$ more than a multiple of $k$, so it is again not divisible by $k$ for $k > 1$. $\blacksquare$