Thread: Pandemic-X
View Single Post
Old 2020-02-26, 04:56   #2
retina's Avatar
"The unspeakable one"
Jun 2006
My evil lair

2×34×37 Posts

Originally Posted by a1call View Post
* Planet-A has a population of 95 people.
* Pandemic-X is in the process of breaking out across the planet
* An unknown number of individuals are infected by Virus-X
* There is a shortage of Test-Kits and not everyone can be tested
* Fluid samples from any number of individuals can be combined and tested per a single Test-Kit
** If any of the combining individual are infected the test will be positive else negative

* What is the minimum number of Kits required to determine who is infected and who is not?

*** Spoiler alert: I have no idea what the answer is, but I think this is a useful problem to figure out given the current affairs of the Planet-Earth

Thank you for your time and insights.
ETA I assume the answer would be a function of number/proportion of the infected individuals.
Because we have no way of knowing in advance how many are infected, and all we know is it is one or more, then I suspect you can't do better than one test per person. In the case of all persons are infected there is no method of combinations that will prove each person is infected, you have to test each case one-by-one. Only if you have the really fortunate case of happening to divide all non-infected cases into a single test can you have the possibility of reducing the tests needed.

This puzzle might be more interesting if you state in advance the number of infected people. Then you can devise a test plan to minimise the total number of tests.

Last fiddled with by retina on 2020-02-26 at 04:57
retina is online now   Reply With Quote