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.

Bonus. Add one more weighing to prove the weight of three more ingots.

Share:Facebooktwitterredditpinterestlinkedinmail

13 Comments

  1. 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?

  2. Kenneth Tay:

    Never mind, I solved it 🙂

  3. 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 […]

  4. [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 […]

  5. Raymond:

    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.

  6. tanyakh:

    Raymond, your method doesn’t distinguish between 4 and 5.

  7. [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 […]

  8. Raymond:

    Tanya, give me another chance.
    First 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.

  9. tanyakh:

    Raymond, the second weighing could be 2 + 9.

  10. Ted:

    I can do one ingot in four weighings, and three more with a fifth weighing. Is that your answer as well?

  11. Ted:

    Probably can be done more quickly.

  12. CyberK:

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

  13. 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:
    There is no need for another weighing because Hiero already knows the weight of 4 ingots

Leave a comment