|
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!
|
Braavos36390 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...
|
Correct~~!
But using that formula asta posted is almost cheating-.,-
Also, the formula doesn't at all require large n since the taylor expansion for 1/e converges amazingly fast. In the problem I said "a large number of rapists". You get 2 correct decimals already at n=5, and with n=20 you get 18 correct decimals.
|
On February 20 2008 04:25 Cascade wrote:Show nested quote +On February 20 2008 02:52 clazziquai wrote: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...
What he means is that he solved all the problems in threads like these.
|
+ Show Spoiler +0%, because now his fingerprints are all over the samples. they probably set up "connections" for every suspect. and anyone innocent wouldn't touch them.
too easy.
one giveaway is the fact that it's a "large number" of rapists. you should give a number of rapists like 100 or something.
|
........
The fact that the actual number of rapists doesn't matter is what makes it interesting -_-
|
It makes me happy to see that my blog has inspired other people to post up cool math problems. We should create a TL math ring :D
|
man this is waaaaaaay harder than what i thought. I hate these theoretical probablility problems.
|
this is called derangement
|
Last time it was prisoners, now its rapist...
I like using prisoners moar.
|
On February 21 2008 20:54 dinmsab wrote:
Last time it was prisoners, now its rapist...
I like using prisoners moar.
haha, next time slithe and I will construct a prison rape math problem!
|
And yeah by request, here is a complete solution, pretty carefully explained. If you are not really into math but would like to know a little-> hit the spoiler buttons!
Ok, let's say there are n rapists, although this won't really matter.
The blood samples are can be labeled in N0:=n! ways.
In how many of these cases does atleast 1 label get the right bloodsample?
N1:=n*(n-1)! = n!
+ Show Spoiler +first pick 1 of the rapists. Can do that in n ways, Say he got connected with his own bloodsample. Then randomly map the others names into samples in (n-1)! ways
And more generally. In how many cases does atleast i rapists get connected with the right sample?
Ni:=(n over i)*(n-i)!=n!/i!
+ Show Spoiler +choosing first i from the rapists and giving them the right sample connection. Then randomly distributing the others. So this is the number of ways that could be done.
Now simply by the principle of inclusion/exclusion, N:=number of ways that nobody is connected with his own sample is:
N=N0-N1+N2-N3+...(-1)^i*Ni+...Nn
+ Show Spoiler +This might be hard to grasp if you havn't seen it before, but it's a fun concept so I'll explain it briefly. There are totally N0 ways. But then we counted too many, so we remove those cases where 1 guy (or more) got the right sample -> -N1. But then we counted too too few, because we took away some cases twice or more. So we have to add N2 and so on. Well might still be hard to see. Let's have a quick example. + Show Spoiler [example] +
25 people on tl.net:
12 plays starcraft
8 plays wc3
9 plays wow
4 plays sc and wc3
3 plays wc3 and wow
3 plays sc and wow
1 plays sc wc3 and wow
So of the 25, how many doesn't play?
One way of calculating this would be 25-(12+8+9)+(4+3+3)-1=5
Simple to understand if you think about it. Or draw venn diagrams.
Ok, if you convinced yourself, let's draw calculate the probability in the original question. p:=probability that no rapist is matched with his own sample=
N/N0=N/n!=1-1+1/2!-1/3!+1/4!-...+(-1)^n *1/n!
If you had kept going forever without stopping at the n:th term you have the taylor expansion for e^-1 exactly.
+ Show Spoiler +In case you are not familiar with taylor expansions, this is a way to express (almost) any function as a infinite polynomial. This is done by constructing the polynomial so that it's function value and all power-derivatives have the same value for some point.
Taylor expansion for e can be calculated to
e^x=1+x/1!+x^2/2!+...+x^i/i!+...
using the point zero.
(wiki for taylor expansion)
Now take x=-1 to get the exact formula we were stuck with above!
so p=~1/e. The more terms we have in the expansion the closer we will get. Since the sum is alternating with decreasing terms it's simple to show that error=|p-1/x|<1/(n+1)!
So 20 rapists would give a smaller error from 1/e than 1/21!=extremy little.
Wow, this looks a lot more complex then it really is, hope I don't scare away some hs students from math If you take math at university it all comes step by step, and it's not really hard at all.
Cheers!
|
|
|
|
|
|
EPT![[image loading]](http://upload.wikimedia.org/math/6/c/7/6c78e65d3203726f3d03c2501a9649f6.png)
