Find smallest $n$ fulfilling requirement 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?
 A: 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$.
A: This is not a full answer, but it should lead to a full answer with some more work I think.
Definition. A set $A\subset T$ is called admissible if there is no $a\in A$ such that $2a\in A$.
We note that the desired $n$ is given by $$n-1=\max\{|A|:A\subset T \text{ is admissible}\},$$
where $|A|$ is the cardinality of $A$.
Lemma. There is a set $B\subset T$ such that every odd number from one to $2k$ is in $B$ and such that $$|B|=\max\{|A|:A\subset T \text{ is admissible}\}.$$
Proof. Let $C$ be any set such that $|C|=\max\{|A|:A\subset T \text{ is admissible}\}$. Then form $B$ with the following process: For any odd number $a$ that is not in $C$, add $a$ to $C$ (and, if necessary, remove $2a$ from $C$). In short, $$B= (C\cup\{\text{odd numbers from $1$ to $2k$}\})\setminus\{2a : a \text{ is odd}\}.$$ Then $|B|\geq|C|$ so we are done. $\square$
Now we note that $B\setminus\{\text{odd numbers}\}$ cannot contain odd numbers, but it can't contain $2a$ for any odd number $a$ either.
So $B\setminus\{\text{odd numbers}\}\subset\{\text{numbers divisible by }4\}$.
So now the question is:
"Which numbers, that are divisible by $4$, can $B\setminus\{\text{odd numbers}\}$ contain?"
But that question really is equivalent to the original question, now with smaller size.
For example, for $k=1000$ after the above steps we need to look at $\{4,8,12,16,\dots,2000\}$, which is really the same as looking at $\{1,2,\dots, 500\}$. So we can reduce the problem from $k=1000$ to $k=250$. We can keep on reducing to $k=\lfloor\frac{250}4\rfloor=62$ and so on...
