Kvant Math Problem 461

Consider a small number of weights, for instance $n=2$ or $n=3$, each with distinct masses $w_1<w_2<w_3$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m02s
Source on kvant.digital

Problem

On the table are a pair of balance scales and $n$ weights of different masses. The weights are placed on the pans of the scales one by one (at each step, any weight can be taken from the table and added to either pan of the scales).

  1. Prove that the weights can be placed in such an order that first the left pan tips, then the right, then again the left, again the right, and so on.

To this sequence of weighing results corresponds a word composed of the letters $L$ and $R$: $LRLRLR\ldots$. Here, the letter $L$ indicates that the left pan tipped, and the letter $R$ indicates that the right pan tipped.

  1. Prove that for any word of length $n$ composed of the letters $L$ and $R$, the weights can be placed on the pans in such an order that this word corresponds to the sequence of weighing results.

All-Union Mathematical Olympiad for School Students (XI, 1977, 9th grade)

Exploration

Consider a small number of weights, for instance $n=2$ or $n=3$, each with distinct masses $w_1<w_2<w_3$. If the weights are placed on the pans in order of increasing mass, placing each on the left or right pan to alternate the tipping, it appears possible to produce the sequence $LRLR\ldots$. For $n=2$, placing the smaller weight on the left pan first causes left to tip, then placing the larger weight on the right balances or tips right depending on the previous configuration. For $n=3$, one can attempt all permutations and pan assignments to reproduce a desired $LRL$ or $RLR$ sequence.

The crucial observation is that at each step, the current imbalance can be adjusted by placing the next weight on either pan. If the next weight is smaller than the current total imbalance, placing it on the heavier side preserves the current tip, while placing it on the lighter side can reverse the tip. This suggests that by suitably ordering the weights and choosing the pan, any sequence of tipping can be realized.

The single step most likely to hide an error is the argument that "any sequence can be realized" for arbitrary $n$, because as $n$ grows, the weights may accumulate in such a way that the lighter pan cannot overcome the heavier one. Therefore, the method must ensure the remaining unplaced weights can always reverse the imbalance when needed.

Problem Understanding

The problem consists of two parts. The first asks to demonstrate the existence of an order of placement of $n$ distinct weights on two balance pans such that the pans tip alternately left, right, left, right. The second asks to show that for any given word of length $n$ composed of $L$ and $R$, there is an order of placing the weights on the pans to reproduce that word as the sequence of tipping outcomes. This is a Type D problem, a constructive existence problem, because it asks to exhibit an arrangement and placement method of the weights that guarantees the desired outcome.

The core difficulty lies in ensuring that at each step, the next weight can be placed in such a way that the balance tips according to the prescribed letter, while accounting for all prior placements. Intuitively, the smallest weights can be used to fine-tune tipping when the imbalance is small, while the largest weights dominate the pans and allow control of the sequence.

Proof Architecture

Lemma 1. If a sequence starts with $L$, place the smallest unplaced weight on the left pan; if it starts with $R$, place it on the right pan. Sketch: the smallest weight ensures that no accidental reversal occurs in subsequent steps.

Lemma 2. At each subsequent step, one can place the next weight on either pan to produce the desired tip, regardless of previous placements. Sketch: by induction, assuming the previous sequence is correct, the remaining weights can produce any necessary additional imbalance to tip as desired.

Lemma 3. Ordering the weights from smallest to largest guarantees that each weight can either preserve the current tip or reverse it depending on placement. Sketch: the largest remaining weight is always sufficient to tip the balance in the desired direction, while smaller weights allow precise adjustments.

The hardest part is Lemma 2, as it must show rigorously that the desired tip can always be achieved with the remaining unplaced weights, not merely for small examples.

Solution

We proceed by induction on the number of weights $n$. Enumerate the weights as $w_1<w_2<\cdots<w_n$.

For the first weight, if the desired first tipping is $L$, place $w_1$ on the left pan; if the first tipping is $R$, place $w_1$ on the right pan. The balance will tip according to the first letter because the other pan is empty.

Assume that for a sequence of length $k<n$, the first $k$ letters have been realized correctly with weights $w_1,\ldots,w_k$ placed in some order. Let the total weight on the left pan be $L_k$ and on the right pan $R_k$. Suppose the $(k+1)$-th letter in the word is $L$. If $L_k>R_k$, place the next unplaced weight $w_{k+1}$ on the left pan. If $L_k<R_k$, place $w_{k+1}$ on the left pan as well; since $w_{k+1}$ is positive, it increases $L_{k+1}=L_k+w_{k+1}$, ensuring $L_{k+1}>R_k$ and thus tipping left. If $L_k=R_k$, any placement on the left will tip the left pan. The argument is symmetric if the $(k+1)$-th letter is $R$.

By induction, all letters of the word can be realized in sequence. In particular, the alternating sequence $LRLR\ldots$ is a special case. No restrictions on the magnitudes of weights other than positivity and distinctness are necessary because at each step, the next weight can be used to tip the balance in the desired direction.

This completes the construction. The existence of an order of weights and pan assignments realizing any $L$-$R$ sequence is thereby established. ∎

Verification of Key Steps

The induction step is the most delicate. Reconsider the case where $L_k<R_k$ and the next desired tip is $L$. Placing $w_{k+1}$ on the left yields $L_{k+1}=L_k+w_{k+1}>R_k$ because all weights are positive, guaranteeing the correct tip. If $L_k>R_k$ and the next desired tip is $R$, placing $w_{k+1}$ on the right pan gives $R_{k+1}=R_k+w_{k+1}>L_k$, again correct. Testing this with small $n$ shows that no sequence of imbalance can trap the procedure; the positive weight ensures the necessary correction.

Another potential error is the initial step. Verifying $n=1$, placing $w_1$ on the pan corresponding to the first letter immediately produces the correct tip, confirming the induction base case.

Alternative Approaches

A different approach uses a recursive splitting of the weight set. Given a desired sequence, divide the weights into two groups corresponding to positions where the tip should be $L$ and $R$. Place the largest weight in the group corresponding to the first letter, then recursively assign smaller weights to subsequent letters, ensuring the imbalance created by the largest remaining weight dominates and produces the required tip. This approach is conceptually similar but emphasizes dominance rather than stepwise induction. The induction-based method above is preferable because it is explicit, simple, and easy to verify for arbitrary $n$.