Maths Olympiad Prep

Library / /319 of 520

Number theory Difficulty 6.7 National olympiad Prove it

Determine all integers n2n \geqslant 2 satisfying the following property: for all integers a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} whose sum is not divisible by nn, there exists an index ii such that none of the numbers

ai,ai+ai+1,,ai++ai+n1 a_{i}, a_{i}+a_{i+1}, \ldots, a_{i}+\cdots+a_{i+n-1}

is divisible by nn (for i>ni>n, we set ai=aina_{i}=a_{i-n} ).

Solution

These are exactly the prime numbers!

Indeed, if n=abn=ab, we can take a1=0a_{1}=0 and a2==an=aa_{2}=\cdots=a_{n}=a. The sum of the aia_{i} is a(n1)a(n-1), which is not divisible by nn. However, for any 1in1 \leqslant i \leqslant n, if i+b1ni+b-1 \leqslant n, then the number ai++ai+b1=ab=na_{i}+\cdots+a_{i+b-1}=ab=n is divisible by nn. If i+b1>ni+b-1>n, then the number ai++ai+b=ab=na_{i}+\cdots+a_{i+b}=ab=n is divisible by nn.
Conversely, suppose nn is prime, and let a1,,ana_{1}, \ldots, a_{n} be integers whose sum is not divisible by nn. If nn does not satisfy the property, then for any index ii, there exists j(i)j(i) with i+1j(i)i+ni+1 \leqslant j(i) \leqslant i+n such that

ai+ai+1++aj(i)1 a_{i}+a_{i+1}+\cdots+a_{j(i)-1}

is divisible by nn. Furthermore, since the sum of the aia_{i} is not divisible by nn, we cannot have j(i)=i+nj(i)=i+n, so i+1j(i)i+n1i+1 \leqslant j(i) \leqslant i+n-1. We then define by induction a sequence of indices (in)\left(i_{n}\right) by i1=1i_{1}=1 and in+1=j(in)i_{n+1}=j\left(i_{n}\right). We know that for all kk, the integer

aik++aik+11 a_{i_{k}}+\cdots+a_{i_{k+1}-1}

is divisible by nn; therefore, by summing, for all indices k<k<\ell, the integer

aik++ai1 a_{i_{k}}+\cdots+a_{i_{\ell}-1}

is divisible by nn. By the pigeonhole principle, there exist 1k<n+11 \leqslant k<\ell \leqslant n+1 such that iki(modn)i_{k} \equiv i_{\ell}(\bmod n). The number of terms in the sum (1) is then iiki_{\ell}-i_{k}, which is divisible by nn, so each of the aia_{i} appears exactly iikn\frac{i_{\ell}-i_{k}}{n} times. Moreover, we know that ij+1ijn1i_{j+1}-i_{j} \leqslant n-1 for all jj and that kn\ell-k \leqslant n, so iikn(n1)i_{\ell}-i_{k} \leqslant n(n-1). The sum (1) is therefore

iikn×i=1nai. \frac{i_{\ell}-i_{k}}{n} \times \sum_{i=1}^{n} a_{i} .

But iiknn1\frac{i_{\ell}-i_{k}}{n} \leqslant n-1 and cannot be divisible by nn, and the sum of the aia_{i} is not divisible by nn either. Since nn is prime, the sum (1) is not divisible by nn, leading to a contradiction.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.