Pigeon hole principle with a set of $50$ integers

Question

Suppose that $26$ integers are chosen from the set $S=\{1,2,\ldots,50\}$.
By writing these numbers as $2^k m$ with $m$ odd, prove that one of the chosen numbers is a multiple of another of the chosen numbers.

I'm not sure how to set pigeons and pigeonholes here. So this is my attempt

The case with a repeated integer is trivial as each integer divides itself. So assume the integers are distinct. There are $\binom{50}{26}$ sets that have $26$ distinct integers.
Now, if the integer is odd, then $k=0$. If the integer is a power of $2$, then $m=1$. Also, if the integer is prime, then $k=0$.
However, I'm not sure what to do now

"if the integer is odd, then k=1." A doubt, if an integer is odd then it should not have 2 as a factor right? So how can k=1? — shwetha, Nov 10 '17 at 06:17
Ah I see, there will be $25$ of possible $m$I was stuck on just counting the number of primes... — Natash1, Nov 10 '17 at 06:53

score 2 · Accepted Answer · answered Nov 10 '17 at 06:11

The $25$ holes are the odd integers $1,3,\ldots,49$. The $26$ pigeons are the selected integers, written with all powers of $2$ factored out, as you noted.

Two of those pigeons must be $2^km$ and $2^jm$ for the same $m$. Suppose $k\ge j$; then the first of these two pigeons is a multiple of the second.

Pigeon hole principle with a set of $50$ integers

1 Answers1