Maths Olympiad Prep

Library / /6 of 16

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 xixj,1i<jmx_{i}-x_{j}, 1 \leq i<j \leq m is divisible by 11 ; and
b) The sum x2x3xm+x1x3xm++x1x2xm1x_{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,1imx_{i}, 1 \leq i \leq m, are all different (mod11)(\bmod 11)
Hence, the number of natural numbers satisfying the conditions is at most 11.
If xj0(mod11)x_{j} \equiv 0(\bmod 11) for some jj, then
x2x3xm+x1x3xm++x1x2xm1x1xj1xj+1xm(mod11) 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 xi0(mod11)x_{i} \equiv 0(\bmod 11) for some iji \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 2310,1310,2 \cdot 3 \cdots \cdot 10,1 \cdot 3 \cdots \cdots 10, \ldots, 1291 \cdot 2 \cdots \cdot 9 are all different (mod11)(\bmod 11), and so
2310+1310++1291+2++10(mod11) 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=5111+2+\cdots+10=55=5 \cdot 11.

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.