Maths Olympiad Prep

Library / /23 of 25

Number theory Difficulty 7.5 National Olympiad, round 2 Prove it North Macedonia

The natural number n>1n > 1 is "good" if for every natural numbers b1,b2,,bn1b_1, b_2, \dots, b_{n-1} such that 1b1,b2,,bn1n11 \le b_1, b_2, \dots, b_{n-1} \le n-1 we have there exist I{1,2,,n1}I \subseteq \{1, 2, \dots, n-1\}, such that kIbki(modn)\sum_{k \in I} b_k \equiv i \pmod n, for every i{0,1,,n1}i \in \{0, 1, \dots, n-1\} (empty sum is equal to zero). Find all the "good" numbers.

Solution

We will prove that nn is a "good" number if and only if it is prime.

First we will prove that if nn is not prime, then it is not "good". Let n=rsn = rs, 1<r,s<n1 < r, s < n. For b1=b2==bn1=rb_1 = b_2 = \dots = b_{n-1} = r then
{bi(modn)I{1,2,,n1}}={0,r,2r,,nr} \{\sum b_i \pmod n \mid I \subseteq \{1, 2, \dots, n-1\}\} = \{0, r, 2r, \dots, n - r\}
and for i=1i = 1 there does not exist a subset II.

Now we prove that every prime number is "good".
Let pp be a prime number. There exist at least r+1r + 1 different numbers (mod pp) as sums of the elements b1,b2,,brb_1, b_2, \dots, b_r, where 1rn11 \le r \le n-1, 1b1,b2,,brp11 \le b_1, b_2, \dots, b_r \le p-1. The proof is by induction.

For r=1r = 1, empty sum is equal to zero (mod pp) and the sum of b1b_1 is not.

Let r<n1r < n-1 and let the proposition be true for rr.
Let the proposition be not true for p+1p + 1. Let 1b1,b2,,br,bp11 \le b_1, b_2, \dots, b_r, b \le p-1 be the numbers such that their sums do not give at least r+2r + 2 different numbers (mod pp). Since the proposition holds for rr, there exist sums 0=σ0,σ1,,σr0 = \sigma_0, \sigma_1, \dots, \sigma_r distinct from each other (mod pp), for b1,b2,,brb_1, b_2, \dots, b_r. Then σ0+b,σ1+b,,σr+b\sigma_0 + b, \sigma_1 + b, \dots, \sigma_r + b do not give a new number (mod pp) (different from 0=σ0,σ1,,σr0 = \sigma_0, \sigma_1, \dots, \sigma_r). Because σi+bσi(modp)\sigma_i + b \ne \sigma_i \pmod p, it holds 0,b,2b,,(r+1)b{σ0,σ1,,σr}0, b, 2b, \dots, (r+1)b \in \{\sigma_0, \sigma_1, \dots, \sigma_r\}. But there exist i,ji, j such that 0i<jr+10 \le i < j \le r+1 and ibjb(modp)ib \equiv jb \pmod p, from where (ji)b0(modp)(j-i)b \equiv 0 \pmod p. This is a contradiction with pp being a prime number.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.