These forums have been archived and are now read-only.

The new forums are live and can be found at https://forums.eveonline.com/

Out of Pod Experience

 
  • Topic is locked indefinitely.
 

Brainteaser time !
Author
Previous Topic Next Topic
Akita T
Caldari Navy Volunteer Task Force
#1 - 2011-11-06 15:15:55 UTC
Here's a quickie for you.

It's Friday morning. You are the lead lab tech for a cosmetics company.
One (just one, you are absolutely sure it was just one) of your last 787 batches of product has been tainted with a nearly undetectable and 100% lethal poison that kills within a day or two all of a sudden, with barely any indication of illness beforehand even after minimal exposure.
Your bosses want to ship out all non-tainted products first thing Monday morning, and you are tasked with identifying the tainted batch.
You only have 10 live lab specimens you are allowed to experiment on.
This basically means you only get one experiment, since there's no time for a repeat.

Disclaimer : The bosses could care less whether they )the lab specimens) live or die, and since you're pretty sure you're going to lose your job, your mortgaged house, wife will divorce you and take the kids etc you also don't really care how many of these animals die in the process even if you normally just loooove animals. Oh, and the animals are convicted murderers or something, and they want to die or whatever. Just go with it, they totally both deserve and want to die or will be reborn in a better place or whatever is needed for you to not care whether they survive your experiment or not.

Devise your experiment. Murderer. And decide with complete accuracy which batch was the tainted one.

Twisted

Akita T evewiki profile | | | Build your own EVE-ready PC
stoicfaux
#2 - 2011-11-06 15:57:33 UTC
You do what the US military did during WWII when testing for STDs (aka VDs aka sexually transmitted disease.) Since running a test on each individual's sample was expensive and time consuming, they mixed several samples (say 10) together and tested the batch. If that combined batch showed positive, then they re-tested the 10 men individually to find the infected person(s).

The statisticians ran the math behind it to determine the optimum sample size given an expected frequency of infection.


In this case you would do a binary search to find the bad batch.
Test a combined batch of 1-394.
If it's positive then test a combined batch of 1-197. If it's negative then test a combined batch 395-591.
Rinse and repeat until you're down to one sample.


In reality, I would document everything, and either claim whistleblower status or blackmail the company into giving you a nice severance package in order to keep me from going to the press with the story and crashing the company's market share.

Pon Farr Memorial: once every 7 years, all the carebears in high-sec must PvP or they will be temp-banned.
Akita T
Caldari Navy Volunteer Task Force
#3 - 2011-11-06 18:24:40 UTC  |  Edited by: Akita T
The catch here is that you only have time for ONE test, not several.

This means you have to subject the specimens to whatever combination of samples from whatever batches you want, you only have 10 specimens to subject to whatever mixes of those you prepare, then you need to wait 2 days, get the results, then immediately say "batch X of 787 is contaminated".

stoicfaux wrote:
In this case you would do a binary search to find the bad batch.
Test a combined batch of 1-394.
If it's positive then test a combined batch of 1-197. If it's negative then test a combined batch 395-591.
Rinse and repeat until you're down to one sample.


You can't test half of them on one subject, then after you get the results from that test some more, and so on.
You have no time for that. You need to do it ALL in a SINGLE go.

The trick is how to determine the mixing of samples from batches to administer to each of the 10 test subjects, and how to determine which batch was the bad one after you get the 10 alive/died results 2 days later.

Akita T evewiki profile | | | Build your own EVE-ready PC
Taedrin
Federal Navy Academy
Gallente Federation
#4 - 2011-11-06 22:42:50 UTC  |  Edited by: Taedrin
Let's see:
1) 787 different items to test
2) 10 test subjects
3) Algorithm must be completed in O(1) time.

Here's how you do it:

Test batch #1 on Subject #1
Test batch #2 on Subject #2
Test batch #3 on Subject #2 and subject #1
Test batch #4 on Subject #3
Test batch #5 on subjects #3 and #1
Test batch #6 on subjects #3 and #2

so on and so forth.

EDIT:
Batch #787 will be tested on:
#1, #2, #5, #9, #10

Theoretically, we could go all the way up to 2^10 - 1 number of batches and succeed.

I DON'T UNDERSTAND EXPLANATION:
I am converting the batch # into a binary number, which just so happens to be able to be uniquely represented with 10 bits. We use our test subjects as bits. If a test subject dies, we mark that bit as a "1".

