| Blogs > jtan |
|
jtan
Sweden5891 Posts
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. | ||
|
FirstBorn
Romania3955 Posts
On February 20 2008 04:25 Cascade wrote: 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. | ||
|
gwho
United States632 Posts
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. | ||
|
jtan
Sweden5891 Posts
The fact that the actual number of rapists doesn't matter is what makes it interesting -_- | ||
|
Slithe
United States985 Posts
| ||
|
thoraxe
United States1449 Posts
| ||
|
imDerek
United States1944 Posts
| ||
|
dinmsab
Malaysia2246 Posts
I like using prisoners moar. | ||
|
jtan
Sweden5891 Posts
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! | ||
|
jtan
Sweden5891 Posts
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! | ||
| ||
StarCraft 2 StarCraft: Brood War Dota 2 League of Legends Other Games |
|
HomeStory Cup
Replay Cast
HomeStory Cup
Replay Cast
Replay Cast
Wardi Open
WardiTV Invitational
The PondCast
WardiTV Invitational
|
|
|
EPT
