Does $\{1,2,\ldots,3000\}$ contain a subset of $2000$ integers with no member twice another? Does the set $X=\{1,2,\ldots,3000\}$ contain a subset $A$ of $2000$ integers in which no member of $A$ is twice another member of $A$?
I started by putting $P=[1501,3000]$, but twice any integer in $P$ is too big to belong to $X$.
I am stuck and need help.
 A: This is a well-known problem.  See here, with solution, published in 1996.
Summarizing:  Having put [1501,3000] into our set, the interval [751,1500] is excluded, so we need 500 from [1,750].  Having then added [376,750] to our set, the interval [188,375] is excluded, so we need 125 from [1,187].  And recurse until done.
A: I don't feel like these above solutions is good enough, it seems to be somewhat hand-wavey (it assume certain solution is the best and proceed to calculate base on that). So I provide a solution, that eventually will reach the same conclusion.
For each odd number $n<3000$, define $P_{n}=\{2^{k}n|0\leq k;2^{k}n\leq 3000\}$. Easily check that those $P_{n}$ are disjoint from each other, and their disjoint union is indeed $[1,3000]$.
Now considering any subset $A$. We can easily prove that if for each odd $n$ then $A\bigcap P_{n}$ do not contain any member twice another, then $A$ itself will also have that property. Hence constructing an $A$ with maximum order involve constructing all those $A\bigcap P_{n}$ that individually have maximum order. The maximum possible order of $A\bigcap P_{n}$ is $[\frac{|P_{n}|+1}{2}]$ (the bracket stand for floor, I do not know how to write that floor bracket).
Now the question boil down to finding the number of possible $n$ of a given value of $[\frac{|P_{n}|+1}{2}]$. This is not too hard. If $[\frac{|P_{n}|+1}{2}]=m$ for some integer $m$, then $|P_{n}|=2m-1$ or $2m$. Not just that $|P_{n}|=k_{\max}+1$ where $k_{\max}$ is the maximum $k$ such that $2^{k}n\leq 3000$. Hence $k_{\max}=2m-2$ or $2m-1$. In other word, $2^{2m-2}n\leq 3000<2^{2m}n$. The maximum possible $n$ in that case is $[\frac{3000}{2^{2(m-1)}}]$ and minimum is $[\frac{3000}{2^{2m}}]+1$.
All that's left is to actually make the calculation for each $m$. Note that we are looking for odd $n$ only.
For $m=1$ we get $751\leq n\leq 3000$ so number of possible $n$ is $1125$.
For $m=2$ we get $188\leq n\leq 750$ so number of possible $n$ is $281$.
For $m=3$ we get $47\leq n\leq 187$ so number of possible $n$ is $71$.
For $m=4$ we get $12\leq n\leq 46$ so number of possible $n$ is $17$.
For $m=5$ we get $3\leq n\leq 11$ so number of possible $n$ is $5$.
For $m=6$ we get $1\leq n\leq 2$ so number of possible $n$ is $1$.
So maximum order is $1\times 1125+2\times 281+3\times 71+4\times 17+5\times 5+6\times 1=1999$. Hence it is impossible.
A: Not sure if this is all correct; I'll just put it out there for people to verify.
Start with all odd numbers $\{1,\ldots,2999\}$. 
Their doubles are numbers with one factor of $2$, so now add all numbers with $2$ factors of $2$. That is the set $\{4,12,20,28,\ldots\}$. Now add the numbers with $4$ factors of $2$, and so on...
The number of odd numbers is $$\left\lfloor \frac{3000-1}{2}\right\rfloor +1= 1500.$$ The number of numbers with $2$ factors of $2$ is $$\left\lfloor \frac{3000-4}{8}\right\rfloor +1 = 375.$$ The next few are $$\left\lfloor \frac{3000-16}{32}\right\rfloor +1 =94 \\ \left\lfloor \frac{3000-64}{128}\right\rfloor +1=23 \\ \left\lfloor \frac{3000-256}{512}\right\rfloor +1=6 $$ and finally $1$. These sum to $$1500+375+94+23+6+1=1999$$ We need one more! 
A: Outline:    
(1) A number can be in the target set S if either (a) twice the number is larger than 3,000 (set $S_0$), or (b) twice the number is not in S ($S_1$; $S = S_0 \cup S_1$).    
(2) if you remove 1 number from $S_0$, how many numbers can you now add to $S_1$ at best? What in the inverse case? So which set do you "fill up first?"   
(3) Assuming you choose all from (a) as $S_0$, what is the largest integer $a$ to be added to $S_1$ from (b) assuming no overlap between $S_0$ and $S_1$?
(3) how many odd integers $\le a$ are there? Assuming you choose all, can you add any more evens? If you choose an even $\le a$, how many odds to you need to remove? So given a maximal $S_0$, what is the maximal size of $S_1$?    
(4) conclude what the largest cardinality for $S= S_0 \cup S_1$ is
A: Consider the set $N:=\{1,...,n\}$ and the subsets of $N$ of maximal size subject to no element of $N$ being twice another. Among such subsets, choose a set $M$ that contains the least number of even integers. Let $m\in M$ be even. Then $m/2\not\in M$. If $m/2$ were odd, we could replace $m$ by it and so get a set with fewer even numbers; so any even element of $M$ is divisible by $4$. Continuing in this way, it is easily seen that $M$ comprises all elements of $N$ of the form $4^kl$, where $k$ is a nonnegative integer and $l$ is odd.
In the case $N=\{1,...,3000\}$, we can include in $M$ all $1500$ odd integers, the $375$ odd multiples of $4$, the $94$ odd multiples of $16$, the $23$ odd multiples of 64, the $6$ odd multiples of $256$, and the solitary $1024$: altogether $1500+375+94+23+6+1=1999$ numbers. So the answer is no, we can't quite manage it.
