mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-02-26, 03:54   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3·643 Posts
Default 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
a1call is offline   Reply With Quote
Old 2020-02-26, 04:56   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23·727 Posts
Default

Quote:
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
Old 2020-02-26, 05:54   #3
axn
 
axn's Avatar
 
Jun 2003

22×32×131 Posts
Default

axn is offline   Reply With Quote
Old 2020-02-26, 06:08   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3·643 Posts
Default

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
a1call is offline   Reply With Quote
Old 2020-02-26, 06:18   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

10110101110002 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
retina is online now   Reply With Quote
Old 2020-02-26, 10:04   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3·643 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2020-02-26, 10:49   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3·643 Posts
Default

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
a1call is offline   Reply With Quote
Old 2020-02-28, 07:29   #8
moebius
 
moebius's Avatar
 
Jul 2009
Germany

2×3×5×13 Posts
Default

Quote:
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?
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
moebius is online now   Reply With Quote
Old 2020-04-03, 03:47   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3×643 Posts
Default

For reference purposes:

Quote:
Originally Posted by R. Gerbicz View Post
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.
a1call is offline   Reply With Quote
Old 2020-04-03, 09:50   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3·2,957 Posts
Default

Quote:
Originally Posted by axn View Post
.
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
LaurV is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Manic of a panic is geopolitical a1call Lounge 1126 2020-10-27 18:55

All times are UTC. The time now is 04:13.

Wed Oct 28 04:13:19 UTC 2020 up 48 days, 1:24, 2 users, load averages: 1.80, 1.96, 1.90

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.