Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$
share|cite|improve this question
Question 2. at least has been asked several times on this site before: see e.g.…, 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
up vote 2 down vote accepted
  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

share|cite|improve this answer

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.

share|cite|improve this answer
  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$.
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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