|
I just read Slithe's blog and solved one of his problems and they are all quite fun so I thought I'd try this too!
Ok, I think this is a pretty classic problem, and since I don't want you to cheat I'll reformulate it 
So a large number of rapists are sitting in prison while waiting for the DNA-evidence against them to come in. They have all given bloodsamples, and the lab is soon about to compare it with fluids from the respective victims. One of the rapists has some contacts inside the prison administration and manages to get into the evidence room. Here he soon discovers a large box labeled "RAPIST BLOOD" and he eagerly opens it. Inside he finds all the blood samples in test tubes labeled with long numbers.
He hears a guard coming, and in desperation he rips of all the labels, quickly mixes the test tubes, and puts labels back on randomly. He then sneaks back to his cell.
What is the probability that all rapists are found innocent?
Good luck! I hope it's not too hard! If you are confused, just read the text again.
And please don't post solutions you didn't do yourself!
|
Braavos36362 Posts
|
Wtf? Wouldn't one of the tainted blood samples still be in the bunch? So one would still be guilty? Can you please clarify.
|
I think they're only testing if you raped your victim, i.e. if your DNA would only be found on another victim you'll be considered innocent.
|
Like I said in the post, they only compare a rapists blood with his supposed victim.
edit: yeah like indecision said.
And yeah, since I called them rapists, you may assume they are all in fact guilty.
|
infinity21
Canada6683 Posts
Umm I think it depends on the number of rapists >_<
Assuming that each rapist in fact did rape their victims
for n # of rapists
[(n-1)/n]^n chance? :S
|
Solution.
+ Show Spoiler +Let n be the number of rapists. That random guy can relabel the samples in n! different ways. n choices for where to put hte first label, n-1 for the second label, etc.
-----------------flawed------------
In how many ways can he label them such that he doesnt place the right name on any sample?
For the first label, he has n-1 alternatives. Lets say he places the first label on sample number i. Then the label i can go n-1 samples still, since the only one occupied is his own. So label i goes on sample j. Label j now can go n-2 samples, since i is occupied, and j is both occupied and forbidden. etc. Total number of possible "all innocent" labelings becomes
------------------flawed------------
(n-1)(n-1)(n-2)(n-3)...3*2*1 = n! / n <-- wrong
Now we see that the number of "all innocent" labelings is 1/n times as many as the total number of labels from which we can say that the probability of all the rapists going free is 1/n. Seems to fit with brute force for n=2 and n=3.
EDIT: found a flaw. And a misscalcualtion.  sorry, just disregard.
|
Russian Federation4235 Posts
I'll randomly say that it's + Show Spoiler + without calculations.
EDIT: whoo, no, this is quite different. However, the answer is dependent on N then which you didn't provide, thus the task was formulated incorrectly ^^
|
On February 20 2008 02:42 Cascade wrote:Solution. + Show Spoiler +Let n be the number of rapists. That random guy can relabel the samples in n! different ways. n choices for where to put hte first label, n-1 for the second label, etc.
-----------------flawed------------
In how many ways can he label them such that he doesnt place the right name on any sample?
For the first label, he has n-1 alternatives. Lets say he places the first label on sample number i. Then the label i can go n-1 samples still, since the only one occupied is his own. So label i goes on sample j. Label j now can go n-2 samples, since i is occupied, and j is both occupied and forbidden. etc. Total number of possible "all innocent" labelings becomes
------------------flawed------------
(n-1)(n-1)(n-2)(n-3)...3*2*1 = n! / n <-- wrong
Now we see that the number of "all innocent" labelings is 1/n times as many as the total number of labels from which we can say that the probability of all the rapists going free is 1/n. Seems to fit with brute force for n=2 and n=3. EDIT: found a flaw. And a misscalcualtion. sorry, just disregard.
You sound so smart lol. Didn't you solve another really hard math problem earlier? >_>
Is this statistics?
|
100% they all raped the same girl duhhhhh
|
|
|
joohyunee
Korea (South)1087 Posts
he should've just mixed all the blood samples --;;
would've been gg.
|
ok caller just assume they did not gang rape the same girl...
clazzi: no this isn't really statistic, it's more of a simple number theoretic problem. And then you just divide (some cases) with (all cases) to get a probability.
|
ok, I've found a neat method to prove that the answer is correct by induction. Just have to find the right formula now....
Or if answer by a recursive formula is ok, then the answer is:
+ Show Spoiler +let P(n) be the probability of getting n prisoners innocent. Then:
P(n) = 1 - 1/n! - Sum(i goes from 1 to n-1)P(i)/(i!(n-i)!)
Feels like there should be a smarter way to go though. 
|
+ Show Spoiler + is the number of fixed-point-free permutations of n elements (test tubes). Divided by n! (the total number of permutations) that is the probability of 0 fixed points. Guess looking up that number ruined the fun for me. 
|
This is a very famous/known result of Euler.
|
I want a numeric value, not a function of n as an answer. So recursive functions would probably just complicate things.
|
On February 20 2008 04:05 Muirhead wrote:
This is a very famous/known result of Euler.
Yes, Euler was also a rapists who got away with it
|
+ Show Spoiler +Hmm, I realised I was looking for the number of fix point free permutaions, but I wouldnt have found that formula of Asta in a while yet. It agrees with my recursive formula up to 5 anyway, so I'll assume for now that it was correct.
For large n, the probability is
Sum(i from 0 to n)(-1)^i / i! = e^(-1) = 0.367879
as it is exactly the taylor expansion of the exponential function.
|
On February 20 2008 02:52 clazziquai wrote:Show nested quote +On February 20 2008 02:42 Cascade wrote:Solution. + Show Spoiler +Let n be the number of rapists. That random guy can relabel the samples in n! different ways. n choices for where to put hte first label, n-1 for the second label, etc.
-----------------flawed------------
In how many ways can he label them such that he doesnt place the right name on any sample?
For the first label, he has n-1 alternatives. Lets say he places the first label on sample number i. Then the label i can go n-1 samples still, since the only one occupied is his own. So label i goes on sample j. Label j now can go n-2 samples, since i is occupied, and j is both occupied and forbidden. etc. Total number of possible "all innocent" labelings becomes
------------------flawed------------
(n-1)(n-1)(n-2)(n-3)...3*2*1 = n! / n <-- wrong
Now we see that the number of "all innocent" labelings is 1/n times as many as the total number of labels from which we can say that the probability of all the rapists going free is 1/n. Seems to fit with brute force for n=2 and n=3. EDIT: found a flaw. And a misscalcualtion. sorry, just disregard. You sound so smart lol. Didn't you solve another really hard math problem earlier? >_> Is this statistics?
haha, thanks I guess. I've been posting in a few other threads like these yes...
|
|
|
|
|
|
EPT![[image loading]](http://upload.wikimedia.org/math/6/c/7/6c78e65d3203726f3d03c2501a9649f6.png)
