8
$\begingroup$

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).

$\endgroup$
11
  • 2
    $\begingroup$ Does this answer your question? Twelve balls and a scale $\endgroup$
    – Oray
    Jul 20 '20 at 16:04
  • 2
    $\begingroup$ Those all involve multiple weighings. I don't think that would produce the optimal answer in this case. $\endgroup$
    – Jiminion
    Jul 20 '20 at 16:07
  • 2
    $\begingroup$ The question that most resembles this one is Wolves and Sheep, but that one asks us to identify 5 out of 100, whereas this one asks for 1 (or more) out of 1000. $\endgroup$ Jul 20 '20 at 16:15
  • 1
    $\begingroup$ @Oray, what I mean by that is the subsequent weighings are dependent on the results of previous weighing(s). $\endgroup$
    – Jiminion
    Jul 20 '20 at 17:25
  • 2
    $\begingroup$ This reminds me of the 1000 bottles of wine problem, though I'm not sure it is a duplicate exactly. $\endgroup$
    – Chipster
    Jul 20 '20 at 23:23
8
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ This is a very good answer. I am not sure it is the optimal answer. $\endgroup$
    – Jiminion
    Jul 20 '20 at 17:46
  • $\begingroup$ @Jiminion Me neither. There might be some other method of grouping them that works better. $\endgroup$ Jul 20 '20 at 18:12
  • $\begingroup$ I am thinking a Hamming error code type of thing, that may be better, but I can't be sure of that. $\endgroup$
    – Jiminion
    Jul 21 '20 at 18:36
  • $\begingroup$ I am now thinking your answer is probably optimal. $\endgroup$
    – Jiminion
    Jul 22 '20 at 1:08
  • 1
    $\begingroup$ @Quuxplusone It answers the question that was asked: If there is exactly one working vaccine, identify it. If there is more than one vaccine, detect that but without needing to identify a working one. $\endgroup$ Aug 28 '20 at 19:14
6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I think the way to look at the second part is with your first test, you only indicate which numbers are 'on', but not necessarily if they are 'off'. If you added more tests to clarify the 'off's, then more information would be provided that would be useful. $\endgroup$
    – Jiminion
    Jul 22 '20 at 1:12
  • $\begingroup$ Wait, is the answer not 10 tests? Did I misunderstand the question? $\endgroup$
    – Spandan
    Jul 22 '20 at 6:22
  • $\begingroup$ You shouldn't have the answer in the comment. And no, that is not the answer because it does not distinguish if one and only one vaccine is working. $\endgroup$
    – Jiminion
    Jul 22 '20 at 17:58
  • $\begingroup$ Oh, my mistake. I thought you were asking two separate questions, not one question with two conditions. $\endgroup$
    – Spandan
    Jul 22 '20 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.