Maths Olympiad Prep

Library / Auswahlklausur /30 of 31

Auswahlklausur

Number theory Difficulty 9.1 IMO level Prove it Germany

Problem:

Determine all integers n≥2n \geq 2 with the following property:
For arbitrary, not necessarily distinct integers m1,m2,…,mnm_{1}, m_{2}, \ldots, m_{n}, whose sum is not divisible by nn, there exists an index ii (1≤i≤n)(1 \leq i \leq n) such that none of the numbers
mi, mi+mi+1, mi+mi+1+mi+2, …, mi+mi+1+…+mi+n−1 m_{i},\ m_{i}+m_{i+1},\ m_{i}+m_{i+1}+m_{i+2},\ \ldots,\ m_{i}+m_{i+1}+\ldots+m_{i+n-1}
is divisible by nn. (Here let mi=mi−nm_{i}=m_{i-n} for i>ni>n.)

Solution

Solution:

The numbers sought are precisely the primes.

Partial proof 1: No non-prime number satisfies all the conditions.

Let n=a⋅bn=a \cdot b with 1<a,b<n1<a, b<n be a factorization of nn into two proper divisors. We choose mi=am_{i}=a for 1≤i<n1 \leq i<n as well as mn=0m_{n}=0. Then the sum m1+m2+…+mn=(n−1)am_{1}+m_{2}+\ldots+m_{n}=(n-1) a is obviously not divisible by nn, since neither factor is divisible by nn.
Now, for an arbitrary index ii, we choose the index j={b for 1≤i≤n−bb+1 for n−b<i≤nj=\left\{\begin{array}{ll}b & \text{ for } 1 \leq i \leq n-b \\ b+1 & \text{ for } n-b<i \leq n\end{array}\right. and obtain mi+mi+1+…+mi+j−1=a⋅b=n≡0 mod nm_{i}+m_{i+1}+\ldots+m_{i+j-1}=a \cdot b=n \equiv 0 \bmod n. With this counterexample the partial proof is complete.

Partial proof 2: Every prime satisfies all the conditions.

Now let nn be a prime. For a proof by contradiction we assume that for the numbers m1,m2,…,mnm_{1}, m_{2}, \ldots, m_{n}, whose sum is not divisible by nn, there exists for every index ii (1≤i≤n)(1 \leq i \leq n) a number jj (1≤j≤n)(1 \leq j \leq n) such that the sum mi+mi+1+…+mi+j−1m_{i}+m_{i+1}+\ldots+m_{i+j-1} is divisible by nn. Here we even have j≠nj \neq n, since the sum of all mim_{i} is not divisible by nn.
Now, for 0≤k≤n−10 \leq k \leq n-1, we construct a finite sequence of integers i0,i1,…,ini_{0}, i_{1}, \ldots, i_{n} with ik+1−ik≤n−1i_{k+1}-i_{k} \leq n-1 (1), by choosing mik+1+mik+2+…+mik+1≡0 mod nm_{i_{k}+1}+m_{i_{k}+2}+\ldots+m_{i_{k+1}} \equiv 0 \bmod n. The starting index i0i_{0} is arbitrary, and the new index ik+1i_{k+1} is chosen to be the smallest possible one after iki_{k} when proceeding cyclically  mod n\bmod n.
By the pigeonhole principle, among this sequence of n+1n+1 indices there exist two distinct numbers iri_{r} and isi_{s} with 0≤r<s≤n0 \leq r<s \leq n that are congruent  mod n\bmod n. For these we have ∑j=rs−1(mij+1+mij+2+…+mij+1)≡0 mod n\sum_{j=r}^{s-1}\left(m_{i_{j}+1}+m_{i_{j}+2}+\ldots+m_{i_{j+1}}\right) \equiv 0 \bmod n, since this holds for every bracketed sum.
On the other hand, from is≡ir mod ni_{s} \equiv i_{r} \bmod n it follows that there exists a positive integer dd with is−ir=d⋅ni_{s}-i_{r}=d \cdot n. By (1), is−ir≤(n−1)ni_{s}-i_{r} \leq(n-1) n, so it follows that d≤n−1d \leq n-1. Then ∑j=rs−1(mij+1+mij+2+…+mij+1)=d(m1+m2+…+mn)\sum_{j=r}^{s-1}\left(m_{i_{j}+1}+m_{i_{j}+2}+\ldots+m_{i_{j+1}}\right)=d\left(m_{1}+m_{2}+\ldots+m_{n}\right) cannot be a multiple of nn, since nn is prime and neither dd nor m1+m2+…+mnm_{1}+m_{2}+\ldots+m_{n} are multiples of nn — contradiction! □\square

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: MathNet, licensed CC-BY-4.0. Statement translated into English from de; metadata (topic, difficulty) added by this project.