• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 12:46
CEST 18:46
KST 01:46
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
RSL Season 1 - Final Week6[ASL19] Finals Recap: Standing Tall12HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0
Community News
Firefly given lifetime ban by ESIC following match-fixing investigation17$25,000 Streamerzone StarCraft Pro Series announced7Weekly Cups (June 30 - July 6): Classic Doubles7[BSL20] Non-Korean Championship 4x BSL + 4x China10Flash Announces Hiatus From ASL82
StarCraft 2
General
The GOAT ranking of GOAT rankings RSL Revival patreon money discussion thread Weekly Cups (June 30 - July 6): Classic Doubles Server Blocker RSL Season 1 - Final Week
Tourneys
WardiTV Mondays RSL: Revival, a new crowdfunded tournament series Sparkling Tuna Cup - Weekly Open Tournament FEL Cracov 2025 (July 27) - $8000 live event $5,100+ SEL Season 2 Championship (SC: Evo)
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
External Content
Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma
Brood War
General
Flash Announces Hiatus From ASL [ASL19] Finals Recap: Standing Tall BGH Auto Balance -> http://bghmmr.eu/ BW General Discussion A cwal.gg Extension - Easily keep track of anyone
Tourneys
[Megathread] Daily Proleagues 2025 ACS Season 2 Qualifier Small VOD Thread 2.0 Last Minute Live-Report Thread Resource!
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Path of Exile CCLP - Command & Conquer League Project The PlayStation 5 Nintendo Switch Thread
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread Summer Games Done Quick 2025! Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine The Accidental Video Game Porn Archive
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Movie Discussion! [Manga] One Piece Anime Discussion Thread [\m/] Heavy Metal Thread
Sports
2024 - 2025 Football Thread Formula 1 Discussion NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
Men Take Risks, Women Win Ga…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 747 users

Rapists math problem

Blogs > jtan
Post a Reply
Normal
jtan
Profile Blog Joined April 2003
Sweden5891 Posts
February 19 2008 16:31 GMT
#1
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!

*****
Enter a Uh
Hot_Bid
Profile Blog Joined October 2003
Braavos36374 Posts
February 19 2008 16:35 GMT
#2
lol... rape.
@Hot_Bid on Twitter - ESPORTS life since 2010 - http://i.imgur.com/U2psw.png
fanatacist
Profile Blog Joined August 2007
10319 Posts
February 19 2008 16:39 GMT
#3
Wtf? Wouldn't one of the tainted blood samples still be in the bunch? So one would still be guilty? Can you please clarify.
Peace~
indecision
Profile Blog Joined November 2004
Germany818 Posts
February 19 2008 16:54 GMT
#4
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.
jtan
Profile Blog Joined April 2003
Sweden5891 Posts
Last Edited: 2008-02-19 16:55:36
February 19 2008 16:54 GMT
#5
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.
Enter a Uh
infinity21 *
Profile Blog Joined October 2006
Canada6683 Posts
February 19 2008 17:39 GMT
#6
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
Official Entusman #21
Cascade
Profile Blog Joined March 2006
Australia5405 Posts
Last Edited: 2008-02-19 17:50:47
February 19 2008 17:42 GMT
#7
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.
BluzMan
Profile Blog Joined April 2006
Russian Federation4235 Posts
Last Edited: 2008-02-19 17:57:09
February 19 2008 17:50 GMT
#8
I'll randomly say that it's + Show Spoiler +
1/2
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 ^^
You want 20 good men, but you need a bad pussy.
clazziquai
Profile Blog Joined October 2007
6685 Posts
February 19 2008 17:52 GMT
#9
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?
#1 Sea.Really Fan / #1 Nesh Fan / Terran Forever~
Caller
Profile Blog Joined September 2007
Poland8075 Posts
February 19 2008 17:52 GMT
#10
100% they all raped the same girl duhhhhh
Watch me fail at Paradox: http://www.teamliquid.net/forum/viewmessage.php?topic_id=397564
jtan
Profile Blog Joined April 2003
Sweden5891 Posts
February 19 2008 17:52 GMT
#11
Nope.

Try again!
Enter a Uh
joohyunee
Profile Blog Joined May 2005
Korea (South)1087 Posts
February 19 2008 17:56 GMT
#12
he should've just mixed all the blood samples --;;

