## Problem 4

Given the numbers $1,2,3, \ldots, 1000$. Find the largest number $m$ with the property that by removing any $m$ numbers from these 1000 numbers, among the $1000-m$ remaining numbers, there exist two such that one divides the other.

Selected problems by Prof. Cicortas Marius

Note: a) The actual working time is 3 hours.

b) All problems are mandatory.

c) Each problem is graded from 0 to 7.

## NATIONAL MATHEMATICS OLYMPIAD

Local stage - 15.02.2014

## Grade IX

## Grading Rubric
## Problem 4

If $m \geq 500$ then, for example, by removing the numbers from 1 to 500, among the remaining numbers, from 501 to 1000, there is no pair of numbers that can be divisible by each other, because their ratio is $<2$. 2 points We will show that $m=499$ has the required property. 1 point We show that among any 501 numbers from 1 to 1000, there is one that divides another. Each of the 501 numbers is of the form $2^{k}(2 t+1), 0 \leq k \leq 9, t$ is a natural number; to each such number, we associate $2 t+1$. There are 500 odd numbers less than 1000, so two of the 501 numbers will correspond to the same odd number. Among these two numbers, one will be obtained from the other by multiplying by a power of 2. 4 points