Searching for the Covid vaccine

Question

You have 1000 possible Covid vaccine candidates.  You need to test them and find out if one works as quickly as possible.  The test is to apply a small drop of a vaccine candidate to a sample,  and wait to see if the Covid virus is compromised.  The tests are very expensive and time-consuming, so you want to perform as few as possible.  Since the tests are time-consuming, you only want to do one round of testing.
What is the fewest number of tests to confirm:

If there is a single working vaccine, identify which one it is.

If there is more than one working vaccine, then identify that situation as well.  (Since that would be good news, it is OK if more testing is needed to root out the particulars of that).

HINT:

Jaap Scherphuis · Accepted Answer

Here is one simple way to solve the problem in a single round of

tests. This is not optimal, but easy to explain. At the end I'll describe an improved version.

When the results come back, you can easily find which candidate is the successful one, because

If there is more than one successful candidate,

The above method is not optimal, but can be improved by

Spandan · Answer

I think I've heard this one before (at least, part 1). It was about one poisoned bottle of wine and prisoners on death row.
The solution to that problem was very similar to what @Jaap suggested:

As for part two, with multiple possible vaccines that work:

Searching for the Covid vaccine

2 Answers

Add your own answers!

Ask a Question