Maths Olympiad Prep

Library / Junior Balkan Mathematics Olympiad /6 of 15

Junior Balkan Mathematics Olympiad

Number theory Difficulty 5.9 AIME, harder Prove it JBMO

Problem:
Find the maximum number of natural numbers x1,x2,…,xmx_{1}, x_{2}, \ldots, x_{m} satisfying the conditions:
a) No xi−xj,1≤i<j≤mx_{i}-x_{j}, 1 \leq i<j \leq m is divisible by 11 ; and
b) The sum x2x3…xm+x1x3…xm+⋯+x1x2…xm−1x_{2} x_{3} \ldots x_{m}+x_{1} x_{3} \ldots x_{m}+\cdots+x_{1} x_{2} \ldots x_{m-1} is divisible by 11 .

Solution

Solution:
According to a), the numbers xi,1≤i≤mx_{i}, 1 \leq i \leq m, are all different ( mod 11)(\bmod 11)
Hence, the number of natural numbers satisfying the conditions is at most 11.
If xj≡0( mod 11)x_{j} \equiv 0(\bmod 11) for some jj, then
x2x3…xm+x1x3…xm+⋯+x1x2…xm−1≡x1…xj−1xj+1…xm( mod 11) x_{2} x_{3} \ldots x_{m}+x_{1} x_{3} \ldots x_{m}+\cdots+x_{1} x_{2} \ldots x_{m-1} \equiv x_{1} \ldots x_{j-1} x_{j+1} \ldots x_{m} \quad(\bmod 11)
which would lead to xi≡0( mod 11)x_{i} \equiv 0(\bmod 11) for some i≠ji \neq j, contradicting (1).
We now prove that 10 is indeed the required maximum.
Consider xi=ix_{i}=i, for all i∈{1,2,…,10}i \in\{1,2, \ldots, 10\}. The products 2⋅3⋯⋅10,1⋅3⋯⋯10,…2 \cdot 3 \cdots \cdot 10,1 \cdot 3 \cdots \cdots 10, \ldots, 1⋅2⋯⋅91 \cdot 2 \cdots \cdot 9 are all different ( mod 11)(\bmod 11), and so
2⋅3⋯⋯10+1⋅3⋯⋯10+⋯+1⋅2⋯⋅9≡1+2+⋯+10( mod 11) 2 \cdot 3 \cdots \cdots 10+1 \cdot 3 \cdots \cdots 10+\cdots+1 \cdot 2 \cdots \cdot 9 \equiv 1+2+\cdots+10 \quad(\bmod 11)
and condition b) is satisfied, since 1+2+⋯+10=55=5⋅111+2+\cdots+10=55=5 \cdot 11.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.