Archimedes Helps Again
Below, you can find a lovely problem from the 2016 All-Russian Olympiad suggested by Bogdanov and Knop. I took some liberties translating it.
Problem. 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?
And a bonus question from me.
Share:Bonus. Add one more weighing to prove the weight of three more ingots.
Kenneth Tay:
Cute problem! I have a solution where I can’t prove the weight of any ingot after 2 weighings, but can prove the weight of 4 ingots after 3 weighings. Does it sound like I’m on the right track?
8 January 2022, 12:10 pmKenneth Tay:
Never mind, I solved it 🙂
8 January 2022, 12:17 pmIdentifying the weight of one ingot | Beyond Solutions:
[…] I discovered this problem on Tanya Khovanova’s blog, who in turn got it from the 2016 All-Russian […]
9 January 2022, 1:01 am[Hints] Identifying the weight of one ingot | Beyond Solutions:
[…] I discovered this problem on Tanya Khovanova’s blog, who in turn got it from the 2016 All-Russian […]
10 January 2022, 1:01 amRaymond:
Only 2 sets of 4 ingots are allowed: 1+2+3+4=10 and 1+2+3+5=11.
1st weighing:1,2,3,4. The bag is safe.
Archimedes removes one of the previous four ingots, and replaces it by 5: that is the second weighing.
As the bag is still alive, this proves that the ingot removed has a weight of 4 libras.
Indeed, if 3 were removed the second weighing would sum up to 1+2+4+5=12, and the bag would break up. Same conclusion if ingot 2 libras or 1 libra were removed after 1st weighing.
So the 4 libra ingot has been identified.
10 January 2022, 11:49 amtanyakh:
Raymond, your method doesn’t distinguish between 4 and 5.
10 January 2022, 12:17 pm[Soln] Identifying the weight of one ingot | Beyond Solutions:
[…] I discovered this problem on Tanya Khovanova’s blog, who in turn got it from the 2016 All-Russian […]
11 January 2022, 1:02 amRaymond:
Tanya, give me another chance.
11 January 2022, 1:29 amFirst try: as before, we put four ingots in the bag. As the bag survives, we have either (1,2,3,4) or (1,2,3,5).
Second try :Archimedes removes 3 ingots from the bag, which he knows to be the three heaviest, and he replaces them by just one ingot: the 10 libra ingot. Thus the bag contains 2 ingots (x,10).
Since the bag survives, x=1: Archimedes draws the bag x=1 from the bag and presents it successfully to the King as the 1 libra ingot.
Only 2 tries have been required to identify the 1 libra ingot.
tanyakh:
Raymond, the second weighing could be 2 + 9.
11 January 2022, 9:51 amTed:
I can do one ingot in four weighings, and three more with a fifth weighing. Is that your answer as well?
21 January 2022, 4:49 pmTed:
Probably can be done more quickly.
21 January 2022, 4:50 pmCyberK:
I think I went through the same thing as Kenneth T. – first finding a solution to figure out 4 ingots in 3 weighings, and then it took me a while to get one ingot in only two weighings.
23 January 2022, 9:52 pmAt first I thought wording wasn’t precise, but it is: to identify four, it’s one more weighing *in addition* to what was done to identify one ingot. Not a separate set of completely new N+1 weighings.
But yeah, cute puzzle, I can ID ingot 1 in two weighings, and then 4,5,6 in one more weighing.
Gennardo:
Let A, B, C, .. , K be the ingots with 1, 2, 3, 11 l(ibras) respectively
Archimedes knows this, Hiero doesn’t. At first Archimedes puts A, B, C, D in the bag then he exchanges D and E
Since the bags helds both times and (1l, 2l, 3l, 4l) and (1l, 2l, 3l, 5l) are the only sets of four which held, Hiero
knows that A, B, C weigh (1l, 2l, 3l) i(n) s(ome) o(rder), D and E weigh (4l, 5l) i.s.o. and F, G, H, I, J, K weigh
(6l, 7l, 8l, 9l, 10l, 11l) i.s.o.
The third try is A, D and F and the bag holds. Since D weighs at least 4g and F at least 6g Hiero knows that these
must be their exact weights and he now knows the weight of A, D, E and F
Bonus question:
2 February 2022, 3:56 pmThere is no need for another weighing because Hiero already knows the weight of 4 ingots