Browse · MathNet
Print55rd Ukrainian National Mathematical Olympiad - Third Round
Ukraine counting and probability
Problem
There are 9 weights with labels g, g, , g respectively. It's known that one of the weights is lighter than the label says, while the other eight labels are correct. Is it possible to detect the counterfeit weight using scales with no additional weights no more than twice?
Solution
At the first move, put on the left side and on the right side. If the total weights are equal, the counterfeit weight is among the other three. Then put on scales the combinations and .
If , they are genuine, hence, is counterfeit.
If , then is counterfeit, because it is lighter and is known to be genuine. * Similarly, would imply that is counterfeit.
If the total weights at the first weighing are not equal, the counterfeit weight is among the three lighter ones. The second move involves putting one potentially counterfeit weight on each side and balancing them with genuine ones. For example, and . Then we use the same arguments: the counterfeit one is where the total weight is less. If the scales are balanced, the unused weight is counterfeit.
If , they are genuine, hence, is counterfeit.
If , then is counterfeit, because it is lighter and is known to be genuine. * Similarly, would imply that is counterfeit.
If the total weights at the first weighing are not equal, the counterfeit weight is among the three lighter ones. The second move involves putting one potentially counterfeit weight on each side and balancing them with genuine ones. For example, and . Then we use the same arguments: the counterfeit one is where the total weight is less. If the scales are balanced, the unused weight is counterfeit.
Final answer
Yes
Techniques
Algorithms