Skip to main content
OlympiadHQ

Browse · MathNet

Print

Argentina_2018

Argentina 2018 counting and probability

Problem

Given are 16 balls with weights , , , , grams. Determine the balls with weights , , , grams, by using a two-pan balance at most times.
Solution
One can find the lightest ball via direct elimination by pairs: we make pairs and determine the lightest on each pair, now we make pairs and determine the lightest on each pair, then we select the two lightest and finally, the ball with the minimum weight. This takes attempts. Ball is among the ones eliminated by ball in the process. There are of them; is the lightest one, and it can be found by direct elimination again with attempts.

Observe now that is the only ball heavier than and combined. Likewise is the only ball with the same weight as and combined. In addition, ball is among the eight losers in the first eight uses of the balance. Let them be . (It could be less if was eliminated by in the first eight uses of the balance.)

For each compare ball with the group , . One of these eight attempts will find ball . If there is equilibrium at one of the seven remaining attempts, ball is found too. Otherwise is a winner in the first round, which is possible only if it was compared with at the first round. Therefore, because is already known, so is also ; no further attempts are needed. The task is solved with attempts.

Techniques

Games / greedy algorithmsAlgorithms