20200226, 03:54  #1 
"Rashid Naimi"
Oct 2015
Remote to Here/There
11111000000_{2} Posts 
PandemicX
* PlanetA has a population of 95 people.
* PandemicX is in the process of breaking out across the planet * An unknown number of individuals are infected by VirusX * There is a shortage of TestKits and not everyone can be tested * Fluid samples from any number of individuals can be combined and tested per a single TestKit ** 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 PlanetEarth 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 20200226 at 04:30 
20200226, 04:56  #2  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
59×103 Posts 
Quote:
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 20200226 at 04:57 

20200226, 05:54  #3 
Jun 2003
2^{3}·607 Posts 

20200226, 06:08  #4 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{6}×31 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 20200226 at 06:11 
20200226, 06:18  #5  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6077_{10} Posts 
Quote:
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. 

20200226, 10:04  #6 
"Rashid Naimi"
Oct 2015
Remote to Here/There
7C0_{16} Posts 
Something bothers me about that video. There is a logical symmetry/interchangableity between infected and noninfected 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. 
20200226, 10:49  #7 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{6}·31 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 20200226 at 10:53 
20200228, 07:29  #8  
Jul 2009
Germany
547 Posts 
Quote:
the unknown number of individuals are infected by VirusX = 0. Just combine all fluid samples from the 95 people. In the case the unknown number of individuals are infected by VirusX > 0. you need a minimum amount of 2 testkits. 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 20200228 at 07:57 Reason: erweiterte LĂ¶sung 

20200403, 03:47  #9  
"Rashid Naimi"
Oct 2015
Remote to Here/There
3700_{8} Posts 
For reference purposes:
Quote:


20200403, 09:50  #10 
Romulan Interpreter
Jun 2011
Thailand
2^{3}·19·61 Posts 
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 betterbetter than in the video, and than in the case above. Last fiddled with by LaurV on 20200403 at 09:52 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Manic of a panic is geopolitical  a1call  Lounge  1319  20210228 00:17 