Maths Olympiad Prep

Library / /20 of 22

Number theory Difficulty 7.1 National olympiad, round 2 Prove it Croatia

Determine all positive integers n2n \ge 2 which satisfy the following condition: For all integers a1,a2,,ana_1, a_2, \dots, a_n such that their sum is not divisible by nn, there exists an integer i{1,2,,n}i \in \{1, 2, \dots, n\} such that none of the nn numbers

ai, ai+ai+1, , ai+ai+1++ai+n1 a_i,\ a_i + a_{i+1},\ \dots,\ a_i + a_{i+1} + \dots + a_{i+n-1}
is divisible by nn, where we define ai=aina_i = a_{i-n} for the case i>ni > n.

Solution

All such numbers are primes.

Let nn be a composite number, i.e. n=abn = ab, where a2a \ge 2 and b2b \ge 2 are positive integers.
Observe the sequence
0,b,b,,b,0, b, b, \dots, b,
in which the number bb is appearing ab1ab-1 times. The sum of all numbers in that sequence is ab2bab^2-b, which is not divisible by n=abn=ab. However, notice that, no matter on the initial index of the sequence, the sum of aa (or a+1a+1, if we pass through element 0 of the sequence) consecutive numbers in the sequence will be equal to abab, and therefore divisible by n=abn=ab.

Let n=pn = p be a prime number. Let us assume the opposite: there exist positive integers a1,a2,,apa_1, a_2, \dots, a_p which all add up to a number not divisible by pp, but for all i{1,2,,p}i \in \{1, 2, \dots, p\} there exists j{i+1,i+2,,i+p1}j \in \{i+1, i+2, \dots, i+p-1\} such that the number ai+ai+1++aj1a_i + a_{i+1} + \dots + a_{j-1} is divisible by pp. Reminder: all operations on indices are made using convention ai=aipa_i = a_{i-p} for i>pi > p.

Let us now make a graph consisted of pp vertices (indicating numbers a1,a2,,apa_1, a_2, \dots, a_p). The two vertices aia_i and aja_j are joined with directed edge if the sum ai+ai+1++aj1a_i+a_{i+1}+\dots+a_{j-1} is divisible by pp. Due to the assumption, from any vertex there is at least one edge incident to that vertex. Since there are only finitely many vertices in the graph, we conclude that the graph has a cycle.

Consider that cycle and let us sum up all sums which correspond to edges of that cycle. Notice that all numbers a1,a2,,apa_1, a_2, \dots, a_p appear equally many times in those sums, and let us denote that number of occurrence by kk. Moreover, in that cycle we have at most pp edges, and for each edge the corresponding sum consists of at most p1p-1 addends, since the sum of all numbers in the original sequence is not divisible by pp. Hence, kp1k \le p-1. However, each of those sums along the edges of the cycle is divisible by pp, so the sum of all those sums in the cycle is pp as well, and we have
pk(a1+a2++ap). p \mid k(a_1 + a_2 + \dots + a_p).
This gives contradiction, since k<pk < p, i.e. pkp \nmid k and pa1+a2++app \nmid a_1 + a_2 + \dots + a_p.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.