Let $S$ be a set consisting of all positive integers less than or equal to $100$.
Let $S$ be a set consisting of all positive integers less than or equal to $100$. Let $P$ be a subset of $S$ such that there do not exist two elements $x,y\in P$ such that $x=2y$. Find the maximum possible number of elements of $P$.
Is answer 67?
$\endgroup$ 12 Answers
$\begingroup$Consider a sequence $m2^k$ with $m$ odd. $P$ can at most contain every other element of this sequence, so it will be maximal if it contains $m2^{2j}$ for $j\in\mathbb N_0$ where possible, and doesn't contain $m2^{2j+1}$.
For $m=1$ we can include up to $j=3$; for $3\le m\le 5$ we can include up to $j=2$; for $7\le m\le25$ we can include up to $j=1$; and for the rest we can only include the odd numbers themselves.
That makes a total of $1\cdot4+2\cdot3+10\cdot2+37\cdot1=67$.
$\endgroup$ $\begingroup$$\{1, 3, 5, \dotsc, 99\}$ has 50 elements in it, and we can't include any singly-even numbers (i.e. those of the form $4k - 2 = 2(2k-1)$). But we can add the 13 doubles of these, $8k-4$ for $1 \le k \le 13$. We can also throw in a few multiples of $8$, namely $16$, $48$, $64$, and $80$, all the others being excluded for one reason or another. This gives 67. (It doesn't show why 67 is the best we can do.)
$\endgroup$ 0
