# About the Pigeonhole principle

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$
-
Question 2. at least has been asked several times on this site before: see e.g. math.stackexchange.com/questions/49080/…, where my answer gives a little history of the problem and mentions that it is often asked along with 1. (But I don't give the answer to 1. there.) Can someone find 1. also previously answered on this site? – Pete L. Clark May 10 '13 at 14:49
Also I don't like the way the conditions are stated: at first glance it looks like we want $a$ and $b$ to satisfy both of them. (Of course the two conditions imply $a = 1$ so that will not be possible.) – Pete L. Clark May 10 '13 at 14:50

## 3 Answers

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

-

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.

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