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.)

The solution below is a little winding, but reflects my thought process as I was trying to solve this problem.

First, it’s clear that doing a weighing with just one ingot in the bag is not helpful: all it tells us is that that ingot is libras, which we knew already. Let’s write out all possible combinations of ingot weights that Archimedes can put into the bag involving 2 or more ingots:

Archimedes knows the weights of the ingots but the king doesn’t; from the point of view of the king he only knows which ingot went into which weighing. Denote the weights as variables .

The first trivial weighing scheme is for Archimedes to weigh the combinations , , …, . That is 9 weighings. From the point of view of the king, he sees

Since all the ingot weights are distinct, it follows that : **no other weight can be weighed against 9 different weights not equal to itself and not rip the bag.**

* While the first weighing scheme works, it’s clearly inefficient: we keep using the weight 1 over and over again.* This next scheme uses 5 weighings: , , , , . The king sees

and deduces that

By not using the same ingots across weighings, we reduced the number of weighings to 5. That still seems high (how would we prove that 4 weighings is not enough?) Looking back at the possible weight combinations, **it seems like putting more ingots in at once would be more efficient: it tells us that all those ingots must be on the lighter end, and very few combinations of these weights are possible.**

Let’s start with 2 weighings: and . The king sees

and looking at all possible combinations, deduces that

That’s a lot of information! Now if Archimedes weighs , the king sees

and deduces that

This in turn implies that . * We seem to have overachieved somehow: with 3 weighings we can identify the weight of 4 ingots!* This suggests that there might be possible to identify the weight of 1 ingot with just 2 weighings.

Let’s start again with 1 weighing: . The king sees

and concludes that

If Archimedes uses as the second weighing, the king sees

and deduces that

i.e. the king can deduce the weight of the ingot that weighs 1 libra. **We found a weighing scheme with 2 weighings that works!**

* What about one weighing?* One weighing is clearly insufficient by appealing to symmetry. As we said at the beginning, weighings with just one ingot do not provide any new information to the king. Assume our one weighing with ingots (where … could be empty) allows us to identify the weight of . If we follow this same procedure but swap the positions of and , everything looks the same to the king, and we will identify the weight of as the weight of , which is clearly false. Contradiction: one weighing is not enough!

**Hence, Archimedes needs 2 weighings to prove the weight of one of the ingots to the king.**

You must be logged in to post a comment.