King Hiero II of Syracuse has 11 identical-looking metallic ingots. The king knows that the weights of the ingots are equal to 1, 2, …, 11 libras, in some order. He also has a bag, which would be ripped apart if someone were to put more than 11 libras worth of material into it. The king loves the bag and would kill if it was destroyed. Archimedes knows the weights of all the ingots. What is the smallest number of times he needs to use the bag to prove the weight of one of the ingots to the king?
(Credits: I discovered this problem on Tanya Khovanova’s blog, who in turn got it from the 2016 All-Russian Olympiad.)
Hint 1: Write down all possible combinations of weights that Archimedes can put into the bag without ripping it.
Hint 2: 2 weighings is enough!
Hint 3: Here’s one way to use 5 weighings to identify the ingot of weight 11. Put the following combinations in the bag: , , , , . With these weighings, we have identified 10 different weights that weigh less than 11. Hence, they must be 1, …, 10 in some order, meaning the last remaining weight must be 11.
Putting two weights in the bag at a time is too inefficient of a way to extract information. Can we do better with more weights in the bag?