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
The answer is 10. More specifically what it takes to get all the possibilities is find a number n that is so that 2^n it bigger or equal to the number of vials
If you have 4 vials for example (a, b, c and d), you’d need 2 people (A and B). Here are the possibilities for each vials if A is injected with b and c, and B is injected with c and d.
a: no one dies
b: A dies
c: AB dies
d: C dies
let’s do 8 vials now (a, b, c, d, e, f, g, h, i). You’d need 3 people (A, B, C). A has bcdh, B has cef and C has dfgh
a: no one dies
b: A dies
c: AB dies
d: AC dies
e: B dies
f: BC dies
g: C dies
h: ABC dies
Now if we have 4 people A, B, C and D, we have:
a: no one dies
b: A dies
c: AB dies
d: AC dies
e: AD dies
f: ABC dies
g: ABD dies
h: ACD dies
i: B dies
j: BC dies
k: BD dies
l: BCD dies
m: C dies
n: CD dies
o: D dies
p: ABCD dies
So the pattern is (left is n person, right is n vials)
1: 2
2: 4
3: 8
4: 16
This follows a 2^n rule, considering n is the number of people
So we need to find the number n that makes 2^n smaller or equal to 1000
29 is 512, then you have 210
So you need 10 people.
My arms hurt typing this lol.
edit: god ther formating
hmm i think that’s basically it so i’ll give it to you. congrats!
Test all 1000, a thousand passoids is a fair sacrifice
it’s fair but you don’t need that many!
Simple. I test each vial on cis passoids. You didn’t specify the type of passoid. Cisoids can be non-passoids too
that might be ideal but since this is matttth it’s incorrect
Oh didn’t read the sub name
(I honestly just saw this problem on xitter recently, but still had to take a piece of paper and check on lower vial counts)
iirc you’ll need 10 passoids
you assign every vial a bit number, which will be 10-bit (2^10 is 1024 obv) then you give 1st passoid a shot from every vial which has 1 as the first digit from the end then you give 2nd passoid a shot from every vial which has 1 as the second digit from the end et cetera
if passoids 10, 9, 3 and 1 kill themselves, for example, the vial would be number 1100000101, which is vial 773
but actually nvm you need like a million passoids and inject all of them from every vial
minimum would be one?
since its the possibility of gettibg it first time
minimum number that guarantees that you know the vial
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.
If the passoid doesn’t kill herself use the same passoid for another vial and repeat until she does. Minimum number of passoids required can’t be determined without knowing how many are T and how many are E
Or alternatively just test each vial on as many cissoids as the contents allow (just to make sure and obviously not for TCD reasons)
Sorry i forgot to mention, 1 vial is T the rest are E and you only have 1 day to figure it out
By time constraints then 1000 but if you can use another batch at that 24hr mark then 500 if you get it first try but 1000 if you don’t . Or am I missing something
Or get reaaaaaally lucky and just so happen to find the t vial first try and not test any more
you only have 1 try but you can do it in fewer than 1000
Wuh, idk I’m stumped then
if no one gets it a few hours i’ll post the answer
Oh nvm only one vial is T so only one passoid is needed
1000
deleted by creator
closest so far
deleted by creator
can you explain the process to find the vial?
Let me see if I am understanding this correctly, we only have 1 round of testing because 1. we have to wait 24 hours to see results and 2. we have a 1 day time limit, correct?
am I retarded or is it not 1000?
Yes you only have 1 round of testing but you can do it in less than 1000
is it 999 and this is just a trick question
nope, i can give a hint: you don’t need to inject each passoid with a whole vial — you can inject multiple passoids with the same one
deleted by creator
yep!
deleted by creator
deleted by creator
yep, there’s enough in the vials to do multiple injections
deleted by creator
500,250,125,63,32,16,8,4, 2, and then only 1 remains so 10 passoids
you only have 1 day to test though
