Maths Olympiad Prep

Library / /151 of 520

Number theory Difficulty 5.3 AIME, harder Find the answer

2302 \cdot 30 Find the smallest positive integer nn, such that for any selection of nn integers, there exist at least two numbers whose sum or difference is divisible by 1991.
(Australian Mathematics Competition, 1991)

A number or a short expression. Spacing and $ signs are ignored.

Solution

[Solution] Take a set of 996 integers
M={aiai=0,1,2,,995}. M=\left\{a_{i} \mid a_{i}=0,1,2, \cdots, 995\right\} .

Then for all ij,i,j=0,1,2,,995i \neq j, \quad i, j=0,1,2, \cdots, 995.
\begin{array}{l} a_{i}+a_{j} \leqslant 995+994=1989, \\ 0996$, so there exist at least two different numbers $a_{i}, a_{j}$, such that $a_{i}=-a_{j}$, thus we have
1991 \mid\left(a_{i}+a_{j}\right) \text {. }

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.