Suppose you have 1000 unlabeled vials, and you want to know whether it’s T or E inside. Since you’re not a chemist, you decide to test on passoids to find out which vials contain which hormone. You know that, if injected with any amount of Testosterone, the passoid kills herself within 24 hours.
*Edit: Forgot to mention but only 1 vial contains T, the rest contain E. You only have 1 day to figure out which vial is T.
What is the minimum number of passoids you need in order to guarantee that you can label the T vial? Explain your test process as well
hint: each vial contains enough to inject multiple times
999 with one day (either whoever dies or (if nobody dies) the untested vial)
with 2 days it’s better though, first take 31 passoids and inject them with 31 or 32 vials each (then the vials are split into 32 groups, since theres an uninjected group of 31 or 32 vials). wait 24 hour. if one dies, test those 31 or 32 vials using 30 or 31 passoids. if none do, its in the untested group and 30 or 31 passoids are needed. worst case, 62 passoids are used and 2 die.
with 3 days, its even better. take 9 passoids and inject them each with 100 vials (10 groups of vials). wait 24 hours, pick the new group to test on 9 more passoids with 10 vials each. wait 24 more hours, and then pick 9 more passoids. 27 passoids needed.
in general, the optimal solution for n days to test is n(⌈((1000)^(1/n))⌉ - 1). t. math major
It’s less!
hint: you can inject multiple passoids with the same vial, only a little T is enough to kill them
are you looking for 10? since log base 2 (1000) ≈ 10? if so, what method would you use to be completely sure, since I don’t think you could get it guaranteed with a worst case using only 10 passoids in a single day. I see that the limit as you get more days is 10 passoids used, but i dont think you could hit it in one day
you’re on the right track! there’s a method to do it in a day though
wait! i do see it actually! thats interesting!! i might be too combinatoricsbrained right now but it made sense to me when i realized you need 10 bits to represent one thousand in binary. also here’s a diagram.