Well, I wrote a program, actually few, to use my strategy above.
And, here is what I got:
First, I tried to make this program without taking nice moves, and as expected I got a bit above 632 rough estimate. But it was due to bug. Then I add binary search in case when only one poisoned is remaining, and got 541: and was like o_O. I made some debug output, and it turned out that 541 was from 99 positives, and for some reason it said in this case you need 7 steps. And, it actually true, because we have 99 positives, and we decide from 99, so power of two is 7 not 9 as I've mentioned above. But, obviously I had a bug. And bug was with range of possible positives, so not all positives was considered. After it was fixed I got 633 and was like - why it's dumb and can't find 632 steps described above. And, it turns out that description above has mistake. :D Correct calculation is following: 333 (groups) + 301(summary size of groups) - 1 (we don't check last one) = 633. So, even with binary search, it wasn't able to find better than 633 steps "dumb approach". So, I had to add advanced knowledge that we already used a bit. It's when there are all negative in positive group, then remaining one is poisined. It's very tricky to apply correctly, because in some cases there are more 'empty' groups, in some cases there are less of those. So, idea is to find out number of minimum emtpy groups using pigeonhole principle or something similar. For example, if there are 99 positives, then there is possible that all of groups not empty. And, number of positives is always less than number of poisoned, so this information not enough to derive minimum number of 'empty' groups. So, I had to also consider how many poisoned drinks we got after tests one by one. And, knowing this information, if we have found 88 drinks among 99 positives, it means that at least 11 groups is empty, so at least 11 additional drinks are found! After this addition, I got result 568! So, in worst case you can solve it in 568 steps using this approach if my calculations and my program is right :D
Now, a bit about worst case. Surprisingly, worst case turns out to be 85 positives. My program says that you need 333 tests to test groups, then 85 largest groups one by one except one in each group = 4+3*(85-1) - 85 = 171. And, it says worst case is when we found 85 poisoned drinks during 171 tests, so none of them are empty. And we have to find 15 poisoned drinks among 85 remaining drinks under suspicion. And, in worst case it says we need 64 steps for that.
I thought worst case would be 75 positives, but my program tells it needs 558 steps, other interesting thing is that for 75 and less positives, worst found drinks is range with 75 in it, so 75 is also worst. And with decreasing number of positives this range is increasing.
I need to mention, that I was always considering as worst case is when positive groups are largest in size. I think following proof works: if we know how to find out poisoned drinks in K steps for largest sizes, then we can always add 'dummy' - non poisoned drinks and do all our operations with them even though we know they are not poisoned. Thus, we have groups of largest possible sizes, and we know how to solve them in K steps. So, always consider largest groups in summary size.
Okay, it was results of using strategy mentioned in previous post with some kind of pigeonhole principle applied. Now, thoughts regarding optimality.
I though about entropy approach, and depending on positive and negative groups any consequent group size is varies. But lets for a moment forget about this fact. Lets assume we know list of sizes. We know that all negative (no poisoned drinks in group) - whole group is decided. So, in the end we only need positive groups. Also, lets assume we don't use intersecting groups. And here is what I think: now we know only total number of poisoned drinks we have, but no information about number of poisoned drinks within groups. It means, in worst case any next group that pick drinks from several groups may have positive result and gives no information. It's not strict statement. It's just intuition, it's not proof and very likely is wrong. But I think so because we get more information (intuitively) if we split this set of picked drinks by groups that was already picked, we get more information. For example, if we try set 3,4,5,6 and we already tried set 1,2,3,4 and also 5,6,7,8, so better would be split our set into two: 3,4 and 5,6. So, if we try 3,4 and it's positive, we know that 3,4,5,6 positive, and also know that 3,4 is positive. but if 3,4 is negative, we know 3,4 is negative, and if we want to know about 5,6, we just also check 5,6. So, two checks to know about two sets. But if we use 3,4,5,6 we will need three checks in worst case. It's just intuition, not a proof. Also, we don't know how many poisoned drinks within the group. And best way to find out is to check all of them. So, if we belive in this, then we have to find out how many poisoned among all groups, and we need again check all of them one by one. This leads to question: how large is total size of all positive groups using entropy method? I don't know. it's hard task. Actually, better to know what maximum total size of all groups for each possible number of positive groups. Then, I can try my approach with it, and probably it could be better. But we know that this size is not greater than (positives*3)+1.
Other thing: for n > 1 to find (n-1) poisoned drinks from n you need n-1 steps. Even though entropy is same as to find 1 among n. You can't do better. because the only one set for test can reveal answer: pick non poisoned one. I think similarly you can prove for n > 2 that you need n-1 steps to find (n-2) poisoned drinks among n drinks. Also, optimal way to find out how many poisoned drinks among n require n steps.
Other idea is following, if I always pick largest positive groups among picked groups size, then imagine we don't care about probability, and just trying to minimize for each possible number of positive groups total size of largest of them. I didn't think in this way much, so I can't say anything about it yet.
Ah, I didn't mention, that to find 2 poisoned drinks among n there is better strategy similar to binary search, but I was lazy to add it. Idea is to try to find two non-intersecting largest groups that are both positive. And then, do binary search within them. Also, it may be better for larger number of poison drinks as well.
Also, little note: my program can't find better than 999 steps solutions for number of poisoned drinks from 333 and above. first less than 999 steps is 998 steps for 332 poisoned drinks :)
