3 ms·
We 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
by yu3zhou4 2y ago
We 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.