1
$\begingroup$

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$

$\endgroup$
7
  • 1
    $\begingroup$ Hint: for $n = 10$ your method gives $4$ numbers (2,3,5,7), but it's possible to get 5. $\endgroup$
    – mihaild
    Jun 29, 2023 at 14:03
  • 4
    $\begingroup$ Hint : for $n=15$, you can take $8,9,10,11,12,13,14,15$, which is better. Can you generalize this argument ? $\endgroup$ Jun 29, 2023 at 14:03
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 29, 2023 at 14:08
  • $\begingroup$ @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. $\endgroup$ Jun 29, 2023 at 14:10
  • $\begingroup$ @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$. $\endgroup$ Jun 29, 2023 at 14:30

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

How is k=305? take numbers from 1701 to 2005. None of them are divisible by any other since 1701*2 > 2005. k is at least 1004, any lesser k would fail in the 2005-k+1 to 2005 range. Assume that you had 1004 numbers, divide multiples of two by the maximal power of two. Now you have 1004 odd numbers. There are 1003 odd numbers from 1 to 2005. Thus there exist a pair in your original number selection with the property that two numbers making up the pair have identical odd parts implying that one of them is divisible by the other.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .