3
$\begingroup$

Prove that if you choose $8$ numbers from the set $\{1,2,3,\ldots,14\}$, at least one of these numbers divides another?

How can I prove this? I don't know if I have to go with pigeonhole principle or something else.

$\endgroup$

closed as off-topic by user21820, Asaf Karagila, user91500, Frits Veerman, Namaste Jun 20 '17 at 13:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user21820, Asaf Karagila, user91500, Frits Veerman, Namaste
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ Go with the pigeonhole principle. Hint: any number can be written as an odd number times a power of two. If you do this with each of your 8 numbers, then you're going to get the same odd number twice (because there are only 7 possible values). $\endgroup$ – bof Jun 20 '17 at 1:34
  • 1
    $\begingroup$ It also helps to know that, if two numbers are powers of two, one of them divides the other one. $\endgroup$ – bof Jun 20 '17 at 1:34
11
$\begingroup$

Each of the numbers belongs to one of the following seven sets:

$\{1,2,4,8\}$
$\{3,6,12\}$
$\{5,10\}$
$\{7,14\}$
$\{9\}$
$\{11\}$
$\{13\}$

If two numbers belong to the same one of those sets, the smaller divides the larger.

By the pigeonhole principle, two of your eight numbers belong to the same one of those seven sets.

In other words:

The set $\{1,2,3,\dots,14\},$ partially ordered by divisibility, is the union of $7$ chains, as shown above. Therefore, every antichain (set of pairwise incomparable elements) has at most $7$ elements, one from each chain. Therefore, a set of $8$ elements cannot be an antichain; it must contain two numbers where are comparable, i.e., one divides the other.

$\endgroup$
  • 1
    $\begingroup$ Motivation for this solution is provided by Dilworth's theorem. By that theorem, bof could be certain in advance that (if the problem statement was correct) a partition of the set into seven chains or less would be possible $\endgroup$ – user49640 Jun 20 '17 at 5:37
  • $\begingroup$ Is it really accurate to put 1 in the first set? $\endgroup$ – Mateen Ulhaq Jun 20 '17 at 6:17
  • 1
    $\begingroup$ @MateenUlhaq Yes, because the numbers $2,\ 4,\ 8$ (like all other numbers) are divisible by $1.$ Of course I could just as well have put $1$ in any of the other sets, but it seemed neatest to do it this way. Why do you ask? $\endgroup$ – bof Jun 20 '17 at 6:21
4
$\begingroup$

Proposition. If we have the set $[2n] = \{1, 2, 3, ..., 2n\}$ and choose any $n+1$ integers, there exist two such that one divides the other.

Proof. Write each number $m$ as the unique product of an odd component and an even component by repeatedly factoring out $2$: $$ m = 2^{p_m}(2k_m+1) $$ Since $1 \leq m \leq 2n$, we have that $$ 0 \leq k_m <n $$ for each $m$. Since we have $n+1$ numbers ($m$) and $n$ possible values for the odd component ($k_m$), there are two numbers, call them $a$ and $b$, among the $n+1$ chosen that have the same $k_m$: $$ a = 2^{p_a}(2k+1) \qquad\qquad b = 2^{p_b}(2k+1) $$ If $p_a < p_b$, then $a \mid b$.

If $p_a > p_b$, then $b \mid a$.

$\endgroup$
  • 1
    $\begingroup$ Good. And of course $n+1$ is best possible, because among the $n$ numbers $n+1,\ n+2,\ \dots,\ 2n$ none divides another. $\endgroup$ – bof Jun 20 '17 at 6:24
4
$\begingroup$

There are few enough numbers that we can just brute force this:

Obviously you can't pick 1.

You can't pick 2 either, for that will rule out the rest of the even numbers, and with 1 gone there are only 6 odd numbers left.

OK, so what is the best we can do?

With 1 gone, we can definitely pick 11 and 13 (that's 2)

You can pick only one of 7 and 14 (3)

You can pick only one of 5 and 10 (4)

You can pick only one out of 3 and 9 (5)

You can pick only one out of 6 and 12 (6)

You can pick only one out of 4 and 8 (7)

So, you can't get to 8

$\endgroup$

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