Combinatorics

Question

Among the integers $1,2,3,....,200$ if $101$ integers are chosen,then show that there are two among the chosen,such that one is divisible by the other.

Comments

Refer this
https://youtu.be/Eick163K5Eo
Skip to 17:20

---

We can easily prove this

See, among 1 to 100

Only 25 prime numbers

among 1 to 200 , there are 63 prime numbers

 All others non prime

So, there must be some numbers divisible by others

Answer 1

Any number n can be factorised as 2^k *m.

Here m is an odd number because all the 2's in the factors of n is in 2^k.

Now,since we are selecting the numbers from {1,2,3,....,200}

So, m can take value in {1,3,5,...,199}

Hence,there are 100 values for m.

Now, we are picking 101 integers from {1,2,...,200}

So, by pigonhole principle we get there exist at least two numbers from the picked numbers such that 

m is equal in both the numbers.

Let, the two numbers be k₁ and k₂

Then k₁ = 2^p * m

and k₂ = 2^q * m

Hence k1/k2 = 2^p-q

if p<=q then k₂ divides k₁ otherwise k₁ divides k₂

So, among the chosen 101 integers there must exist at least two integers such that one is divisible by the other.