Maths Olympiad Prep

Library / /514 of 520

Number theory Difficulty 7.8 National olympiad, round 2 Prove it

12. Let nn be an odd number greater than 1. Prove: There exist 2n2 n integers a1,a2,,ana_{1}, a_{2}, \cdots, a_{n}; b1,b2,,bnb_{1}, b_{2}, \cdots, b_{n}, such that for any k{1,2,,n1}k \in\{1,2, \cdots, n-1\}, the following 3n3 n numbers
ai+ai+1;ai+bi;bi+bi+k.i=1,2,,n.a_{i}+a_{i+1} ; a_{i}+b_{i} ; b_{i}+b_{i+k} . \quad i=1,2, \cdots, n .

form a complete residue system modulo 3n3 n, where an+1=a1,bn+j=bj(1jn)a_{n+1}=a_{1}, b_{n+j}=b_{j}(1 \leqslant j \leqslant n).

Solution

12. Let ai=3i2,bi=3i1,i=1,2,,na_{i}=3 i-2, b_{i}=3 i-1, i=1,2, \cdots, n. Then for any kN,k<nk \in \mathbf{N}^{*}, k<n, we have
ai+ai+12(mod3),ai+bi0(mod3),bi+bi+k1(mod3)a_{i}+a_{i+1} \equiv 2(\bmod 3), a_{i}+b_{i} \equiv 0(\bmod 3), b_{i}+b_{i+k} \equiv 1(\bmod 3)

Thus, when we denote
A={ai+ai+11in},B={ai+bi1in},C={bi+bi+k1A=\left\{a_{i}+a_{i+1} \mid 1 \leqslant i \leqslant n\right\}, B=\left\{a_{i}+b_{i} \mid 1 \leqslant i \leqslant n\right\}, C=\left\{b_{i}+b_{i+k} \mid 1 \leqslant\right.
in}i \leqslant n\},
in the sets A,B,CA, B, C, any two numbers taken from different sets are not congruent modulo 3n3 n (since they are not congruent modulo 3). Therefore, to prove that ABCA \cup B \cup C forms a complete residue system modulo 3n3 n, it suffices to show that any two numbers in AA are not congruent modulo 3n3 n (the same can be shown for BB and CC).

If ai+ai+1aj+aj+1(mod3n)a_{i}+a_{i+1} \equiv a_{j}+a_{j+1}(\bmod 3 n), then
2ai+32aj+3(mod3n)2 a_{i}+3 \equiv 2 a_{j}+3(\bmod 3 n)

This leads to aiaj(mod3n)a_{i} \equiv a_{j}(\bmod 3 n), and thus i=ji=j. This shows that any two numbers in AA are not congruent modulo 3n3 n.

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.