Pigeon hole

Question

Answer 1

for natural numbers k and m, if n = km + 1 objects are distributed among m sets, then the pigeonhole principle asserts that at least one of the sets will contain at least k + 1 objects 

So now n is 25 and I want to divide it into two sets one set which doesn't have any multiples and other set which has multiples 

So now I will get k as 25-1/2=12

From this one set must contain atleast k+1 that is 12+1=13 elements 

So this 13 elements can be of both the sets . . But in the question it was asked about minimum so 13 will be the elements of not having multiples but by adding one more element we can have multiples so minimum will be 13+1=14 is the answer 

Answer 2

given are 1 to 25 numbers.
25/2 = 12.5
12*2=24 and 13*2=26
between 13 and 25 you can find no pair of multiples. bcoz, multilying 13 by 2 itself is crossing 25. so there can be no two elements which are multiples between 13 ad 25.
this could be the worst set taken.13 to 25 are 13 numbers and no element is multiple of other. add 12 into the set. we can get exactly 1 pair of multiples 12 and 24.
so the worst case set you could take is 12 to 25. which contains 14 elements.
so minimum k value is 14

Answer 3

Min number of elements in set = 10

Let P be the required min set satisfying the condition.

In worst case, first pick all elements which make condition false => pick all primes.

P = {2,3,5,7,11,13,17,19,23}, |P| =9

Remaining = {1,4,6,8,9,10,12,14,15,16,18,20,21,22,24,25}

Pick any one element from remaining, and add to P. This will satisfy the condition that atleast one element in P is a multiple of another element of P.

=> min |P| = 9 + 1 =10.

Comments

this can be the set

{4,6,9,10,11,13,14,15,17,19,21,23,25} these are 13 elements without there multiples so ans will 14 if iadd one more element it will be the multiple