Maths Olympiad Prep

Library / /6 of 20

Number theory Difficulty 6.3 National olympiad Find the answer

Determine all integers n2n \geq 2 such that there exists a permutation x0,x1,,xn1x_0, x_1, \ldots, x_{n - 1} of the numbers 0,1,,n10, 1, \ldots, n - 1 with the property that the nn numbers
x0,x0+x1,,x0+x1++xn1x_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. Spacing and $ signs are ignored.

Solution

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

x0,x0+x1,,x0+x1++xn1 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 0k<n 0 \leq k < n . We need S0,S1,,Sn1 S_0, S_1, \ldots, S_{n-1} to be distinct modulo n n .

### Step 1: Permutation and Constraints

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

x0+x1++xn10+1++(n1)n(n1)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++xn10(modn) x_0 + x_1 + \ldots + x_{n-1} \equiv 0 \pmod{n}

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

### Step 2: Distinctness Condition

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

Sk1≢Sk2(modn)for0k1<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 n2 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:

SkSk(modn)for some k<k since nn(n1)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(n1)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 n2 \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.