Kvant Math Problem 192
Consider small analogues first.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m55s
Source on kvant.digital
Problem
The numbers 1, 2, 3, ..., 1000 are given. Find the greatest $m$ with the following property: no matter which $m$ of the given numbers are crossed out, among the remaining $1000-m$ numbers there will be two such that one is divisible by the other.
Exploration
Consider small analogues first. For numbers $1$ through $8$, we want the largest $m$ such that, after deleting any $m$ numbers, the remaining numbers always contain two where one divides the other. Listing the numbers and considering powers of two, the odd numbers, and their multiples may suggest a pattern. Noticing that sequences where no number divides another are sets of numbers with distinct largest odd factors is promising. For instance, ${5, 6, 7, 8}$ has $6$ divisible by $3$, $8$ divisible by $4$, but ${5, 7}$ has no divisibility among them. In general, numbers with distinct largest odd divisors form sets free of mutual divisibility. Thus, the problem reduces to understanding these largest odd divisors and how many numbers can be simultaneously deleted to avoid the divisibility condition.
Testing a few examples: for numbers $1$ through $8$, the sets of numbers with distinct largest odd divisors are ${1,2,4,8}$ (largest odd $1$), ${3,6}$ (largest odd $3$), ${5}$ (largest odd $5$), ${7}$ (largest odd $7$). The largest set without internal divisibility is formed by picking one number per largest odd factor, giving size $4$. Therefore, removing up to $4$ numbers may avoid forcing a divisibility pair, but removing more leaves some forced pair. The key is understanding how to count numbers grouped by largest odd divisor.
Problem Understanding
We are given integers $1$ through $1000$ and seek the largest integer $m$ such that, no matter which $m$ numbers are removed, the remaining numbers always contain two numbers where one divides the other. This is a Type C problem because we are asked to find the maximal number $m$ with a specified extremal property.
The core difficulty lies in characterizing the sets of numbers where no number divides another, which will dictate how many numbers can be deleted without violating the divisibility condition. The main insight is that numbers sharing the same largest odd factor are linearly ordered by powers of two, so picking one number per largest odd factor avoids divisibility, while any more deletions force divisibility among remaining numbers.
Intuitively, the answer should be the number of integers minus the size of the largest set without internal divisibility. This set is exactly the collection of numbers obtained by choosing the maximal number for each largest odd factor, which partitions the integers from $1$ to $1000$.
Proof Architecture
Lemma 1: Every positive integer $n$ can be uniquely written as $n = 2^k \cdot t$ with $t$ odd and $k \ge 0$; $t$ is the largest odd divisor of $n$. This is standard from the fundamental theorem of arithmetic.
Lemma 2: In any set of numbers with the same largest odd divisor, one number divides another. This follows because numbers with the same largest odd divisor are exactly powers of two times that odd number, forming a chain under divisibility.
Lemma 3: Any set of numbers containing at most one number per largest odd divisor has no divisibility among its elements. This is a contrapositive of Lemma 2.
Lemma 4: The maximum number of numbers that can be selected without having a divisibility pair is equal to the number of odd numbers up to $1000$. This is because each odd number gives one distinct largest odd divisor, and selecting one number per largest odd factor produces a maximal set avoiding divisibility.
Lemma 5: The largest $m$ such that deleting $m$ numbers still leaves a forced divisibility pair is $1000$ minus the maximum size of a set with no divisibility, i.e., $1000 - 500 = 500$.
The hardest step is Lemma 4, which requires counting all odd numbers up to $1000$ and ensuring that any additional number necessarily introduces a divisibility pair.
Solution
Every integer $n$ from $1$ to $1000$ can be written uniquely as $n = 2^k \cdot t$ with $t$ odd. Define $t$ as the largest odd divisor of $n$. Numbers with the same largest odd divisor $t$ are of the form $t, 2t, 4t, \dots, 2^k t$, and these numbers form a chain under divisibility because $2^i t$ divides $2^j t$ whenever $i \le j$. Therefore, any set containing two numbers with the same largest odd divisor contains a divisibility pair.
Consider sets avoiding internal divisibility. By Lemma 3, such a set contains at most one number per largest odd divisor. The largest possible such set contains exactly one number for each odd number $t$ between $1$ and $1000$. The number of odd integers from $1$ to $1000$ is $\lceil 1000/2 \rceil = 500$. Hence, the maximal size of a set of numbers with no internal divisibility is $500$.
Now consider deleting numbers. If we delete $m$ numbers and wish to avoid leaving a divisibility pair, the remaining $1000 - m$ numbers must form a set with no divisibility. Since the largest such set has size $500$, it follows that $1000 - m \le 500$, so $m \ge 500$. Therefore, the largest $m$ such that, after deleting any $m$ numbers, the remaining numbers always contain a divisibility pair is $m = 500$.
Hence the answer is
$\boxed{500}.$
Verification of Key Steps
The critical step is counting the size of the maximal set without divisibility. The set formed by picking exactly one number per largest odd divisor is of size $500$, as there are $500$ odd numbers from $1$ to $1000$. Testing small examples, such as $1$ through $8$, confirms that choosing numbers ${1,3,5,7}$ produces a maximal set with no divisibility pair, matching the method used for $1000$. Additionally, the argument that numbers sharing the same largest odd factor form a divisibility chain holds for small examples, such as $2,4,8$ (largest odd $1$) and $6,3$ (largest odd $3$), verifying the key structural insight.
Alternative Approaches
An alternative approach is to consider the Hasse diagram of numbers $1$ through $1000$ ordered by divisibility and to apply Sperner's theorem. In this approach, the maximal antichain corresponds to the maximal set of numbers with no divisibility relation. The size of the maximal antichain coincides with the number of numbers with distinct largest odd divisors. This method is equivalent in result but less elementary, relying on lattice theory. The direct approach using largest odd divisors is preferable because it is constructive, simple, and yields an explicit maximal set.