Integers $a_1, a_2, \dots a_n$ are different at $\text{mod n}$. If $a_1, a_2-a_1, a_3-a_2, \dots a_n-a_{n-1}$ are also different at $\text{mod n}$, we call the ordered $n$-tuple $(a_1, a_2, \dots a_n)$ lucky. For which positive integers $n$, one can find a lucky $n$-tuple?
Problem
Source: 2021 Turkey JBMO TST P6
Tags: number theory, modular arithmetic, number theory proposed
BarisKoyuncu
24.05.2021 10:12
$n=1$ or $n$ is even
For $n=1$, take $a_1=0$.
For $n$ is even, take $a_{2i}=n-i$ and $a_{2i-1}=i-1$ for $i=1,2,\cdots ,\dfrac n2$.
$a_1, a_2-a_1, a_3-a_2, \dots ,a_n-a_{n-1}$ are different at $\text{mod n}$. Thus, $\{a_1, a_2-a_1, a_3-a_2, \dots ,a_n-a_{n-1}\}\equiv \{0,1,\cdots ,n-1\} \pmod{n}$.
We know that $a_i\not \equiv a_j\pmod{n}$ for $i\neq j$. Hence; $a_2-a_1, a_3-a_2, \dots ,a_n-a_{n-1}\not \equiv 0 \pmod{n}$. So, $a_1\equiv 0 \pmod{n}$.
$a_1+(a_2-a_1)+(a_3-a_2)+ \dots +(a_n-a_{n-1})\equiv 0+1+\cdots +(n-1)\equiv \dfrac{(n-1)n}{2}\equiv 0 \pmod{n}$. Hence, $a_n\equiv 0 \pmod{n}$.
We have $a_1\equiv a_n\equiv 0 \pmod{n}$. Contradiction.
hakN
24.05.2021 10:37
$n=1$ clearly works. If $n$ is odd and $n\geq 3$, then summing up gives $a_n \equiv 0 \mod n$ but that is impossible as $a_1 \equiv 0 \mod n$. For $n$ even, let $n=2k$, it is easy to prove that this construction works: $(0 , 1 , 2k - 1 , 2 , 2k - 2 , 3 , 2k - 3 , 4 , 2k - 4 , \dots , k - 1 , k + 1 , k)$.