7
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Try add the odd numbers less than 1501 $\endgroup$
    – DiegoMath
    Jul 3 '14 at 15:44
  • 1
    $\begingroup$ (1) This is not set theory, not even elementary set theory I think. More like combinatorics. (2) The conditions don't state that "twice any member of A is still a member of X," so it's no issue if twice an integer in P is too big to belong to X. The problem with your example P is that it does not contain 2000 integers. $\endgroup$
    – blue
    Jul 3 '14 at 15:44
  • $\begingroup$ @blue the OP said the solution is incomplete. $\endgroup$
    – DiegoMath
    Jul 3 '14 at 15:45
  • 4
    $\begingroup$ How many pairs $\{n, 2n\}$ are there in $\{1, 2, \dotsc, 3000\}$? $\endgroup$
    – rogerl
    Jul 3 '14 at 15:51
  • 2
    $\begingroup$ The way to deal with this kind of problem is to change the 3000 to 30, or even to 3. Are there 2 numbers in $\{1, 2, 3\}$ where no number is twice another? Are there 4 numbers in $\{1, 2, \ldots 6\}$ where none is twice another? Are there 6 numbers in $\{1, 2,\ldots, 9\}$ where no number is twice another? If you can solve those, can you solve the case with 3000 numbers? $\endgroup$
    – MJD
    Jul 3 '14 at 15:59
9
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Forgive me my ignorance, but I cannot see why this method would give us the largest possible set having the property $2x \in A \implies x \not \in A.$ $\endgroup$ Jul 3 '14 at 16:07
  • $\begingroup$ @IndrayudhRoy: Because any number you add from $[750,1500]$ forces the removal of one from $[1501,3000]$ So the total number from $[750,3000]$ is no more than $1500$ $\endgroup$ Jul 3 '14 at 16:14
  • $\begingroup$ So can it be done or not? $\endgroup$
    – user142299
    Jul 3 '14 at 16:17
  • $\begingroup$ @gnometorule Are you sure? I thought I had a way to get it up to $1999$. $\endgroup$
    – user142299
    Jul 3 '14 at 16:28
  • $\begingroup$ @gnometorule See my answer - I likely made an error. $\endgroup$
    – user142299
    Jul 3 '14 at 16:35
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ "\lfloor" and "\rfloor". $\endgroup$ Jul 4 '14 at 18:41
2
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ Very pretty! +1 (makes the 2,000 also more meaningful). $\endgroup$ Jul 3 '14 at 16:40
  • $\begingroup$ ...actually I like this, but as you were, I think, also looking for feedback, doesn't it show only that you can get at least 1,999? You can probably tie this up with some addition though if you want to. The idea is just pretty, $\endgroup$ Jul 3 '14 at 16:45
  • $\begingroup$ @gnometorule You are right it's not a proof. I think Gina's answer may be a more rigorous version of the same idea though. $\endgroup$
    – user142299
    Jul 3 '14 at 16:50
  • $\begingroup$ I agree, but I think all the key ideas are in your answer. It's nice & creative. ;) $\endgroup$ Jul 3 '14 at 16:55
  • $\begingroup$ @gnometorule Thank you! $\endgroup$
    – user142299
    Jul 3 '14 at 17:01
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.