You have a balance scale and a set of identical looking balls, exactly one of which is heavier than the rest. What is the largest number of balls for which 3 weighings always identify the heavy one, and why does one more ball defeat every strategy?

You have a balance scale and a set of identical looking balls, exactly one of which is heavier than the rest. What is the largest number of balls for which 3 weighings always identify the heavy one, and why does one more ball defeat every strategy?

Approach: Count how many distinguishable outcome sequences three weighings can produce, then build a strategy that realises every one of them by splitting into equal thirds.

27. A balance scale gives three outcomes per weighing, left heavy, right heavy or level, so 3 weighings produce at most 3^3 = 27 distinct outcome sequences, and each candidate ball needs its own sequence. That is the information bound. It is achieved: split 27 into three groups of 9 and weigh two groups, which names the group of 9 holding the heavy ball, then repeat on groups of 3, then on single balls. With 28 balls the 28 candidates exceed 27 sequences, so by pigeonhole two balls share a sequence and no strategy can separate them. The bound is this tight only because the heavy direction is known: with an unknown direction 3 weighings handle at most 12 balls.

Follow-up: How many balls can 3 weighings handle if one ball differs in weight but you are not told whether it is heavier or lighter?

Key concepts: information bound, three outcomes, balance scale, pigeonhole.