Prove that we can always find a and b in S, a not equal to b, such that a divides b.

Question

I have found this forum very helpful in the past and can usually get good references to what I need by using the search function, but had trouble with this one:

I am working on this problem in the area of number theory dealing with division of integers.

The problem is as follows:

Prove by induction:

(g) Given an integer number n ≥ 1, let S ⊆ {1, 2, . . . , 2n} such that the number of elements in S is greater than or equal to n + 1. Prove that we can always find a and b in S, a 6= b, such that a divides b.

This is the way that I am approaching it:

After checking the base case, and assuming it true for some integer, "k", I claim that this doesn't hold for (k+1) and try to arrive at a contradiction (having found two elements that have to divide each other r).

IE- Assume that for any k, any set of greater than k+1 elements from A = {1,2,...,2k} will have elements a and b in A such that a|b.

Suppose that there are no elements a and b in any set (C) that has number of elements greater than (k+1)+1 made of elements from the set Q = {1,2,...,2(k+1)}.

Since A is a subset of Q, we have some restrictions on the elements that we can put into this set that we are constructing (C; numElements >= (k+2)). Namely, that we cannot choose k+1 elements from A since we assumed that the property holds here. Supposing that you can take k number of elements from A, we are left with only A intersection Q to choose elements from. A intersection Q = {2k+1, 2K+2}

... This is where I'm stuck. If I can prove that some elements (the minimum element?) divides one of these two, then I think I have a contradiction with the supposition, and this, proves the inductive hypothesis (that it is true for (k+1)).

What do you think? Am I on the right track? What do I need to consider to move this forward?

Thank you!

Answer 1

Sorry that I am also not able to continue on your MI proof, but I can provide another proof which may help...

This proof makes use of the Pigeon Hole Principle. I first construct $n$ sets which is a partition of the set $\{1,2,\dots,2n\}$, whicn for all $n$ sets, any two element $a$, $b$ in the same set will have either $a|b$ or $b|a$. Then by PHP it's done. The key is how to construct the partition:

For each even number $2n$ group it up with $n$. If $n$ is still even, further group them up with $\frac n2$. If ......

Let's see an explicit example with the set $\{1,2,\dots,10\}$

$10\to5$
$9$
$8\to4\to2\to1$
$7$
$6\to3$

So we are done. The partition is shown above, one row one set.

We can show that there is exactly $n$ sets in this partition: each set contains exactly one odd number, and there are $n$ odd numbers in the set $\{1,2,\dots,2n\}$.

The divisibility is easy to check: either $a=2^ib$ or $b=2^ia$ for some positive $i$ if $a$ and $b$ belongs to the same set and $a\neq b$. This is an immediate result by the above construction.

So the whole proof finishes.

Hope this helps you! Cheers!

Answer 2

Assume for 2n. A set of cardinality (n+1)+1 from {1,...,2n+2} is a set of cardinality n+2 from {1,...,2n}U{2n+1,2n+2}. If it is an extension (superset) of a set of cardinality n+1 from {1,..,2n} we are done. Thus it is the union of a set of cardinality n from {1,..,2n} with {2n+1,2n+2}.If the set of cardinality n were extended to a set of cardinality n+1 on {1,...,2n} an element would be a proper divisor of another element. In particular if the new element was n+1. But seeing as n+1 cannot properly divide something less than or equal to 2n, n+1 is a multiple of some element of our set. But then so is 2n+2=2(n+1).