• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 04:01
CEST 10:01
KST 17:01
  • 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
[ASL19] Finals Recap: Standing Tall10HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy6
Community News
Firefly given lifetime ban by ESIC following match-fixing investigation5$25,000 Streamerzone StarCraft Pro Series announced4Weekly Cups (June 30 - July 6): Classic Doubles6[BSL20] Non-Korean Championship 4x BSL + 4x China9Flash Announces Hiatus From ASL66
StarCraft 2
General
Weekly Cups (June 30 - July 6): Classic Doubles The SCII GOAT: A statistical Evaluation The GOAT ranking of GOAT rankings Firefly given lifetime ban by ESIC following match-fixing investigation Jim claims he and Firefly were involved in match-fixing
Tourneys
$25,000 Streamerzone StarCraft Pro Series announced FEL Cracov 2025 (July 27) - $8000 live event Sparkling Tuna Cup - Weekly Open Tournament RSL: Revival, a new crowdfunded tournament series WardiTV Mondays
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
[UMS] Zillion Zerglings
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
i aint gon lie to u bruh... ASL20 Preliminary Maps BGH Auto Balance -> http://bghmmr.eu/ [ASL19] Finals Recap: Standing Tall SC uni coach streams logging into betting site
Tourneys
[BSL20] Non-Korean Championship 4x BSL + 4x China [BSL20] Grand Finals - Sunday 20:00 CET CSL Xiamen International Invitational The Casual Games of the Week Thread
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Path of Exile What do you want from future RTS games? Beyond All Reason
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
Things Aren’t Peaceful in Palestine US Politics Mega-thread Summer Games Done Quick 2025! Russo-Ukrainian War Thread Stop Killing Games - European Citizens Initiative
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [\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
momentary artworks from des…
tankgirl
Culture Clash in Video Games…
TrAiDoS
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Customize Sidebar...

Website Feedback

Closed Threads



Active: 619 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
Next event in 1h 59m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
JimRising 535
trigger 23
StarCraft: Brood War
TY 486
Shuttle 438
Zeus 353
actioN 285
Stork 173
Larva 160
Leta 124
PianO 117
ToSsGirL 61
Noble 46
[ Show more ]
Yoon 46
sSak 42
Sacsri 25
Nal_rA 21
yabsab 19
Sharp 13
IntoTheRainbow 1
Dota 2
XaKoH 549
XcaliburYe319
Fuzer 182
Counter-Strike
Stewie2K850
Other Games
shahzam1238
monkeys_forever219
Happy148
ceh9106
crisheroes59
Organizations
Other Games
gamesdonequick35128
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 16 non-featured ]
StarCraft 2
• Berry_CruncH384
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• tankgirl 2
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota2154
League of Legends
• Lourlo1540
• Stunt548
• HappyZerGling96
Upcoming Events
The PondCast
1h 59m
uThermal 2v2 Circuit
7h 59m
WardiTV European League
7h 59m
Jumy vs NightPhoenix
Percival vs Nicoract
ArT vs HiGhDrA
MaxPax vs Harstem
Scarlett vs Shameless
SKillous vs uThermal
Replay Cast
15h 59m
RSL Revival
1d 1h
ByuN vs SHIN
Clem vs Reynor
OSC
1d 4h
Replay Cast
1d 15h
RSL Revival
2 days
Classic vs Cure
FEL
2 days
OSC
2 days
[ Show More ]
RSL Revival
3 days
FEL
3 days
FEL
3 days
CSO Cup
3 days
BSL20 Non-Korean Champi…
3 days
Bonyth vs QiaoGege
Dewalt vs Fengzi
Hawk vs Zhanhun
Sziky vs Mihu
Mihu vs QiaoGege
Zhanhun vs Sziky
Fengzi vs Hawk
Sparkling Tuna Cup
4 days
RSL Revival
4 days
FEL
4 days
BSL20 Non-Korean Champi…
4 days
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
Replay Cast
6 days
Liquipedia Results

Completed

Proleague 2025-07-07
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
KCM Race Survival 2025 Season 2
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
Championship of Russia 2025
RSL Revival: Season 1
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
CCT Season 2 Global Finals
IEM Melbourne 2025

Upcoming

2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
CSL Xiamen Invitational
2025 ACS Season 2
CSLPRO Chat StarLAN 3
K-Championship
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.