Maths Olympiad Prep

Library / /43 of 57

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Russia

King Hiero has 11 metal pieces indistinguishable in appearance. The King knows that their weights (in some order) are 1,2,,111, 2, \ldots, 11 kg. Also the King has a bag that breaks if it contains more than 1111 kg. Archimedes knows the weight of each piece, and he wants to prove to Hiero that the first piece weighs 11 kg. By a move Archimedes can put several pieces into the bag demonstrating to the King that the bag is still not broken (it is prohibited to break the bag!). Find the least number of moves needed for Archimedes to prove his claim.

Solution

The moves are 1+2+3+51+2+3+5 and 1+4+61+4+6.

Show that Archimedes needs to use the bag twice. Let him first put into the bag the pieces weighing 11, 22, 33, and 55 kg, and then the pieces weighing 11, 44, and 66 kg. In both cases, the bag does not break.

Let us prove that this could only happen if the 11 kg piece was used both times. Indeed, if Archimedes, instead of the pieces weighing 1,,61, \ldots, 6 kg, used pieces weighing w1,,w6w_1, \ldots, w_6 kg, then these weights would satisfy the system of inequalities w1+w2+w3+w511w_1 + w_2 + w_3 + w_5 \le 11, w1+w4+w611w_1 + w_4 + w_6 \le 11. Adding these inequalities, we get w1+(w1+w2++w6)22w_1 + (w_1 + w_2 + \ldots + w_6) \le 22. The sum in parentheses is the sum of six distinct natural numbers, so it is at least 1+2++6=211 + 2 + \ldots + 6 = 21. Hence, w12221=1w_1 \le 22 - 21 = 1. Therefore, w1=1w_1 = 1, that is, the 11 kg piece is uniquely determined.

It remains to show that one move is not enough. If Archimedes puts only one piece in the bag, the bag will not break in any case, so no piece can be identified. If Archimedes puts more than one piece in the bag and the bag does not break, then if the 11 kg piece is not in the bag, replacing any piece in the bag with it will not change the result; thus, Hiero cannot even tell whether the 11 kg piece is in the bag. If the desired piece is in the bag, Hiero cannot tell which of the (at least two) pieces is the required one.

Note. After these two moves, the group of pieces weighing 22, 33, and 55 kg, as well as the group weighing 44 and 66 kg, are also uniquely determined.

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.