Maths Olympiad Prep

Library / /30 of 31

Number theory Difficulty 9.1 IMO level Prove it Germany

Problem:

Determine all integers n2n \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 (1in)(1 \leq i \leq n) such that none of the numbers
mi, mi+mi+1, mi+mi+1+mi+2, , mi+mi+1++mi+n1 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=minm_{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=abn=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 1i<n1 \leq i<n as well as mn=0m_{n}=0. Then the sum m1+m2++mn=(n1)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 1inbb+1 for nb<inj=\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+j1=ab=n0modnm_{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 (1in)(1 \leq i \leq n) a number jj (1jn)(1 \leq j \leq n) such that the sum mi+mi+1++mi+j1m_{i}+m_{i+1}+\ldots+m_{i+j-1} is divisible by nn. Here we even have jnj \neq n, since the sum of all mim_{i} is not divisible by nn.
Now, for 0kn10 \leq k \leq n-1, we construct a finite sequence of integers i0,i1,,ini_{0}, i_{1}, \ldots, i_{n} with ik+1ikn1i_{k+1}-i_{k} \leq n-1 (1), by choosing mik+1+mik+2++mik+10modnm_{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 modn\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 0r<sn0 \leq r<s \leq n that are congruent modn\bmod n. For these we have j=rs1(mij+1+mij+2++mij+1)0modn\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 isirmodni_{s} \equiv i_{r} \bmod n it follows that there exists a positive integer dd with isir=dni_{s}-i_{r}=d \cdot n. By (1), isir(n1)ni_{s}-i_{r} \leq(n-1) n, so it follows that dn1d \leq n-1. Then j=rs1(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,444 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.