Communications of the ACM
Last byte
Ruby Risks
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 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.
Footnotes
All are invited to submit their solutions to [email protected]; solutions and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2017 ACM, Inc.
No entries found