1
$\begingroup$

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$
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Pete L. Clark May 10 '13 at 14:49
  • $\begingroup$ 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.) $\endgroup$ – Pete L. Clark May 10 '13 at 14:50
2
$\begingroup$
  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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But those aren't the only 2-element subsets of $\{1,2,...,2n\}$ are they? They partition the set into n subsets, but what if there was another way to partition the set such that we obtained $\geq n$ subsets? Grouping prime numbers would result in a smaller subset, but I can't think of any other way. This is where I get hung up on this problem. $\endgroup$ – alwaysiamcaesar Dec 8 '18 at 20:34
0
$\begingroup$
  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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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