Given $n > 0$, let $S$ be a set whose elements are positive integers $\leq 2n$ such that if $a$ and $b$ are in $S$ and $a\neq b$ then $a\nmid b$ . What is the maximum number of integers that $S$ can contain? [Hint: $S$ can contain at most one of the integers $1$, $2$, $2^2$, $2^3$, $\cdots$, at most one of $3$, $3\cdot2$, $3\cdot 2^2$, $\cdots$ , etc.]

I proceeded as follows: Suppose prime numbers $p_i$ and $p_j$ divide $2n$. Let $\alpha_i$ be the maximum value for which $p_i^{\alpha_i}$ divides $2n$. Then $S$ can contain elements of form $p_1^{k_1}p_2^{k_2}\cdots p_i^{k_i}\cdots p_j^{k_j}\cdots p_m^{k_m}$ and $p_1^{k_1}p_2^{k_2}\cdots p_i^{k_i-1}\cdots p_j^{k_j}\cdots p_m^{k_m+1}$. Thus,

$|S|=\sum{min(\alpha_i,\alpha_j)}$ where $i<j$.

That is , $|S|=\sum((k-i)\alpha_i)$ where $i < k$ and $\alpha_i < \alpha_j$ for $i<j$

Am I missing something ? Is there something very simple hidden somewhere ?


1 Answer 1


It is clear that the numbers $n+1$ to $2n$ work. We show that $S$ cannot have more than $n$ elements.

If $S$ has more than $n$ elements, there must be a pair $(a,b)$ with $b=2^k a$ for some $k\ge 1$. For given any odd $q$, let the family of $q$ be the set of all $2^kq$. with $2^kq\le 2n$. There are $n$ families, so by the Pigeonhole Principle if we pick $n+1$ or more numbers $\le 2n$, some pair will be in the same family.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .