Sign In

Communications of the ACM

Last byte

Ruby Risks


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
Ruby Risks, illustrative photo

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

Credit: Victor Moussa

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 questionwhere one box has four more rubies than some other boxhow 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

Author

Dennis Shasha (dennisshasha@yahoo.com) is a professor of computer science in the Computer Science Department of the Courant Institute at New York University, New York, as well as the chronicler of his good friend the omniheurist Dr. Ecco.

Back to Top

Footnotes

All are invited to submit their solutions to upstartpuzzles@cacm.acm.org; solutions and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html

Back to Top

Figures

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

Back to top


Copyright held by the author.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2017 ACM, Inc.


 

No entries found