Communications of the ACM
Last byte
Upstart Puzzles: Brighten Up
Contemplating two bags containing flares, only one of which has bad flares; the goal is to take only good flares, which could come from one or from both bags, on a trip.
Credit: Andrij Borys Associates / Shutterstock
You are given two bags, each containing some number NumPerBag of flares. You know there are NumBad flares in one of the bags but not which bag. The other bag has all good flares. Each time you test a flare, you use it up.
Here is the first challenge: You want to take NumBad-1 flares with you and want to know all are good. Further, you want to use up as few flares as possible in the process. It is fine that when you are done, you may not know which of the unused flares you leave behind are good.
Warm-up. If all the flares in the bad bag are indeed bad, then how many flares would you need to test?
Solution to this warm-up. Test just one flare in one bag. After that you would have at least NumPerBag-1 = NumBad-1 good flares to take from the bag you know has only good flares.
For general values of NumPerBag and NumBad, consider two strategies:
Balanced. Take a flare from the first bag and test it, then one from the other bag and test it, and continue alternating until you find a bad one or you reach NumBad-1 in one of the bags, in which case you know the remaining ones in that bag are good; and
Unbalanced. Keep taking one flare from a single bag and testing it until you find a bad one or reach NumBad-1 in that bag.
Which strategy uses up fewer flares in the worst case?
The average case is worthy of an upstart challenge:
Upstart 1. Assuming NumBad = 3, are there values of NumPerBag for which the balanced strategy uses up fewer flares than the unbalanced strategy on average, assuming no particular ordering of the flares in either bag? And vice versa. Is there some mixed strategy that is better than either one alone?
2. Now imagine you want to take NumBad flares (not just NumBad-1) on your trip with the guarantee all are good. Which strategy would give you the best chance of achieving this? For this challenge, the number of flares you use up in testing is unimportant.
Upstart 2. Given NumPerBag and NumBad, suppose you want to take d more than NumBad with the guarantee all are good. What is the best strategy to use (it may be a hybrid), and what probability of success as a function of d can you achieve?
Solution to 1, or taking NumBad − 1 good flares on the trip. Unbalanced, because it will use up 1 + NumPerBag − NumBad flares in the worst case, whereas balanced may use up 1 + 2*(NumPerBag − NumBad) in the worst case.
Solution to 2, or taking NumBad good flares on the trip. With the unbalanced strategy, if you are lucky enough to start testing flares with the bad bag, you will be able to take NumBad good flares for sure. If you start testing flares with the good bag, then you will test 1 + NumPerBag − NumBad flares from that good bag, leaving you NumBad − 1 good fares. But you can get one more good flare from the bad bag by testing flares from that bag until you discover all NumBad flares and seeing whether you have any more flares left in that bag. With the balanced strategy, if you discover no bad flare by the time both bags have NumBad flares left and the next flare tested is also good, then the strategy fails to deliver NumBad flares that are all good. However, that is the only case in which the balanced strategy loses. Balanced is thus better.
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
Figures
Figure. Contemplating two bags containing flares, only one of which with bad flares; the goal is to take only good flares, which could come from one or from both bags, on a trip.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2015 ACM, Inc.
No entries found