would've been gg.
jtan
Profile Blog Joined April 2003
Sweden5891 Posts
February 19 2008 18:00 GMT
#13
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.
Enter a Uh
Cascade
Profile Blog Joined March 2006
Australia5405 Posts
Last Edited: 2008-02-19 18:38:17
February 19 2008 18:29 GMT
#14
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.
Asta
Profile Joined October 2002
Germany3491 Posts
February 19 2008 18:41 GMT
#15
+ Show Spoiler +
[image loading]
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.
Muirhead
Profile Blog Joined October 2007
United States556 Posts
February 19 2008 19:05 GMT
#16
This is a very famous/known result of Euler.
starleague.mit.edu
jtan
Profile Blog Joined April 2003
Sweden5891 Posts
February 19 2008 19:06 GMT
#17
I want a numeric value, not a function of n as an answer. So recursive functions would probably just complicate things.
Enter a Uh
jtan
Profile Blog Joined April 2003
Sweden5891 Posts
February 19 2008 19:09 GMT
#18
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
Enter a Uh
Cascade
Profile Blog Joined March 2006
Australia5405 Posts
February 19 2008 19:20 GMT
#19
+ 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.
Cascade
Profile Blog Joined March 2006
Australia5405 Posts
February 19 2008 19:25 GMT
#20
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...
jtan
Profile Blog Joined April 2003
Sweden5891 Posts
February 19 2008 19:35 GMT
#21
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.
Enter a Uh
FirstBorn
Profile Blog Joined March 2007
Romania3955 Posts
February 19 2008 21:27 GMT
#22
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.
SonuvBob: Yes, the majority of TL is college-aged, and thus clearly stupid.
gwho
Profile Blog Joined January 2008
United States632 Posts
Last Edited: 2008-02-19 21:33:30
February 19 2008 21:30 GMT
#23
+ 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.
jtan
Profile Blog Joined April 2003
Sweden5891 Posts
February 19 2008 22:21 GMT
#24
........

The fact that the actual number of rapists doesn't matter is what makes it interesting -_-
Enter a Uh
Slithe
Profile Blog Joined February 2007
United States985 Posts
February 19 2008 22:31 GMT
#25
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
thoraxe
Profile Blog Joined March 2007
United States1449 Posts
February 19 2008 23:55 GMT
#26
man this is waaaaaaay harder than what i thought. I hate these theoretical probablility problems.
Obama singing "Kick Ass" Song: http://www.youtube.com/watch?v=yghFBt-fXmw&feature=player_embedde
imDerek
Profile Blog Joined August 2007
United States1944 Posts
February 20 2008 02:24 GMT
#27
this is called derangement
Least favorite progamers: Leta, Zero, Mind, Shine, free, really <-- newly added
dinmsab
Profile Blog Joined January 2008
Malaysia2246 Posts
February 21 2008 11:54 GMT
#28
Last time it was prisoners, now its rapist...

I like using prisoners moar.
..
jtan
Profile Blog Joined April 2003
Sweden5891 Posts
February 23 2008 17:16 GMT
#29
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!
Enter a Uh
jtan
Profile Blog Joined April 2003
Sweden5891 Posts
February 23 2008 18:09 GMT
#30
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!
Enter a Uh
Normal
Please log in or register to reply.
Live Events Refresh
FEL
15:00
Polish Championship - Playoffs
Spirit vs Gerald
Elazer vs MaNa
IndyStarCraft 387
CranKy Ducklings239
Liquipedia
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
IndyStarCraft 387
Hui .229
BRAT_OK 121
trigger 33
MindelVK 12
StarCraft: Brood War
EffOrt 1771
Larva 716
firebathero 598
Mini 353
Dewaltoss 110
Shinee 71
Barracks 69
Aegong 51
GoRush 49
Movie 41
[ Show more ]
Terrorterran 31
Stormgate
BeoMulf114
Dota 2
Gorgc12248
qojqva2846
League of Legends
Dendi1304
Counter-Strike
fl0m231
flusha163
Heroes of the Storm
Khaldor923
Liquid`Hasu452
Other Games
FrodaN10701
singsing2432
B2W.Neo1483
KnowMe273
RotterdaM158
mouzStarbuck126
Rex19
Organizations
Other Games
EGCTV1918
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 14 non-featured ]
StarCraft 2
• HeavenSC 54
• Adnapsc2 22
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• Ler114
League of Legends
• Nemesis5770
Upcoming Events
BSL20 Non-Korean Champi…
1h 14m
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
Wardi Open
18h 14m
Replay Cast
1d 17h
WardiTV European League
1d 23h
PiGosaur Monday
2 days
uThermal 2v2 Circuit
2 days
Replay Cast
3 days
The PondCast
3 days
Replay Cast
4 days
Epic.LAN
4 days
[ Show More ]
CranKy Ducklings
5 days
Epic.LAN
5 days
BSL20 Non-Korean Champi…
6 days
Bonyth vs Sziky
Dewalt vs Hawk
Hawk vs QiaoGege
Sziky vs Dewalt
Mihu vs Bonyth
Zhanhun vs QiaoGege
QiaoGege vs Fengzi
Sparkling Tuna Cup
6 days
Online Event
6 days
Liquipedia Results

Completed

KCM Race Survival 2025 Season 2
HSC XXVII
NC Random Cup

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
2025 ACS Season 2: Qualifier
BSL20 Non-Korean Championship
Championship of Russia 2025
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters

Upcoming

CSL Xiamen Invitational
CSL Xiamen Invitational: ShowMatche
2025 ACS Season 2
CSLPRO Last Chance 2025
CSLPRO Chat StarLAN 3
BSL Season 21
K-Championship
RSL Revival: Season 2
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
Underdog Cup #2
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.