the blood test riddle (number theory)

Question

A microbiologist has been given a set of $100$ blood vials. Exact one of those $100$ vials is positive to a concrete disease X. The microbiologist desires to send only $7$ vials for analysis. He can mix as many samples as he wants into $1$ vial. Which and how many samples should contain every to-be-sent-for-analysis vial so the microbiologist can determine which of $100$ vials contains the contagious blood?

Caution: All $7$ vials are supposed to be sent at once! (So binary search is not an option.)

Tip: The binary representation of $100$ is
$1\cdot64 + 1\cdot32 + 1\cdot4 = 1\cdot2^6 + 1\cdot2^5 + 0\cdot2^4 + 0\cdot2^3 + 1\cdot2^2 + 0\cdot2^1 + 0\cdot2^0=\\ = (1100100)_2$

Answer 1

Do you already know the answer to this question? You really should indicate that if you do.

I presume the microbiologist determines the $7$-bit representation of the sample number, and sends all samples with the highest-order bit set into vial $1$, the second-highest-order bit into vial $2$, and so on, with those samples with the lowest-order bit set into vial $7$. This presumes that each sample can be divided into at least $6$ parts that are sufficient for analysis. (There are fewer than $2^7-1 = 127$ samples, so there are no samples that will be put into all $7$ vials.)

ETA: Let me elaborate on how to interpret the results. Suppose that the results come back and vials $2$, $5$, and $6$ are positive for Disease X. Then we write out the $7$-bit binary number with $1$ in the second, fifth, and sixth position: $0100110$. That is equal to $2^5+2^2+2^1 = 32+4+2 = 38$, so the $38$th sample was the one positive for Disease X.

Answer 2

1. Imagine for now that instead of 100, we had 128 blood vials to begin with [the number is easier as it its the 7th power of 2 [lets pretend the 28 last ones are empty]

2. Let us assume that we line them up and label them from left to right with tags 1 to 128, one tag per vial, tag label representing position.

3. Let us now take take 7 test vials and poor in blood from the 128 labelled ones in the following way:

Test vial 1: poor in blood from each of 1-64. [assume no blood poored from 65-128].

Test vial 2: poor in blood from 1-32, 65-96 inclussive.

Test vial 3: take blood from 1-16, 33-48, 65-80, 97-112.

Test vial 4: take blood from 1-8, 17-24, 33-40, 49-56, 65-72, 81-88, 97-106, 113-120.

Test vial 5: take blood from 1-4, 9-12, 17-20, 25-28, 33-36, 41-44, 49-52, 57-60, 65-68, 73-76, 81-84, 89-92, 97-100, 105-108, 113-116, 121-124.

Test vial 6: 1-2, 5-6, 9-10, 13-14, 17-18, 21-22, 25-26, 29-30, 33-34, 37-38, 41-42, 45-46, 49-50, 53-54, 57-58, 61-62, 65-66, 69-70, 73-74, 77-78, 81-82, 85-86, 89-90, 93-94, 97-98, 101-102, 105-106, 109-110, 113-114, 117-118, 121-122.

Test vial 7: all the odd numberred ones.

there are 7 test vials, each of which can either test positive or negative. In otherwords, we have 7 binary questions, which means that the number of different results can be 2^7 =128 different outcomes.

The above construction, allows the microbiologist, to infer each outcome, to a unique vial label.

For example: If all 7 vials test positive, then the culprit will be number 1 [see if you can convince yourself that 1 is the only possible culprit. See if you can convince yourself for the remaining 127 outcomes ;) ]

Now I would like to flip back this problem, back to the original poster and ask him or her this:

Can you find a construction, that can determine the culprit with less than 7 test vials? If so, then what is the minimum number of test vials required, in order to reveal the contaminated vial, out of a sample of 100 vials?

The answer is obvious.

But what if the contaminated sample was diluted to a degree which even if contamination was present, the vial will have tested negative because of inefficient equipment [which is the case in real life :) equipment is not 100% efficient at all molarities]

In this case, can we optimise the construction such that less than 7 test vails are required?

Hint:

despite the fact that: 2^x <100 for all x<7

One can find a pair of p and q such that:

2^p . 3^q > 100

where p+q < 7.

For example, what if we assume the following: a contaminated vial will still test negative if it so happens to be diluted to a molarity of less than 1 part in 200.

Many Thanks, Mike.

Answer 3

Number the samples 1-100.

Vial 1: All those with sample number of the form 1xxxxxx in binary

Vial 2: All those with sample number of the form x1xxxxx in binary

Vial 3: All those with sample number of the form xx1xxxx in binary

etc.

Vial 7: All those with sample number of the form xxxxxx1 in binary