5 ms·
The shape of information
- bbqbbqbbq 2y ago[dead]
- yu3zhou4 2y agoWe can also open first 50 bottles, mix drops of each, use test, if positive then we know that one of them is poisoned, if not then we know that one of the other 50 is poisoned. So we take the poisoned 50, split on two brackets and repeat. With 7 tests, we can narrow down to a single poisoned bottle (50, 25, 12/13, 6/7, 3/4, 2, 1)
- The28thDuck 2y agoBinary search strikes again!
- yu3zhou4 2y agoNothing clever, I know :p
- selimthegrim 2y agoMaybe so, but pooled testing as they refer to in the article involves using Lambert W function to solve for optimal size of individuals tested.
- photochemsyn 2y agoThe limit of detection of the test comes into play; detecting poison at a 1:50 dilution might be impossible with that test.
- TeMPOraL 2y agoBut then, if that test can detect poison at 1:50 dilution, it means it probably has enough reagent to detect poison at 1:25 twice, if you're clever about it. Done well, you may end up with a single bottle identified and a bunch of unused tests to sell.
- account42 2y agoThe solution in TFA already requires the test to detect the poinson in a mix of up to 64 bottles as for 7 test each batch will contain half of the (maximum possible 128) bottles.
- ubittibu 2y agoI hate when riddles are told badly and ruined. I remember the original one which was not solvable this way and really puzzled me. When resolving the one in the article I asked myself why I had found this to be much more complicated, and it was beacuse the number of bottles was 128 in the original.
- Chinjut 2y agoWhat do you mean? It works the exact same way for 128 bottles. 64, 32, 16, 8, 4, 2, 1.
- baruz 2y agoIf I understand the GP comment correctly, the puzzle when they first heard it was for 128 bottles, which was a big clue that the solution involved binary, spoiling the puzzle for them. The article’s use of 100 bottles obscured the intent and made the puzzle harder.
- kgwgk 2y ago“the original one which was not solvable this way” doesn’t seem to fit in that interpretation.
- Chinjut 2y agoThis is essentially the same approach as the solution described in the article. You are observing the bits of the poisoned bottle number in binary, bit by bit. The only difference is that you avoid retesting any bottles once they have been ruled out by previous tests, whereas the fixed design in the article does not bother with this.
- bo1024 2y agoIn these situations one can also ask about the "adaptivity gap", which is the difference in how many tests are required if one is allowed to be adaptive -- make a test, look at the result, then decide what to test next -- versus nonadaptive, i.e. decide in advance what all the tests will be and conduct them all at once.
- ReleaseCandidat 2y agoThe answer is easy: by his way of testing exactly one bottle won't be opened and of course that's the one that contains the poison. Drinking 99 bottles of wine before they go stale isn't too healthy either, I'd guess.
- mirekrusin 2y agoExactly better to keep 7 with scotch taped test and sell the rest on amazon, call it a day.
- twentythree 2y agoGuaranteed 98.9% positive feedback (https://xkcd.com/325 https://xkcd.com/325)
- photochemsyn 2y agoWhen faced with incomplete data, it's really always better to go back and get a more complete and reliable dataset than to apply a host of statistical tools to that poor data in the hopes of extracting some trend or meaning from it. > "Fortunately, you have a test that can detect poison very accurately, even among a large volume of liquid. Unfortunately, you have only 7 of these tests available. What should you do?" You should estimate the cost of getting another 93 tests, consider if a cheaper method is plausible and could be developed at lower cost, then compare that to the value of the wine bottles. With infectious disease, this is problematic as putting a cost on every individual human life is tricky, even if that's the life insurance business model. As a practical example, the cost of running the CDC's malaria detection program (captures some 2,000-3,000 cases a year from incoming travellers) in the USA is considered worth the benefit of not allowing malaria to become endemic again across the Southeastern US.
- Nevermark 2y agoThe puzzle fails spectacularly. Without additional action all that wine will go bad. Important detail is one must recork each bottle immediately after sampling & refrigerate. Now the wine will be preserved, and the very slight pre-drinking oxygen bump is likely to improve it over first corking. A little overlooked & underrated trick. (Remember to decant reds and allow them to reach room temp before drinking.) Also left out is value/opportunity maximization, which is a crucial implicit factor in any gamed, especially adversarial, situation. Math & algorithm problems without complete context value optimization are just ivory tower toys! The real world, Machiavelli, your ancestors, and your shareholders demand better! The poisoned bottle, once identified, is worth a great deal. Minimum value realization is obtained by rebottling, and re-gifting it to its original source. Anonymously. Of course! Or you can save it for a special occasion! Sometimes the best move is no move. Accumulate optionality.
- Kydlaw 2y agoThis type of comment is one of the two reasons I'm still opening comments on HN. Thank you for the laugh.
- TSP00N3 2y agoActually, they used a Coravin[0] so they can test the wine without opening the bottle! [0]https://www.coravin.com/pages/how-it-works https://www.coravin.com/pages/how-it-works
- IncreasePosts 2y agoYou can pierce the cork with a hypodermic needle to obtain a sample without introducing any outside atmosphere, as any wine aficionado knows.
- tpoacher 2y ago"Did you remember to change the needle between samples?" "... ah ... shit."
- esafak 2y agoTo paraphrase Crocodile Dundee; that's not the shape of information, this is: https://en.wikipedia.org/wiki/Information_geometry https://en.wikipedia.org/wiki/Information_geometry
- deleted 2y ago[deleted]
- atherton33 2y agoI think you need to take into account how long the wine lasts after you uncork it and how long it takes you to drink the bottle. If you're drinking all 100 bottles in one night this works, but if you drink a bottle a week you're going to spoil all of it using this strategy.
- Aunche 2y agoYou can use a Coravin to sample all the wines while introducing minimal oxygen.
- juancn 2y agoThis is how syphilis was screened by the army, it's called sample pooling and saves an awful lot of money.
- Nihilartikel 2y agoI used to use a variant of this poison wine problem as an interview question. It was actually pretty good - the ones that could perceive problems abstractly usually got it without too much prompting. And the process of approaching a solution was informative.
- personjerry 2y agoReminds me of the probability based counting algorithm that was on the front page last month: https://news.ycombinator.com/item?id=40379175 https://news.ycombinator.com/item?id=40379175