4 ms·
I love problems like that. I'm going to go work that out for awhile, you have any links to the answer, or more questions like it?
by ImprovedSilence 15y ago
I love problems like that. I'm going to go work that out for awhile, you have any links to the answer, or more questions like it?
- web_chops 15y agoanswer can be found at http://madhurtanwani.blogspot.in/2009/09/find-poisoned-wine-barrel.html http://madhurtanwani.blogspot.in/2009/09/find-poisoned-wine-...
- nitrogen 15y agoI'm not the OP and I don't have a solution at hand, but I'd start by thinking about error correction and parity, then realize that 10 bits is enough to represent 1000 items completely.
- Munksgaard 15y agoSPOILER: Couldn't you just make one prisoner drink from half the barrels, and then if he dies have another prisoner drink from half of those barrels, and if not from half of the other barrels, and so forth?
- nitrogen 15y agoThat would work for the original question, but with the delayed death and quick response conditions imposed by pooriaazimi[0], it would not work. Tying the solution back to binary, you realize that each barrel has a unique 10-bit identifier (2^10=1024, so numbering the barrels in binary gives each one a unique ID). You assign each prisoner to a bit, then have them all drink from the barrels where their bit is a 1. 30 days later, you'll have a pattern of prisoner deaths exactly matching a single barrel. Note: I have not verified this solution, and it does not match the solution that was posted elsewhere in this thread. [0] https://news.ycombinator.com/item?id=3804350 https://news.ycombinator.com/item?id=3804350