Can’t you easily reduce this to a compatible problem though?
Let’s say you have the set of foods you suspect: red blue green yellow brown purple
You construct an ordered set from this by making the elements sets of foods such that each set is the one to its left plus any one more entry, the leftmost set is the empty one, and the rightmost is the one containing all your suspects:
Now a check operation means eating the elements in the current set, if you get sick you go half way to the left border and update the right one, if you don’t get sick you go half way to the right border and update the left one.
You should end up with the smallest set that makes you sick. Subtract the set to the left of it and you have the food that makes you sick left over.
I dont think that works. If i try the 5 ingredient set and get sick, i gained no information about ingrediences 6,7,8,9,10 (if there are 10 ingredients in total). If next i try set 3 and get sick, i have made 2 tries and still have 0 information. If ingredient 1 makes me sick i will need log(n) tries until i try the set that only contains ingredient 1. After that i have only one point of information because everything i tried so far was tainted by ingredient 1. I have to try everything again.
Anytime you get sick you gain no information. If you are very lucky and ingedient 1-x are all harmless, then you will eliminate multiple at once. But if 1 is harmless, 2 makes you sick, and the next 1000 ingredients are harmelss you will still have to try log(1002) times to eliminate ingredient 2 and then you know nothing about 3-1003.
I dont think that works. If i try the 5 ingredient set and get sick, i gained no information about ingrediences 6,7,8,9,10 (if there are 10 ingredients in total).
Wait why not?
Maybe we’re not thinking of the same scenario here. I thought we were searching for exactly one ingredient that makes you sick. In which case this result would tell you the ones outside the set are all fine.
Can’t you easily reduce this to a compatible problem though?
Let’s say you have the set of foods you suspect: red blue green yellow brown purple
You construct an ordered set from this by making the elements sets of foods such that each set is the one to its left plus any one more entry, the leftmost set is the empty one, and the rightmost is the one containing all your suspects:
{}, {red}, {red, blue}, {red, blue, green} … {red, blue, green, yellow, brown}, {red, blue, green, yellow, brown, purple}
Now a check operation means eating the elements in the current set, if you get sick you go half way to the left border and update the right one, if you don’t get sick you go half way to the right border and update the left one.
You should end up with the smallest set that makes you sick. Subtract the set to the left of it and you have the food that makes you sick left over.
I dont think that works. If i try the 5 ingredient set and get sick, i gained no information about ingrediences 6,7,8,9,10 (if there are 10 ingredients in total). If next i try set 3 and get sick, i have made 2 tries and still have 0 information. If ingredient 1 makes me sick i will need log(n) tries until i try the set that only contains ingredient 1. After that i have only one point of information because everything i tried so far was tainted by ingredient 1. I have to try everything again.
Anytime you get sick you gain no information. If you are very lucky and ingedient 1-x are all harmless, then you will eliminate multiple at once. But if 1 is harmless, 2 makes you sick, and the next 1000 ingredients are harmelss you will still have to try log(1002) times to eliminate ingredient 2 and then you know nothing about 3-1003.
Wait why not?
Maybe we’re not thinking of the same scenario here. I thought we were searching for exactly one ingredient that makes you sick. In which case this result would tell you the ones outside the set are all fine.
Yes, you can reduce it much faster assuming one food doesn’t contaminate random other foods and it’s not a workplace hygiene thing.
You could also ask for a bowl, dressing on the side, take it home, try the tuna, 12h try the dressing, 12h try the veggies.