9.3. Find the smallest natural number $n$ such that in any set of $n$ distinct natural numbers, not exceeding 1000, it is always possible to select two numbers, the larger of which does not divide the smaller one.
Answer. $n=11$.

Solution. Among the first 10 powers of two $1=2^{0}, 2=2^{1}, 4=2^{2}, \ldots, 512=2^{9}$, in each pair of numbers, the larger number is divisible by the smaller one, hence $n \geq 11$.

On the other hand, let there be some set of $n \geq 11$ numbers where the larger number of each pair is divisible by the smaller one. Arrange all the numbers in ascending order; from the assumption, it follows that each subsequent number is at least twice the previous one. Therefore, the largest number is at least $2^{10}=1024$ times larger than the first, meaning it is greater than 1000 - a contradiction.

Instructions. Proving $n \geq 11$ with an example: 3 points. Proving only $n \leq 11$ (the second part): 4 points.