Fewest Balance-Scale Weighings to Find the One Ball With a Different Weight

You have a set of balls that look identical, and exactly one of them has a different weight from the others. You also have a two-pan balance that only shows which side is heavier or that the two sides balance. What is the minimum number of weighings that guarantees you find the odd ball? The report does not give the number of balls or say whether the odd ball is known to be heavier or lighter, so settle both with the interviewer first. A strong answer gives the minimum for any number of balls n in each case and works through a concrete instance. ```hint Three outcomes Each weighing has three possible results. Count the distinct answers the weighings must tell apart, and see what that implies for the number of weighings. ``` ```hint When the direction is unknown Count each ball twice, once as possibly heavy and once as possibly light, and ask whether the first weighing can always split those possibilities into three groups that are small enough. ``` ### Clarifying Questions - How many balls are there? - Is the odd ball known to be heavier, known to be lighter, or could it be either? - Must you also say whether it is heavier or lighter? - Is an extra ball of known normal weight available? - May each weighing depend on the results of the earlier ones? ### What a Strong Answer Covers - The counting bound from three outcomes per weighing - A matching strategy when the odd ball is known to be heavier, with the formula for n balls - The unknown-direction case: why the counting bound is not tight, the exact maximum number of balls for a given number of weighings, and a complete strategy for a concrete case - How a reference ball, or not needing the direction, changes the answer - Small and impossible cases, such as two balls when the direction is unknown ### Follow-up Questions - With 13 balls and the direction unknown, can three weighings always find the odd ball and its direction? What changes with one extra ball known to be normal? - Can the three weighings for 12 balls be fixed in advance, so that no weighing depends on an earlier result? - If the odd ball is known to be heavier, how many balls can four weighings handle?