Given n1 natural numbers say a1a2an1 all less than or equal

Given n+1 natural numbers, say a₁,a₂,...,a_n+1, all less than or equal to 2n, then there exists a pair, say a_i and a_j with i does not equal j, such that a_i|a_j.

Solution

This problem is based on the concept of Pigeon Hole Principle

Let us pick (n-1) odd numbers i.e. (3,5,7,9,11,...,2n-1)

Now we need to pick two numbers, let us pick 2

(2,3,5,7,9,11,....,2n-1)

Now we need to choose from 1 or any even number greater than 2 or less than equal to 2n

If we choose 1, then it will divide all the elements in the set

If we choose an even number greater than 2 or less than or equal to 2n, then it will be divisible by 2

Hence there will be atleast one pair (ai,aj) where ai divides aj

There are n+1 pigeons and n pigeon holes, hence there will be atleast one hole containing 2 pigeons.

Hence by using pigeon hole principle, we ca prove that there exists a pair, say a_i and a_j with i does not equal j, such that a_i|a_j.