Olympiad Maths Prep

Track / Stage 5 / 106 of 400 #706 of 2000

Problem 706

AIME late
Combinatorics Difficulty 5.3 Find the answer

Three, (50 points) There are 12 balls, all identical in color and size, but one of them is defective in weight, though it is unknown whether this ball is heavier or lighter than the standard. Can the defective ball be identified using a balance scale in just three weighings (without using weights)?

Can the defective ball be found using a balance scale in just three weighings (without using weights)?

Official solution

Three, number 12 balls as 1,2,,121,2, \cdots, 12, then the following weighing method can be designed:
\begin{tabular}{ccc}
& Left Pan & Right Pan \\
First Time & 1,5,6,121,5,6,12 & 2,3,7,112,3,7,11 \\
Second Time & 2,4,6,102,4,6,10 & 1,3,8,121,3,8,12 \\
Third Time & 3,4,5,113,4,5,11 & 1,2,9,101,2,9,10
\end{tabular}

Each weighing can result in three outcomes: balanced, left heavy, or right heavy. Combined, there are 27 possible outcomes, but the result of balanced, balanced, balanced will not occur, as it contradicts the problem statement.

Similarly, the results of left heavy, left heavy, left heavy, and right heavy, right heavy, right heavy will not occur, because in our weighing design, no single ball is placed on the same side (left or right) all three times. Therefore, in the case of only one defective ball, the above results will not appear.

Among the remaining 24 possible outcomes, each pair of results can determine which ball is defective and whether it is heavier or lighter. For example, if the weighing results are balanced, balanced, left heavy, it can be concluded that the defective ball is number 9, and it is lighter; if the result is balanced, balanced, right heavy, it can still be concluded that the defective ball is number 9, but it is heavier.

Similarly, if other situations arise, the defective ball can be identified smoothly using this method.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.