Integers a1,a2,…an are different at mod n. If a1,a2−a1,a3−a2,…an−an−1 are also different at mod n, we call the ordered n-tuple (a1,a2,…an) 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 a1=0.
For n is even, take a2i=n−i and a2i−1=i−1 for i=1,2,⋯,n2.
a1,a2−a1,a3−a2,…,an−an−1 are different at 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).