## [Soln] Identifying the weight of one ingot

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 $\leq 11$ 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 $a, b, \dots, k$.

The first trivial weighing scheme is for Archimedes to weigh the combinations $\{1, 2\}$, $\{1, 3\}$, …, $\{1, 10\}$. That is 9 weighings. From the point of view of the king, he sees

\begin{aligned} \begin{cases} a + b &\leq 11, \\ a + c &\leq 11, \\ \vdots \\ a + j &\leq 11. \end{cases} \end{aligned}

Since all the ingot weights are distinct, it follows that $a = 1$: 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: $\{1, 10\}$, $\{2, 9\}$, $\{3, 8\}$, $\{4, 7\}$, $\{5, 6\}$. The king sees

\begin{aligned} \begin{cases} a + b &\leq 11, \\ c + d &\leq 11, \\ e + f &\leq 11, \\ g + h &\leq 11, \\ i + j &\leq 11, \end{cases} \end{aligned}

and deduces that

\begin{aligned} a, b, \dots, j &\leq 10 \\ \Rightarrow \qquad \{ a, b, \dots, j \} &= \{1, 2, \dots, 10\}, \\ \Rightarrow \qquad k &= 11. \end{aligned}

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: $\{1, 2, 3, 4\}$ and $\{1, 2, 3, 5\}$. The king sees

\begin{aligned} \begin{cases} a + b + c + d &\leq 11, \\ a + b + c + e &\leq 11 ,\end{cases} \end{aligned}

and looking at all possible combinations, deduces that

\begin{aligned} \{a, b, c\} &= \{ 1, 2, 3\} \\ \{d, e\} &= \{ 4, 5\}, \\ \{ f, g, h, i, j, k\} &= \{ 6, 7, 8, 9, 10, 11\}. \end{aligned}

That’s a lot of information! Now if Archimedes weighs $\{ 1, 4, 6\}$, the king sees

\begin{aligned} a + d + f \leq 11, \end{aligned}

and deduces that

\begin{aligned} 11 \geq a + d + f &\geq 1 + 4 + 6 = 11, \\ a + d + f &= 11, \\ (a, d, f) &= (1, 4, 6). \end{aligned}

This in turn implies that $e = 5$. 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: $\{ 1, 2, 3, 5 \}$. The king sees

\begin{aligned} a + b + c + d \leq 11, \end{aligned}

and concludes that

\begin{aligned} \{ a, b, c, d\} &= \{ 1, 2, 3, \text{either } 4 \text{ or } 5 \}, \\ \{ e, f, g, h, i, j, k \} &= \{ \text{either } 4 \text{ or } 5, 6, 7, 8, 9, 10, 11\}. \end{aligned}

If Archimedes uses $\{ 1, 4, 6\}$ as the second weighing, the king sees

\begin{aligned} \begin{cases} a + b + c + d &\leq 11, \\ a + e + f &\leq 11, \end{cases} \end{aligned}

and deduces that

\begin{aligned} 11 \geq a + e + f &\geq 1 + 4 + 6 = 11, \\ \Rightarrow \quad a &= 1, \{ e, f \} = \{ 4, 5\}, \end{aligned}

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 $\{a ,b, ... \}$ (where … could be empty) allows us to identify the weight of $a$. If we follow this same procedure but swap the positions of $a$ and $b$, everything looks the same to the king, and we will identify the weight of $b$ as the weight of $a$, 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.

This entry was posted in Russia and tagged , , , . Bookmark the permalink.