mersenneforum.org Pandemic-X
 Register FAQ Search Today's Posts Mark Forums Read

 2020-02-26, 03:54 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22×487 Posts Pandemic-X * 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. Last fiddled with by a1call on 2020-02-26 at 04:30
2020-02-26, 04:56   #2
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

3·13·151 Posts

Quote:
 Originally Posted by a1call * 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

 2020-02-26, 05:54 #3 axn     Jun 2003 112658 Posts
 2020-02-26, 06:08 #4 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22·487 Posts Brilliant indeed, thank you. Good to know the algorithm is useful and already in use for the purpose. ETA not sure though if the algorithm was used in case of the Cruse ship off the coast of Japan for example. Last fiddled with by a1call on 2020-02-26 at 06:11
2020-02-26, 06:18   #5
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

134018 Posts

Quote:
 Originally Posted by a1call Good to know the algorithm is useful and already in use for the purpose.
It is only useful if you know in advance the percentage of expected positive/negative results. So be careful how and where you apply it. You can end up with more work overall.

One way to approach this is to sample a small population first with individual tests to obtain an approximate percentage and then apply some statistical methods to reduce the number subsequent tests. This would require good unbiased selection criteria to start with.

 2020-02-26, 10:04 #6 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22·487 Posts Something bothers me about that video. There is a logical symmetry/interchangable-ity between infected and non-infected individuals. If the algorithm requires n tests for say 20% infected then it should require exactly n tests for 100%-20%=80%. Shouldn't it? Then the claim that above 30% infection rates will require more tests than number of individuals is false. Corrections are appreciated.
 2020-02-26, 10:49 #7 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 111100111002 Posts Nevermind, I see my mistake. Out is not symmetrical. Since 1 infection per batch will give positive but -1 infection per batch will not give negative result. Last fiddled with by a1call on 2020-02-26 at 10:53
2020-02-28, 07:29   #8
moebius

Jul 2009
Germany

461 Posts

Quote:
 Originally Posted by a1call * 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?
It's simple Logik, minimum number is 1 Test-Kit, in the case
the unknown number of individuals are infected by Virus-X = 0.
Just combine all fluid samples from the 95 people.

In the case the unknown number of individuals are infected by Virus-X > 0.
you need a minimum amount of 2 test-kits. In this case the first test is positive.
With the second test kit you have to test the remaining 94 People. Number of Infections = 1.

easy to extend to an algorithm....

Last fiddled with by moebius on 2020-02-28 at 07:57 Reason: erweiterte LĂ¶sung

2020-04-03, 03:47   #9
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

22×487 Posts

For reference purposes:

Quote:
 Originally Posted by R. Gerbicz https://medium.com/@dinber19/more-wi...s-8ba1a2cd8b67 https://www.medrxiv.org/content/10.1....26.20039438v1 Pretty trivial, I guessed the method after I have first read only the lead of a similar article in Hungarian that we could easily test ten millions in a few days and the number 64.

2020-04-03, 09:50   #10
LaurV
Romulan Interpreter

Jun 2011
Thailand

214038 Posts

Quote:
 Originally Posted by axn .
Given the initial problem, 1000, 10%, we can do better! (even if you don't know the exact quantity of the poisoned glasses).
If you know there are exactly 100 glasses poisoned from 1000, you can do even better-better than in the video, and than in the case above.

Last fiddled with by LaurV on 2020-04-03 at 09:52