We are given the set of numbers $T$ from $1$ to $2k$, in this case $k=1000$.
What is the smallest $n$, so that for $n$ selected numbers out of the set $T$ there definetly exists a number $a$ such that $a$ and $2a$ are both in the set?
Intuitively, the first thing I would have said is $k+1$ traditional pigeon-hole principle. It isn't hard to see that that is wrong- take all the odds and the numbers $4$ and $16$ for example. Grouping, we can combine numbers with their double and argue that only one in this group can be included in this grouping if we don't want to obtain doubles. Yet this grouping is not bijective, take for example the case $a=500$, which is grouped with $b=1000$, but $c=2000$ also is grouped with $b$, so it suffices to take out $b$. Knowing this, we could do an Inclusion-Exclusion Principle solution but it is quite time-consuming. Is there a more elegant solution?
For numbers $1$ to $2k \, (= 2000)$, the minimum size $n$ of a random set that will ensure, there is at least one pair of $a, 2a$ present in the set -
Basically it works out to $n \displaystyle \ge 1 + \sum \limits_{i \ge 0} \lceil \frac{k}{2^{2i}}\rceil \, (2^{2i} \le 2k$, even powers of $2$). I think we can write a closed form but will be approximation.
Details -
Any or all of the odd numbers can be randomly present. So we need at least $k+1$ numbers.
So $ n \ge 1001$.
Now if we choose any number of the form $\, 2(2m-1)$ where $(m \ge 1, \in \mathbb{Z+})$ to be in the set, the set will have at least one pair of $(a, 2a)$.
But if the randomly chosen number to be in the set is of the form $4(2m-1)$ instead of $2(2m-1)$, then we still do not have a pair of $a,2a$.
Numbers of the form $4(2m-1) = 250 \,$ ($\lceil \frac{k}{4} \rceil)$.
So we are covered if the randomly chosen numbers are of the form $2(2m-1), 4(2m-1), 8(2m-1)$ but not covered for $4^2(2m-1)$.
Numbers of the form $4^2(2m-1) = 63 \,$ ($\lceil \frac{k}{4^2} \rceil)$.
Similarly, numbers of the form $4^3(2m-1) = 16 \,$ ($\lceil \frac{k}{4^3} \rceil)$.
numbers of the form $4^4(2m-1) = 4 \,$ ($\lceil \frac{k}{4^4} \rceil)$.
numbers of the form $4^5(2m-1) = 1\,$ ($\lceil \frac{k}{4^5} \rceil)$.
So, $n \ge 1001 + 250 + 63 + 16 + 4 + 1 = 1335$ will ensure there is at least a pair of numbers of the form $a,2a$.