Computing Applications Last byte

Ruby Risks

  1. Article
  2. Author
  3. Footnotes
  4. Figures
Ruby Risks, illustrative photo
How many of these red beauties could you obtain if you properly curbed your greed?

You have three covered boxes of Burmese rubies before you. You know there are a total of 30 identical seven-carat rubies in the three boxes. You can ask for a certain number of rubies from each box. If you ask for more than there are, you get none from that box. Otherwise, you get what you asked for from that box. For now, suppose you must state your requests in advance for all three boxes and have no chance to change your mind; that is, with no feedback.

Warm-Up. Given no further constraints, how many rubies do you ask for from each box?

Solution to Warm-Up. If you ask for, say, 10 from each box, then one box may have 30 and the others 10, so you may get only 10. If you ask for x, where x < 10, you might get only x, if one box has all 30. On the other hand, if you ask for more than 10, then they might evenly be distributed (10 rubies in each box), meaning you get none. You should thus ask for 10, because 10 is the maximum you are guaranteed to get.

Suppose you know one box has four more rubies than some other box and the remaining box could have any number. Again, you must make requests for all boxes at once, so you cannot use your winnings from earlier boxes to help you determine what to do later. How many rubies in total can you guarantee to receive?

Solution. The boxes have x, x + 4, and y. Here are the possibilities, in ascending order, from what is in the first box:

(i) 0, 4, 26; (ii) 1, 5, 24; (iii) 2, 6, 22; (iv) 3, 7, 20; (v) 4, 8, 18; (vi) 5, 9, 16; (vii) 6, 10, 14; (vii) 7, 11, 12; (vii) 8, 12, 10; (viii) 9, 13, 8; (xi) 10, 14, 6; (xii) 11, 15, 4; and (xiii) 12, 16, 2

You are guaranteed to receive 12 rubies by asking for 12 from all three. No other scenario guarantees you more rubies.

Upstart 1. (Feedback) Suppose the boxes are laid out in left-to-right order and you may state your request for the leftmost box first, then, based on how many rubies you receive, state your request for the middle box, and then the rightmost one. When you are done, you can repeat this process (left, then middle, then right). For both the warm-up scenario and the scenario outlined in the first question—where one box has four more rubies than some other box—how many more rubies can you guarantee to get in this “2-feedback” scenario?

Upstart 2. Suppose you are told there are b boxes with r rubies overall and that one box has d more rubies than some other box. Can you formulate an algorithm for both the f-feedback (meaning you go left, middle, right f times) and no-feedback scenario that is optimal? If so, please explain your algorithm in pseudocode and send links to your software.

Back to Top

Back to Top

Back to Top


UF1 Figure. How many of these red beauties could you obtain if you properly curbed your greed?

Back to top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More