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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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