5
$\begingroup$

This problem comes from a seemingly innocuous question from a professor during a lesson for a Math Olympiad course. [A part of this question is really a classic of number theory/combinatorics]

Problem: Let $S$ be a a non-empty subset of $\{1,2,\ldots,2n\}$. It is clear that if $|S|$ is "enough large" then, independently from the choice of $S$, there are for sure some distinct $a,b \in S$ such that $a$ divides $b$.

Then, what is the maximal $k$ such that, for some $S$ with cardinality $k$, if $a,b$ are distinct members of $S$ then $a$ does not divide $b$?

[Ps. I know the solution]

$\endgroup$
  • 2
    $\begingroup$ If you know the solution, then what are you looking for here? $\endgroup$ – Omnomnomnom Aug 25 '15 at 15:51
  • $\begingroup$ A wholesome discussion $\endgroup$ – user137794 Aug 25 '15 at 15:52
  • 1
    $\begingroup$ With $100$ instead of $1000$, a golden oldie that has appeared more than once on MSE. $\endgroup$ – André Nicolas Aug 25 '15 at 15:54
  • 1
    $\begingroup$ No, I find searching MSE too difficult. $\endgroup$ – André Nicolas Aug 25 '15 at 15:58
  • 1
    $\begingroup$ Not quite. though a small twist on that solution will do it. $\endgroup$ – André Nicolas Aug 25 '15 at 16:11
3
$\begingroup$

Let $S=\{n+1,n+2,\ldots,2n\}$. The claim is that $|S|$ is maximal.

To prove this, form descending sequences starting with each term in $S$, where each sequence is finite and ends on an odd term and the term in any sequence is the previous term divided by 2. Denote each sequence by its starting term, e.g. $$\begin{align} S^{(2n)}&=\{2n,n,\ldots\} \\ S^{(2n-1)}&=\{2n-1\} \\ &\quad\vdots \\ S^{(n+1)}&=\{n+1,\ldots\} \end{align}$$

Every number in $\{1,2,\ldots,2n\}$ appears in exactly one of the $S^{(k)}$ because:

  1. Surjective. Every number inclusively between $1$ and $n$ has a multiple of a power of two inclusively between $n+1$ and $2n$. If not, $2 \ge \frac{2n+1}{n}$, which is absurd.
  2. Injective. No number can appear in more than one sequence. If this was untrue we could find two distinct terms in $\{n+1,n+2,\ldots,2n\}$, one of which is a multiple (of a power of two) of the other.

It is clear that every pair of terms in a given $S^{(k)}$ has the smaller term dividing the larger one, so we are free to choose at most one term from each $S^{(k)}$, i.e. $|S|\le n$ for any prospective set $S$. It is also clear that choosing $S$ as originally proposed gives $|S|=n$, so this is maximal.

$\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.