Maths Olympiad Prep

Library / Middle European Mathematical Olympiad /7 of 26

Middle European Mathematical Olympiad

Number theory Difficulty 6.3 National Olympiad Find the answer

Determine all integers n≥2n \geq 2 such that there exists a permutation x0,x1,…,xn−1x_0, x_1, \ldots, x_{n - 1} of the numbers 0,1,…,n−10, 1, \ldots, n - 1 with the property that the nn numbers
x0,x0+x1,…,x0+x1+…+xn−1x_0, \hspace{0.3cm} x_0 + x_1, \hspace{0.3cm} \ldots, \hspace{0.3cm} x_0 + x_1 + \ldots + x_{n - 1}
are pairwise distinct modulo nn.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Given the problem, we are tasked with finding all integers n≥2 n \geq 2 such that there exists a permutation x0,x1,…,xn−1 x_0, x_1, \ldots, x_{n-1} of the numbers 0,1,…,n−1 0, 1, \ldots, n-1 with the property that the n n numbers

x0,x0+x1,…,x0+x1+…+xn−1 x_0, \quad x_0 + x_1, \quad \ldots, \quad x_0 + x_1 + \ldots + x_{n-1}

are pairwise distinct modulo n n .

To solve this, consider the sequence Sk=x0+x1+…+xk S_k = x_0 + x_1 + \ldots + x_k for 0≤k<n 0 \leq k < n . We need S0,S1,…,Sn−1 S_0, S_1, \ldots, S_{n-1} to be distinct modulo n n .

### Step 1: Permutation and Constraints

Since x0,x1,…,xn−1 x_0, x_1, \ldots, x_{n-1} is a permutation of 0,1,…,n−1 0, 1, \ldots, n-1 , we have:

x0+x1+…+xn−1≡0+1+…+(n−1)≡n(n−1)2(modn) x_0 + x_1 + \ldots + x_{n-1} \equiv 0 + 1 + \ldots + (n-1) \equiv \frac{n(n-1)}{2} \pmod{n}

This reduces to:

x0+x1+…+xn−1≡0(modn) x_0 + x_1 + \ldots + x_{n-1} \equiv 0 \pmod{n}

Thus, Sn−1≡0(modn) S_{n-1} \equiv 0 \pmod{n} .

### Step 2: Distinctness Condition

For S0,S1,…,Sn−1 S_0, S_1, \ldots, S_{n-1} to be pairwise distinct modulo n n , we need:

Sk1≢Sk2(modn)for0≤k1<k2<n S_{k_1} \not\equiv S_{k_2} \pmod{n} \quad \text{for} \quad 0 \leq k_1 < k_2 < n

### Step 3: Consider Special Cases

- **Case n=2 n = 2 :** The permutation (0,1) (0, 1) works because:

S0=0,S1=0+1=1 S_0 = 0, \quad S_1 = 0 + 1 = 1

Both are distinct modulo 2.

- **Even n≥2 n \geq 2 :** Consider the permutation that results in distinct cumulative sums. By constructing carefully, we can ensure the sums are distinct modulo n n .

- **Odd n n :** If n n is odd, consider:

Sk≡Sk′(modn)for some k<k′ since n∣n(n−1)2 S_k \equiv S_{k'} \pmod{n} \quad \text{for some } k < k' \text{ since } n \mid \frac{n(n-1)}{2}

Since n(n−1)2 \frac{n(n-1)}{2} is an integer and n n odd, this leads to a contradiction of the distinct condition.

### Conclusion

Thus, the integer n n must be even for the condition to hold. Therefore, the solution is:

even integers n≥2 \boxed{\text{even integers } n \geq 2}

This concludes that all even integers greater than or equal to 2 satisfy the given property in the problem.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.