# From the first $2005$ natural numbers, $k$ of them are arbitrarily chosen.

From the first $$2005$$ natural numbers, $$k$$ of them are arbitrarily chosen.

What is the least value of $$k$$ to ensure that there are at least one pair of numbers such that one of them is divisible by the other?

I tried to get a feel of the question by reducing $$2005$$ to $$15$$. Then, if I select the numbers $$2, 3, 5, 7, 11$$ and $$13$$, which are all primes, I will get a set of numbers of which no pair can be formed containing a number divisible by another. Now if I select any other non-prime number from the set $$\left[1,2,...15\right]$$, and add it to the set of primes which I originally selected, I will get at least one pair where a number is divisible by another (the newly added number will be divisible by one of the primes). So basically, we get a result that the least value of $$k=N_{p}+1$$ (here $$k=7$$), where $$N_{p}$$ represents the number of primes from $$1$$ to $$n$$, both inclusive (do let me know if there is any flaw in my reasoning).

Now if I extend this reasoning to the first $$2005$$ natural numbers, I will get $$k=N_{p}+1$$. Calculating $$N_{p}$$ for numbers from $$1$$ to $$2005$$ without a program seems a daunting task, and it is humanly impossible to do this during an Olympiad exam by brute force (I sourced this question from a previous Olympiad). Could someone help me in the method of finding $$N_{p}$$ for such large numbers? Also, could you please tell me if this would be the correct answer? (Don't reveal without trying to solve)

$$k=305$$

Thanks a lot!

Edit: If we take the original set of $$\left[1,2,...15\right]$$, and we select $$k=7$$ numbers from this set, we should get at least a pair of numbers in which one divides another. But if we take the numbers $$9, 10, 11, 12, 13, 14$$ and $$15$$; we see that none of them divides another. The least $$k$$ in this case is $$9$$, i.e. our set contains $$7, 8, 9, 10, 11, 12, 13, 14, 15$$. I tested this value on other relatively small values for natural numbers other than $$15$$, such as $$10$$, $$25$$ and $$6$$. In each case, $$k=\lfloor\frac{n}{2}\rfloor+1$$ for even $$n$$ and $$k=\lfloor\frac{n}{2}\rfloor+2$$ for odd $$n$$. Could anyone explain to me why does this rationale hold?

If it does hold for larger numbers, then my new answer for $$k$$ when $$n=2005$$ would be:

$$k=1004$$

• Hint: for $n = 10$ your method gives $4$ numbers (2,3,5,7), but it's possible to get 5. Jun 29, 2023 at 14:03
• Hint : for $n=15$, you can take $8,9,10,11,12,13,14,15$, which is better. Can you generalize this argument ? Jun 29, 2023 at 14:03
• The question is not asking for a particular smallest set that cannot be extended without giving divisors, it is asking for the smallest k for which ALL sets with k elements have divisors. In a sense you are not looking for the best case but for the worst case. Jun 29, 2023 at 14:08
• @JaapScherphuis Yes, but obviously, finding a set whose elements don't divide each other can give a minoration of the number $k$... So finding such a family is a very natural first step. Jun 29, 2023 at 14:10
• @mihaild Exactly. $k=4+1$, $N_{p}$ in your case is $4$, which makes $k=5$. I guess you missed the part where I stated the following: Now if I select any other non-prime number from the set [1,2,...15], and add it to the set of primes which I originally selected, I will get at least one pair where a number is divisible by another (the newly added number will be divisible by one of the primes). So basically, we get a result that the least value of $k=N_{p}$ $+1$. Jun 29, 2023 at 14:30

First, let's consider the numbers $$1003$$, $$1004$$, $$1005$$, ..., $$2005$$. Among these $$1003$$ numbers, there is no pair of number such that one divides the other. So $$k > 1003$$.
Let's prove that $$k=1004$$ works. We consider $$\lbrace a_1, a_2, ..., a_{1004} \rbrace$$ a family of $$1004$$ distinct natural numbers between $$1$$ and $$2005$$.
For each $$i=1, ..., 1004$$, let's write $$a_i = 2^{k_i} m_i$$, with $$k_i \in \mathbb{N}$$ and $$m_i$$ is an odd integer between $$1$$ and $$2005$$. Since there are $$1003$$ odd numbers between $$1$$ and $$2005$$, by the pigeonhole principle, there exists $$i \neq j$$ such that $$m_i=m_j$$.
Then if you consider the pair $$(a_i, a_j)$$, one has $$a_i=2^{k_i}m_i$$ and $$a_j = 2^{k_j}m_i$$, so one of these numbers divide the other.