Competition problem — Combinatorics

Library / /16 of 24

Combinatorics Difficulty 6.8 National olympiad Prove it Argentina

There are 13 weights, all of different colors, and a balance. Ana and Beto know that the weights are of $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$ , $9$ , $10$ , $11$ , $12$ and $13$ grams, but only Ana knows which color corresponds to each weight.

An operation consists in putting weights on each side of the balance so that it stays balanced.

Ana wants to do a series of operations that allow Beto to determine with certainty the color of the weight of $1$ gram, by just looking at what she does.

What is the minimum number of operations Ana must do to achieve her goal? Decide which those operations are and how Beto determines the color of the weight of $1$ gram. Explain why she cannot do it with fewer operations.

Remark: The balance is balanced when the total weight of the objects put in each side is the same.

Solution

Let us see that the minimum number of operations that Ana has to make is $2$ .

In the first operation, Ana balance eight weights in one side with three in the other. The weight of eight weights is at least $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36$ , and the weight of three weights is at most $11 + 12 + 13 = 36$ . Then, the only possibility to achieve balance is that the weights in one pan are $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$ and the weights in the other pan are $11$ , $12$ and $13$ . The weights that have not been put on the balance are those of $9$ and $10$ grams.

In the second operation, Ana balances the weight of $10$ grams in one side, with the weight of $9$ grams together with the weight of $1$ gram in the other side.

Since Beto had identified the weights of $9$ and $10$ grams after the first operation (even if he does not know the weight of each of them), he deduces that the third weight considered by Ana in the second operation is that of $1$ gram.

Finally, let us show that Beto cannot identify the weight of $1$ gram in only one operation. When Ana makes an operation, there are three groups of weights: those in the left side of the balance, those in the right side, and those that remain outside. To determine which is the weight of $1$ gram, it should be the only weight in one of these groups. It cannot be the only weight outside the balance, since the weight of the remaining ones is $2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 = 91$ , which is odd, so there is no way to achieve balance with them. It is not possible either to achieve balance by leaving the weight of $1$ gram alone in one side. The proof is complete.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.