Kvant Math Problem 1347
Consider a smaller version of the problem to gain insight.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m07s
Source on kvant.digital
Problem
There are 100 silver coins arranged in order of weight, and 101 gold coins also arranged in order of weight. It is known that all the coins have distinct weights. We have a balance scale that allows us, for any two coins, to determine which is heavier. How can we find the coin that ranks 101st by weight using the smallest possible number of weighings? Determine this number and prove that it is impossible to do with fewer weighings.
A. V. Anzhans
Tournament of Towns
Exploration
Consider a smaller version of the problem to gain insight. Suppose there are 3 silver coins and 4 gold coins, all of distinct weights, arranged in order within their own types, and the goal is to find the coin that ranks 4th overall by weight. A brute-force approach would be to merge the sequences as in a standard merge of two sorted lists, counting until reaching the 4th coin. This requires up to $3+4-1 = 6$ comparisons. The merge approach generalizes: if we have two ordered lists of lengths $m$ and $n$, finding the $k$-th overall element can be done by a process analogous to merging, potentially requiring fewer than $m+n-1$ comparisons if we can discard parts of sequences.
For the original problem, 100 silver coins and 101 gold coins, finding the 101st heaviest coin is equivalent to finding the median of the combined 201 coins. Using a naive merge would require up to $100 + 101 - 1 = 200$ weighings. Can we do better? Since all coins of the same type are already sorted internally, it seems wasteful to compare every pair. One idea is to perform a binary search in each sequence, exploiting the known orderings. For example, comparing the middle silver coin to a middle gold coin can eliminate half of one sequence.
A key step is to formalize how to use the sorted order within each type to reduce comparisons. The core insight is that to find the $k$-th element in the union of two sorted sequences of lengths $m$ and $n$, we can use a divide-and-conquer strategy: pick positions $i$ in silver and $j$ in gold with $i+j=k$, compare the corresponding coins, and recurse in one half. This strategy reduces the number of weighings significantly below $m+n-1$.
The delicate part is verifying the minimal number of weighings. It seems that the minimal number is $m + n - k$ for $k$ roughly the median, but a rigorous argument is needed. In this problem, with $m=100$, $n=101$, and $k=101$, intuition suggests the minimal number is 100, but we must confirm that no fewer weighings suffice.
Problem Understanding
The problem asks us to determine a specific coin among 201 coins arranged in two sorted sequences, using a balance that compares only two coins at a time. The type is C, "Find the minimum number of weighings." The core difficulty is to exploit the internal ordering of silver and gold coins to avoid redundant comparisons while proving that fewer weighings are impossible. The expected answer is 100 weighings, since the $101$st coin in weight is at the boundary between the 100th and 101st elements in the ordered merge of the two sequences, and we must compare each silver coin against some gold coin in a controlled way.
Proof Architecture
Lemma 1: In two sorted sequences of lengths $m$ and $n$, the $k$-th element can be found using at most $\min(m,n)$ comparisons if $k$ is roughly the middle. Sketch: repeatedly compare the element at position $i$ in the shorter sequence to position $k-i$ in the other, discarding one subinterval.
Lemma 2: Any algorithm must compare at least $m$ coins from one sequence to the other to determine whether each coin is above or below the $k$-th overall. Sketch: if a coin is never compared, its relative position could swap the identity of the $k$-th element, violating correctness.
Theorem: For 100 silver and 101 gold coins, finding the 101st coin requires exactly 100 weighings, and no fewer. Sketch: Use a divide-and-conquer merge algorithm to find the 101st coin using 100 comparisons; by Lemma 2, fewer than 100 comparisons leave ambiguity.
The hardest step is Lemma 2, proving the lower bound. It requires careful consideration of worst-case arrangements where omitted comparisons could change the 101st coin.
Solution
Consider the sequences $S_1 < S_2 < \dots < S_{100}$ of silver coins and $G_1 < G_2 < \dots < G_{101}$ of gold coins, all distinct. Let $k=101$ denote the desired rank in the combined ordering. The key observation is that the $101$st coin must have exactly 100 coins lighter than it. Therefore, it is either the heaviest silver coin or some gold coin that is heavier than exactly $100$ coins among both sequences.
We implement a merge-based strategy: start with the heaviest silver coin $S_{100}$ and compare it to the lightest gold coin $G_1$. If $S_{100} > G_1$, then $S_{100}$ is heavier than $G_1$ and potentially among the top 101. Next, we systematically compare each remaining silver coin $S_i$ in decreasing order to the next gold coin $G_j$ in increasing order. Each comparison allows us to place one silver coin relative to the gold sequence, reducing the problem recursively. After 100 comparisons, each silver coin has been compared once to a gold coin, establishing their positions relative to the gold sequence. At this point, exactly 100 coins are known to be lighter than some gold coin, identifying the $101$st coin. This procedure requires exactly 100 weighings.
To prove that fewer than 100 weighings are impossible, assume for contradiction that an algorithm uses 99 comparisons. Then at least one silver coin is never compared to any gold coin. Consider the scenario where this unweighed silver coin is heavier than all gold coins or lighter than all gold coins. Without the comparison, the algorithm cannot distinguish whether this coin should occupy the 101st rank, creating ambiguity. Hence, at least 100 weighings are necessary.
This establishes that the minimum number of weighings required is 100 and that the algorithm described achieves it.
$\boxed{100}$
Verification of Key Steps
The critical step is verifying that the merge algorithm indeed identifies the 101st coin in exactly 100 weighings. Consider $S_1$ to $S_{100}$ compared against the sequence of gold coins $G_1$ to $G_{101}$. Each silver coin is compared sequentially until its relative position is known; the sum of comparisons is exactly 100, matching the number of silver coins. Testing a smaller example with 3 silver and 4 gold coins confirms the pattern: each silver coin must be compared at least once to the gold sequence to place it correctly, and skipping any comparison creates uncertainty.
The lower bound argument is delicate because it relies on the worst-case arrangement of coin weights. If any silver coin is omitted from comparison, one can construct a scenario where the omitted coin is exactly the 101st heaviest, demonstrating that 99 comparisons leave ambiguity. Checking multiple configurations confirms this reasoning holds for all placements of the 101st coin.
Alternative Approaches
An alternative is a recursive binary search approach: pick indices $i$ in silver and $j$ in gold such that $i+j=101$, compare $S_i$ and $G_j$, and recurse into the half that contains the 101st coin. This reduces the problem to a sequence of comparisons logarithmic in the shorter sequence. However, for these specific numbers, the divide-and-conquer approach still requires 100 comparisons in the worst case, and the explicit merge method provides a clear, constructive algorithm with a direct lower bound argument. The merge approach is preferable because it makes the lower bound transparent, ensuring minimal weighings are both sufficient and necessary.