Prove that if any 14 integers from 1 to 25 are chosen then o

Prove that if any 14 integers from 1 to 25 are chosen, then one of them is a multiple of another.

Dear Student

Thank you for using Chegg !!

If we create 13 pigeon holes in such a way that each numberchosen can be assigned to only 1 igeon hole.

and when the number x and y are assigned to same pigeonhole,it is guranteed that either x divides y or y divides x.

There are 9 prime numebrs between 1 to 25, but knowing that x and y are multiples of the same prime will not guarantee that either x divides y or y divides x.

So the proof will be as follows

There are 13 odd numbers between 1 and 25. But we can write every positive integer n as n = m*2^k.

where m is odd and k>0

Now label the pigeon holes,with 1,3,5..25.the odd numbers between 1 to 25.

Assign each of the selected 14 numbers to the pigeon holes labeled with its odd part.

But there are only 13 pigeonholes.

So by pigeonhole principle, two of them must have the same odd part.

Let us assume n1 n1 and n2 have the same odd part. So n1 = m*2^(k1) and n2 = m*2^k2.

for some k1 and k2.

If k1> k2

then n1 is multiple of n2 other wise n2 is a multiple of n1

Prove that if any 14 integers from 1 to 25 are chosen, then one of them is a multiple of another.SolutionDear Student Thank you for using Chegg !! If we create

Prove that if any 14 integers from 1 to 25 are chosen then o

Solution

Get Help Now

Submit a Take Down Notice