retagged by
319 views
3 votes
3 votes

Let $\text{S} = \{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21\}.$ What is the possible value of integer $\text{N} > 0$ such that for any set of $\text{N}$ integers, chosen from $\text{S},$ there must be two distinct integers such that one of them divides the other?

  1. $10$
  2. $7$
  3. $9$
  4. $8$
retagged by

2 Answers

3 votes
3 votes
Lets try to build the largest set in which no 2 numbers are divisible by one another

What i can do is add all primes to the list and exclude 1 because 1 divides every number(and of course it's not prime)

so I Get {3,5,7,11,13,17,19} NOW FROM remaining elements that are 1,9,15 and 21 . as soon as you add anything from these numbers to the set , 2numbers get divisible

 

hence least size required is 7+1=8
edited by
2 votes
2 votes
Select all prime numbers , that is $7$ prime numbers. Then if you select one more number then we will get at least one pair of elements which divide each other. So, $8$ is the minimum possible answer. Hence, anything $\geq 8$ is answer.
Answer:

Related questions

4 votes
4 votes
3 answers
3
5 votes
5 votes
3 answers
4