Kvant Math Problem 212

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m03s
Source on kvant.digital

Problem

At a trial, 14 coins are presented as physical evidence. An expert has determined that seven of them are counterfeit and the remaining seven are genuine, and moreover has identified exactly which coins are counterfeit and which are genuine. The court knows only that all counterfeit coins have the same weight, all genuine coins have the same weight, and that counterfeit coins are lighter than genuine ones. Using three weighings on a balance scale without weights, the expert wants to prove to the court that all the coins he identified as counterfeit are indeed counterfeit, and that the others are genuine. Can he do this?

R. V. Freivald

All-Union Mathematical Olympiad for School Students (VII, Grades 8 and 9)

Exploration

We are asked whether an expert can convince the court, using only three weighings on a balance scale, that exactly seven out of fourteen coins are counterfeit. A natural starting point is to consider smaller numbers. For instance, with two or four coins where half are fake, one can balance subsets to reveal differences. The challenge arises because the court knows nothing about which coins are counterfeit or genuine, only that all counterfeit coins are lighter. Thus each weighing must convey unambiguous information, and the total information must suffice to identify all seven counterfeit coins. Each weighing of two sets of coins partitions the universe of possibilities into three outcomes: left heavier, right heavier, or balanced. Therefore three weighings produce at most $3^3 = 27$ distinguishable outcomes. We need to distinguish all $\binom{14}{7} = 3432$ possible assignments of seven counterfeit coins. Since $27 \ll 3432$, it is immediately clear that no set of weighings can uniquely identify the counterfeit coins without additional structure. This suggests that proving the expert's knowledge is correct in three weighings is impossible if the court begins with no prior information. The crucial point is to compare the number of possible outcomes with the number of configurations to be distinguished.

Problem Understanding

The problem asks whether the expert can demonstrate the authenticity of his classification of 14 coins, seven genuine and seven counterfeit, using exactly three weighings on a balance scale. This is a Type B problem, as it asks to prove or disprove the possibility of an action rather than to find all solutions or extremal values. The core difficulty lies in assessing whether three weighings carry enough information to unambiguously prove which coins are counterfeit. Intuitively, since a balance scale produces three outcomes per weighing, three weighings yield only $27$ possible sequences of outcomes, while the court must distinguish between $3432$ possible arrangements of coins into genuine and counterfeit. The disparity suggests that the expert cannot convince the court in only three weighings.

Proof Architecture

Lemma 1: Each weighing on a balance scale yields exactly three possible outcomes. This is true by definition: left pan heavier, right pan heavier, or balance.

Lemma 2: Three weighings produce at most $3^3 = 27$ distinct sequences of outcomes. This follows from Lemma 1 by combinatorial multiplication of independent events.

Lemma 3: There are $\binom{14}{7} = 3432$ possible ways to choose seven counterfeit coins among fourteen. This is a standard combinatorial count.

Lemma 4: If the number of distinct outcomes is smaller than the number of configurations to distinguish, it is impossible to unambiguously identify the configuration. This follows from the pigeonhole principle: at least two configurations would produce the same sequence of outcomes.

The hardest step is Lemma 4, as it requires carefully connecting the information-theoretic limitation of the scale to the impossibility of proving the classification.

Solution

Each weighing of a subset of coins on a balance scale without weights produces exactly three outcomes: either the left pan is heavier, the right pan is heavier, or the pans are equal in weight. Therefore, with three weighings, the expert can produce at most $3 \cdot 3 \cdot 3 = 27$ distinct sequences of outcomes.

The court, knowing nothing about which coins are genuine or counterfeit, must distinguish all $\binom{14}{7}$ possible selections of seven counterfeit coins among fourteen, which is

$\binom{14}{7} = \frac{14!}{7! \cdot 7!} = \frac{87178291200}{5040 \cdot 5040} = 3432.$

Since $3432 > 27$, the total number of possible outcome sequences from three weighings is far smaller than the number of arrangements to distinguish. By the pigeonhole principle, at least two distinct configurations of counterfeit coins would lead to identical sequences of weighings, making it impossible for the court to verify which configuration is correct.

Therefore, no strategy using only three weighings can prove to the court the correctness of the expert's classification. This completes the proof.

∎

Verification of Key Steps

The count $\binom{14}{7} = 3432$ was verified by stepwise computation: $14! = 87178291200$, $7! = 5040$, then $14! / (7! \cdot 7!) = 87178291200 / 25401600 = 3432$, confirming the combinatorial magnitude. The information-theoretic step also holds: $3^3 = 27$ outcomes from three weighings is indeed much smaller than 3432, so the impossibility follows rigorously. No assumptions about the arrangement of coins were made beyond the definition of the scale's outcomes.

Alternative Approaches

One could attempt a direct construction strategy, trying to design weighings that encode subsets of coins to uniquely identify the seven counterfeit coins. However, any such construction fails because the number of outcomes cannot exceed 27, which is insufficient to encode 3432 possibilities. The information-theoretic argument is simpler and fully conclusive, avoiding the need to consider specific weighing arrangements, and thus is the preferred approach.