FOR EXAMPLE, if batch #256 us tainted, then subject #9 will die and no one else. If batch #255 is tainted, then subjects #1-#8 will die.
Akita T
Caldari Navy Volunteer Task Force
#5 - 2011-11-07 01:25:19 UTC
Heh, that was relatively fast Blink
I need to give you guys harder brainteasers P

Akita T evewiki profile | | | Build your own EVE-ready PC
Taedrin
Federal Navy Academy
Gallente Federation
#6 - 2011-11-07 01:55:07 UTC  |  Edited by: Taedrin
Akita T wrote:
Heh, that was relatively fast Blink
I need to give you guys harder brainteasers P


Well, you made me think. I was initially thinking about if there was a way to generating 10 sets of unique combinations of tests - 1 for each test subject such that the intersection of any combination of sets always yielded at most a singleton set. I had to sit there for awhile until I had my "aha!" moment while looking at the number 787 wondering if it was significant or not. As a computer science student, I immediately noticed that 787 was NOT close to any powers of 2 - which is probably why you picked this number so that the answer wouldn't be easily apparent.

Unfortunately, by this time the damage had already been done - simply THINKING about the powers of 2 led me to binary numbers, which made me realize that 787 is less than 2^10 and could thus be represented as a binary number.

In hind sight, my original idea was not incorrect - by mapping the batch number to a binary representation using the test subjects DOES in fact create 10 sets of unique batteries of tests to be performed on the tests subjects. If you take the intersection of which ever sets results in a dead test subject, the intersection will be the singleton set containing the batch number which was represented by our 'binary number'.
Akita T
Caldari Navy Volunteer Task Force
#7 - 2011-11-07 14:44:08 UTC
Taedrin wrote:
I immediately noticed that 787 was NOT close to any powers of 2 - which is probably why you picked this number so that the answer wouldn't be easily apparent.

And it's also a prime number, to give one extra false lead "just in case" Blink

Akita T evewiki profile | | | Build your own EVE-ready PC
Nova Fox
Novafox Shipyards
#8 - 2011-11-07 15:01:04 UTC
You only need one person to live.

Dust 514's CPM 1 Iron Wolf Saber Eve mail me about Dust 514 issues.
Green Beans
R and J Inc.
#9 - 2011-11-09 03:25:37 UTC
Taedrin wrote:
Let's see:
1) 787 different items to test
2) 10 test subjects
3) Algorithm must be completed in O(1) time.

Here's how you do it:

Test batch #1 on Subject #1
Test batch #2 on Subject #2
Test batch #3 on Subject #2 and subject #1
Test batch #4 on Subject #3
Test batch #5 on subjects #3 and #1
Test batch #6 on subjects #3 and #2

so on and so forth.

EDIT:
Batch #787 will be tested on:
#1, #2, #5, #9, #10

Theoretically, we could go all the way up to 2^10 - 1 number of batches and succeed.

I DON'T UNDERSTAND EXPLANATION:
I am converting the batch # into a binary number, which just so happens to be able to be uniquely represented with 10 bits. We use our test subjects as bits. If a test subject dies, we mark that bit as a "1".

FOR EXAMPLE, if batch #256 us tainted, then subject #9 will die and no one else. If batch #255 is tainted, then subjects #1-#8 will die.


How long did it take you to come up with that?!?

This line for rent! YOUR AD HERE!

Taedrin
Federal Navy Academy
Gallente Federation
#10 - 2011-11-09 03:31:11 UTC
Green Beans wrote:
Taedrin wrote:
Let's see:
1) 787 different items to test
2) 10 test subjects
3) Algorithm must be completed in O(1) time.

Here's how you do it:

Test batch #1 on Subject #1
Test batch #2 on Subject #2
Test batch #3 on Subject #2 and subject #1
Test batch #4 on Subject #3
Test batch #5 on subjects #3 and #1
Test batch #6 on subjects #3 and #2

so on and so forth.

EDIT:
Batch #787 will be tested on:
#1, #2, #5, #9, #10

Theoretically, we could go all the way up to 2^10 - 1 number of batches and succeed.

I DON'T UNDERSTAND EXPLANATION:
I am converting the batch # into a binary number, which just so happens to be able to be uniquely represented with 10 bits. We use our test subjects as bits. If a test subject dies, we mark that bit as a "1".

FOR EXAMPLE, if batch #256 us tainted, then subject #9 will die and no one else. If batch #255 is tainted, then subjects #1-#8 will die.


How long did it take you to come up with that?!?


About 15 minutes.