8. What is the least number of odd numbers that can be chosen from the set of all odd numbers lying between 16 and 2016, so that no one of the chosen numbers is divisible by any other?


Solution. We will select all odd numbers from 673 to 2015, their quantity is

$\frac{2015-671}{2}=672$. None of these numbers is divisible by another, because in division, the result should be an odd number, which is at least 3, but $673-3>2015$.

We will show that it is impossible to select more than 672 numbers satisfying the condition of the problem. Indeed, let's divide all odd numbers from 17 to 2015 into 672 groups, generated by the selected numbers and including the generating number and all its divisors, such that the result of division by which is a power of three: $\{2015\},\{2013,671\},\{2011\},\{2009\},\{2007,669,223\}, \ldots,\{675,225, 75,25\},\{673\}$. If more than 672 numbers are selected, then by the pigeonhole principle, at least two of them will end up in the same group, meaning one of them will be divisible by the other.

Note that the selected set of 672 numbers is not unique. For example, if we replace the number $2013=671 \cdot 3$ with 671, the new set will also satisfy the condition of the problem.

Answer variant 1: 672. Suitable, for example, the set 673,..., 2015.

Answer variant 2: 667. Suitable, for example, the set 669, ..., 1999.

Answer variant 3: 673. Suitable, for example, the set 673, ..., 2017.

Answer variant 4: 670. Suitable, for example, the set 671, ..., 2009.

Scoring criteria: 15 points - correct reasoning and correct answer, 10 points - correct answer and a correct example provided, but no proof that more numbers cannot be selected.

## 2015/2016 academic year  CRITERIA FOR DETERMINING WINNERS AND PRIZE WINNERS ${ }^{1}$  of the schoolchildren's olympiad  «LOMONOSOV»  in mathematics  10-11 grades  ELIMINATION STAGE

WINNER:

From 91 points inclusive and above.

PRIZE WINNER:

From 60 points to 90 points inclusive.

## FINAL STAGE

WINNER (Diploma I degree):

From 90 points inclusive and above.

PRIZE WINNER (Diploma II degree):

From 80 points to 89 points inclusive.

PRIZE WINNER (Diploma III degree):

From 65 points to 79 points inclusive.[^0]


[^0]:    ${ }^{1}$ Approved at the meeting of the jury of the schoolchildren's olympiad «Lomonosov» in mathematics