Hacker News Reader

Comment by yu3zhou4 | Hacker News Reader

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)

View on HN

Binary search strikes again!

Nothing clever, I know :p

Maybe so, but pooled testing as they refer to in the article involves using Lambert W function to solve for optimal size of individuals tested.

I 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.

What do you mean? It works the exact same way for 128 bottles. 64, 32, 16, 8, 4, 2, 1.

If 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.

“the original one which was not solvable this way” doesn’t seem to fit in that interpretation.

The limit of detection of the test comes into play; detecting poison at a 1:50 dilution might be impossible with that test.

But 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.

The 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.

This 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.

In 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.

Reply on news.ycombinator.com