About the Pigeonhole principle

Question

The principle says that: Let $k$ and $n$ be any two positive integers. If at least $kn+1$ objects are distributed among $n$ boxes, then one of the boxes must containat least $k+1$ objects. In particular, if at least $n+1$ objects are to be put into $n$ boxes, then one of the boxes contain at least two objects.

Then I have to use the Pigeonhole principle to prove that all $(n+1)$-subset of $\{1,2,3,\ldots,2n-1,2n\}$ have at least two elements $a,b$ such that:

1. $a\mid b$
2. $\gcd(a,b)=1$

Answer 1

1. For each of the $n$ odd numbers $k\le 2n$, make a box consisting of $k, 2k, 4k,8k, \ldots$ (i.e. numbers of the form $k2^j$).

2. Make $n$ boxes from pairs of consecutive numbers

Answer 2

For the gcd, pair the numbers together into "boxes" of the form $\{i,i+1\}$. There are $n$ such "boxes", so at least one such pair has both numbers in the $(n+1)$-subset we chose. Hence these two satisfy the required property.

Answer 3

1. Any integer can be written in the form $2^{k}*x$ where $k\geq0$ and $x$ is odd. For number $x$ among $2n$ consecutive numbers in this set you have $n$ possibilities. So if you choose $n+1$ numbers from that according to pigeonhole principle you must have at least two of them with same factor $x$. If we have $a=2^{k}*x$ and $a=2^{l}*x$, for $k< l$ $a|b$, and for $k> l$ $b|a$.