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:

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

2. 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:

It is assumed one can provide multiple vaccine candidates to a single sample. For example, if you apply three different candidates to one sample, and the sample is not compromised, then you know none of those candidates work. On the other hand, if the sample is compromised, then you know that at least one of the three samples work, but not which one(s).

Answer 1

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

30

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

Label the $1000$ candidates from $000$ to $999$. Prepare $30$ tests, each testing the $100$ candidates that use a particular digit $0$-$9$ at a particular location in its label, for example one test contains all candidates that have a $7$ as their middle digit.

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

if there are 3 successful tests, each gives you one digit of the successful candidate's number.

If there is more than one successful candidate,

you will get more than three successful test results. You will still know what the digits are on the labels of the successful candidates, but not which combination of them is correct.

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

numbering in a different number base. For example in base $3$, you can use seven digits to label up to $3^7=2187$ candidates, and then you need a single round of only $3\cdot7=21$ tests to distinguish them. With $1000$ candidates the first ternary digit is never a $2$, so actually only $20$ tests suffice.
In binary you need $10$ bits ($2^{10}=1024$), so again this leads to $20$ tests. Larger bases result in a larger number of tests, so with this method $20$ is optimal.

Answer 2

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:

10 tests. $2^{10}=1024$, as Jaap said, so you can number the vaccines $1$ to $1000$ and give $1$ to $500$ to test subject 1, $1$ to $250$ and $500$ to $750$ to subject 2, $1$ to $125$, $250$ to $375$, $500$ to $625$, and $750$ to $875$, and so on and so on.

That way, your results will be a binary output of your ten test subjects, whether they still have COVID or not. There are 1024 possible outputs for that binary sequence, and thus they will provide enough information to narrow down which one is the working vaccine. Each ordered 10-tuple will correspond to exactly one vaccine, apart from 24 10-tuples, which will be impossible to obtain.

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

I can attack the problem from an information theory point of view. You're looking for 1000 bits of information - you don't just want to know how many work, you want to know whether every single vaccine works or doesn't work. Each test can only provide a positive or negative result, and thus no matter how many vaccines you inject someone with, they'll only give you one bit of information. Therefore, you need 1000 tests to determine exactly which vaccines work and which don't.

The most obvious way to do this is just to give one vaccine each to 1000 people.