The unbelievable solution to the 100 prisoner puzzle.

Yes, here is the follow-up video: • My response to being r...
Order Alex Bellos's book now and get a limited-edition 'Matt verified' copy.
mathsgear.co.u...
Thanks to Matt Scroggs and the Chalkdust folks for helping organise the volunteers and the maths.
chalkdustmagazi...
Cheers to the Ri for letting us film in their building.
www.rigb.org/
We have free Think Maths work sheets for any teachers who want to use the prisoner puzzle in their lessons.
think-maths.co....
CORRECTIONS
- Yes, it seems we can’t spell success successfully.
- Turns out we do know there is a limit.
- Let me know if you spot any other mistakes!
Thanks as always for Jane Street being my principal sponsor.
www.janestreet...
Thanks to my Patreon supporters who help make these videos possible. Here is a random subset:
Everett Chouinard
Lucie
Christian Martel
Joost Smits
Rhys Llewellyn
Anthony Allan
Support my channel and I can make more maths videos:
/ standupmaths
Filming and editing by Trunkman Productions
Music by Howard Carter
Design by Simon Wright
MATT PARKER: Stand-up Mathematician
Website: standupmaths.com/
Maths book: wwwh.umble-pi.com
Nerdy maths toys: mathsgear.co.uk/

[@MinutePhysics]

Nicely done! In case you want to see another version of this puzzle/explanation :) kzbin.info/www/bejne/m5rZeJ94gNF-bK8 and kzbin.info/www/bejne/eWaQemOYdtp4i6c

[@johnchessant3012]

Yay! Crossover!

[@hawktitan7896]

Watching sciency KZbin pays off. I knew the answer from watching this previously.

[@black_platypus]

Aaaah, that's where I knew that from!

[@umanglunia2194]

TED-ed had a similar riddle.

[@juliusreiner5733]

I thought I was having deja vu

[@TheRoyalInstitution]

It was a pleasure to host you! Although, next time, maybe a spa retreat for our staff, instead of a prison, yes?

[@chrispham6599]

But it's team building stuff! ( ͡° ͜ʖ ͡°)

[@w3w3w3]

Super interesting! I only wish they teached math like this at school lol.

[@glenmcgillivray4707]

Win a prize! A day of vacation at a staff retreat. Just pull your number from some drawers! In exchange, anyone who fails? Team building exercises. Same venue. The Whole Day. One variation on this, was everyone has two draws, they can communicate/interact, although the original had no speaking after a period of discussion. Prisoners ask to take one at a time, and draw their own number on the ground in front of them. Everyone gets out on the second round, by identifying exactly these loops after checking their own number and forming a second 'mixed' line by standing behind the number they found, allowing each person to locate their number.

[@10001000101]

Asking for spa? Straight to gaol.

[@XiXi-t5t]

Not mentioning the time he was in a cave for chessboard puzzle

[@Math5D]

12:52 It's not an open bit. It is known, and the limit is exactly 1-ln(2)

[@zanti4132]

Interesting. 1 - ln 2 = .30685... Surely Parker is blowing smoking when he claims there is no known solution.

[@titip1995]

Intrigued.. What is the proof of that?

[@vincentpelletier57]

In the description, Matt corrected that "We do know there is a limit I believe, but we don't know what it is." So, yeah, knowing how to prove that would be great.

[@zanti4132]

I'm betting it has something to do with the convergence of the series 1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + .... to ln(2).

[@Math5D]

Actually, the proof can be found on Wikipedia, so I won't copy it here in total. But you can very easily show, that with N prisoners, the probability of having at least a cycle of length D>N/2 (and this implies, there is only exactly one of those, which makes it so easy) is just 1/D. So the winning probability is 1 - sum(1/D for D from N/2 to N) = 1 - H(2n) + H(n), which has the claimed limit.

[@jessecook9776]

"Successful" is misspelled - a classic Parker square moment.

[@janikarkkainen3904]

Came for this comment, was not disappoint.

[@JollyTurbo1]

Isn't "drawers" also misspelled in the thumbnail as "draws"

[@jackradzelovage6961]

math and english arent on the same plane lol

[@imagineaworld]

Himme witha time stamp my boi

[@juancappa3838]

In the reference below there is an exposition of the problem for general n with a complete solution (it is proved that the strategy shown in this video is optimal and the probability of success tends to 1-ln2 as n goes to infinity). There's also a bit of history of the problem and some generalizations. E Curtin and M Warshauer: The locker puzzle, in The Mathematical Intelligencer vol 28, number 1 (2006).

[@KipIngram]

This is a great puzzle, though of course what is interesting about it is their strategy. Looking forward to learning it...

[@randomcreek]

Love the ending bit!

[@Ruddigore]

Great video and signed/verified order placed for Alex Bellos;s new book 👍

[@feha92]

The strat I came up with (guaranteed to not save them 100% of the time, aka the wrong strat as it might fail) is that they all walk up to the box and open #1 one at a time (then iterate boxes in order as they go away). At most 9 people can fail the box, in which case the iteration didn't really help (which is why they can fail). Each person opening the box has a 9/10 chance of failing, which as you multiply gets below 50% after 7 people (so more likely seventh, eighth or ninth person succeeds, than not). If say seventh succeeds the drawn, it leaves, and eighth, ninth and tenth gets to check #2, meaning only 1-4 needs to check #2 to reach seven people. And so on it goes, eliminating boxes (and people) one at a time. I am unsure (cba to count) what the odds for survival ends up at, but it should at the very least be higher than if people only approach the box once and use up their five uses of the box before letting the next person approach. maybe? EDIT: huh, so the video (and book) didnt have the solution either. They also went with a strat that merely alleviated the probability.

[@omikronweapon]

The answer provide in the video IS the best one. You assume they're looking for a 100% succesful strategy. there isn't one. The goal of the problem is to find the BEST strategy, not a flawless one. In any strategy you can think of, there's always at least the first one that has the take the 50/50 chance, before they can even start to relay information to the second person. Besides, they're not even allowed to leave drawers open or communicate with the others anyway.

[@feha92]

@@omikronweapon They are allowed to communicate beforehand, it is how they implemented the strat in the video. They can also communicate in terms of whether they survive or not. While they can't leave drawers open, you are forgetting that when a prisoner finds their card, they *take* the drawer and leave a hole in the box (leaving it 'open' of sorts. Unsure why you mentioned those two points at all tho. As for my strat, the first person doesn't have a 50/50 chance, but rather a 1/10 chance (only opens a single drawer - #1 specifically, - not 5). The same person will have a higher chance for the second drawer they open though.

[@MartiniComedian]

I believe that SUCESSFUL is part of a new thing called "Parker's Spelling". Brady, T-shirt?

[@dudbike]

So the way to get 100% success rate is to pair up. 1st person goes through 1st row 2nd goes through second row. That way they are guaranteed to see both numbers and voila.

[@Space_Reptile]

"prisons are great places for puzzles" Future Aperture Science project lead right there

[@fsmoura]

We do what we must, because we can.

[@pedromira08]

@@fsmoura For the good of all of us, exept the ones who are dead.

[@RFC3514]

And if at first you don't succeed, you fail.

[@glados1750]

There will be cake!

[@pedromira08]

@@glados1750The cake is a lie!

[@x0r1k]

1:22 I like how the on-screen text start to appear, but interrupted

[@aok76_]

Just came here again after the reverse-Dereked incident. Thank you for all the content Matt! Very entertaining, educational and hilarious!

[@fortunefavorsthebold3459]

Me too lol. Between the two vids, my likelihood of understanding this problem also went up from 1/1000 to about 1/3 as well, and now I can sleep finally thanks to you Matt for your as-always awesome explanations! I'm successfully un-reverse-Dereked!

[@MitchellD249]

"Later, later. Honestly, can you believe this guy, always going on about his book? On an unrelated note, Humble Pi is available now in a bookstore near you!"

[@garetr]

I wrote a Python program to play around with this, but rather than randomly sample permutations I just generated all of them. I set the prisoners to 100 without thinking about how big 100! is, and it immediately took all of my 8GB of RAM. I changed the list of permutations into a generator (so it didn't try to keep it all in memory), and only then realized that the outer-most of my three loops was trying to perform more iterations than there are Plank times before the heat death of the universe...

[@timq6224]

in other news, 52! doesn't even fit in the universe, so your attempt was doomed.

[@David_Kinsler]

Veritasium anyone?

[@BASEBALLFURIES.]

prisoner 11- the guy who wrote dreams paper and forgot the closing bracket

[@falquicao8331]

That was not even the worst error

[@heatherswanson1664]

HaRvaRD aStRopHysICisT

[@SoulOfNemiss]

Would have been hilarious to have Derek using the Parker adjective on this one !

[@alexsoussani1936]

No one forgot the +C when integrating? Impressive!

[@sevret313]

That's the reason Matt Parker is there with them.

[@LegolasnGimli]

@@sevret313 a Parker Integral

[@mikhailvolkov8370]

My first thought too 😂

[@louismyers8845]

i actually did (prisoner number 7) but they read out the wrong crime!

[@georgplaz]

who cares about constants? they are soo boring. nothing ever changes

[@feliciabarker9210]

I originally heard about this a couple of days before my birthday this year, and spent my entire birthday party re-explaining it to each new guest that arrived.

[@lehpares]

Three Blue, One Brown is a national treasure. Agree!

[@Macieks300]

he said international

[@jamesonsanders8838]

Anyone here after Veritassium?

[@guiorgy]

12:50 Came from Dereks' (Veritasium) video to find another Parker Square statement

[@3Ppaatt]

My idea for landing in Maths jail "let epsilon be less than zero".

[@ZedaZ80]

I feel like "let epsilon equal 0" is far more scandalous.

[@brendanh8193]

Or the optimistic/pessimistic probability pair: (p>1, p

[@christianosminroden7878]

Let ε be greater than 1.

[@vsiegel]

@@ZedaZ80 No, not more scandalous, but it hurts more, I can feel ist!

[@VeniVidiVelcro]

Let's hope the limit spells out the digits of pi...

[@ostrich_dog]

That'd be interesting

[@ragnkja]

VeniVidiVelcro It’s more likely to be 1/e

[@SpencerTwiddy]

Nillie that was my initial thought, but since it was seeming to get lower from 31% and 1/e is 37% I doubt that's right

[@SpencerTwiddy]

VeniVidiVelcro pi/10 also seems unlikely but would be so cool

[@conoroneill8067]

The limit is 1-ln(2), as explained in this link: datagenetics.com/blog/december42014/index.html standupmaths must have just made an error or received an incorrect bit of information, which happens.

[@johnchessant3012]

Great video! I first saw this puzzle from minutephysics but your explanation was very clear. Is it really an open problem of what the limit is? I worked out that the probability for 10 prisoners is 1 - (1/6+1/7+1/8+1/9+1/10), which is indeed 35.44%. From that I'd guess the probability for 2n prisoners is 1 - (1/(n+1)+...+1/(2n)), which tends to 1 - log(2). Also, the reasons your math prisoners were put in prison are hilarious! Regarding the pi vs. tau guy, I'd say an opinion without pi is an onion. I myself spent a few years in math prison, for saying that a 4-d dog got into my locked trunk and ate my homework.

[@andreacolongo8094]

Hi Matt, I hope you'll consider this little hint for the next riddle video. At the "pause now if you want to think for yourself" point, it is incredibly handful a graphic with a summary of the riddle rules. Really helpful. Thank you for spreading math stuff. Bye!

[@stevethea5250]

2 years later.. Veritasium did just that

[@CrittingOut]

The reasoning at the end for them being there is too funny

[@leoimrie]

The limit is 1 - ln2. Solution here: en.wikipedia.org/wiki/100_prisoners_problem#Probability_of_success. Also, a fun version is where a prisoner is allowed to go in first to examine the contents of the drawers and make one swap. Then the survival rate is 100% as this prisoner can break any cycle greater than length 5 into 2 smaller cycles.

[@johnchessant3012]

This comment got featured in his new video, nicely done

[@Ken.-]

You mean length 50, right?

[@zanti4132]

When Matt found that the rate of success (as an aside, note that I am spelling "success" correctly here, with two c's) with a large number of prisoners always appeared to be around 31%, I'm genuinely shocked he didn't immediately think that ln 2 must be involved. I mean, doesn't ln 2 = .69... come up all the time in these types of problems?

[@itismethatguy]

@@zanti4132 lol

[@chessman88]

This is a nice version explaining that: kzbin.info/www/bejne/n4SxpJqgZrR2gqM

[@brenthooton3412]

12:50 If you have more and more prisoners, you would have more and more drawers, and it would take them more and more time to go through those drawers, so the upper limit is that the prisoners start to die out of old age before being able to test the hypothesis.

[@jetison333]

It's true, but luckily in maths jail pesky things like old age and common sense aren't around :)

[@kallewirsch2263]

Hmm. Some sort of "Hilbert prison"?

[@Debbiebabe69]

Havnt you ever watched shawshank redemption? Roughly - 'It will take a long long time to tunnel through this reinforced armourcrete wall with a toothbrush, but thankfully time is something I have a lot of on my side'....

[@Jaabo37]

Fascinating maths. Also the crimes were too

[@gordonrichardson2972]

Yes, #10 wrongly rounding down is regarded as a crime by some...

[@Danilego]

Biggest crime was disliking a 3blue1brown video!

[@KuraIthys]

Dividing by zero. Totally worth it. XD

[@gordonrichardson2972]

@@KuraIthys Judging by their expressions, I would say the culprits were unaware of the 'crimes' that they were responsible for.

[@iprice77]

Haha, number 4 looks shocked at the accusation :D

[@Anvilshock]

13:50 "draws infinity as two circles next to each other" … says the guy who writes the letter x as two _half_ circles next to each other …

[@RFC3514]

I'll get the rope.

[@Anvilshock]

@@rosiefay7283 "is the usual way"[citation needed]

[@PhilBagels]

@@rosiefay7283 Yeah, it's the usual way - if you're some kind of sick freak!

[@bordershader]

How are you supposed to distinguish it from × if you write x?

[@Anvilshock]

@@bordershader You know, one of the very first things taught when you enter school is handwriting. If by the time you start needing the sign for (cross) multiplication you can _still_ not write characters legibly enough to distinguish × from x, you've got other problems entirely. It's not the responsibility or even the job of Maths' typography to fix your chicken scratches.

[@Liamneedham29]

Hey that guy has a How Do You Wanna Do This? Shirt. Hes a Critter!!

[@hatgloves8948]

Guilty as charged! Given the problem I thought it would be appropriate. I'm also a huge Prisoner fan which is why I made sure to get number 6. Had to swap my original number out. Everyone else there was too young to appreciate the significance so they didn't mind! Fun fact: I share a birthday with both The Prisoner and Patrick McGoohan, 19th March

[@JorgetePanete]

He's*

[@nymalous3428]

Hat Gloves Great, now I've got to look up the Prisoner.

[@girv98]

Bidet!

[@katiemiller8313]

Yup... I was about to post "Found the Critter," but I figured someone else would've also noticed. :D

[@Music_Engineering]

The philosophy of this problem is left as an exercise for the viewer

[@MrSigmaSharp]

The crimes at the end was hilarious. You are the best Matt

[@trizgo_]

"Takes place in the Maths Prison!" Ah, so my Calc 2 classroom

[@plassbakkallen]

12:50 - The Parker Fun Fact

[@Flare3924]

The fact that number 6 is wearing a "How do you want to do this?" shirt just brings a smile to my face.

[@diarya5573]

Howdydoodiedoodis

[@alexandermcclure6185]

@@diarya5573 It gave me the option to translate, and changed nothing? bruh

[@KartheekTammana123]

For anyone who's wondering, that 35.43% chance isn't that hard to derive. The total number of permutations for a loop of size 6 is (10C6)*(5!)*(4!), or (number of ways to choose 6 elements for the loop)*(number of ways to order the 6 elements in a loop)*(number of ways to order the remaining 4). This works out to 10!/6, and since there are 10! total permutations, the probability of a loop of size 6 is 1/6. Similar logic works for loops of length 7, 8, 9, and 10. So 1/6 is the probability of a loop of size 6, 1/7 for a loop of size 7, and so on. As long as none of these exist (and only one can exist at a time), the prisoners are free. So the final probability works out to be 1-(1/6+1/7+1/8+1/9+1/10)=35.4365% This should generalize if you have 2n prisoners and n guesses each, which will give a probability of: 1 - (1/n+1 + 1/n+2 + 1/n+3 ..... + 1/2n)

[@AngryArmadillo]

Kartheek Tammana I agree with your derivation. Your final expression can be written in terms of the harmonic series as 1 - (H_2n - H_n). As n goes to infinity, the limit goes to 1 - ln(2).

[@PiercingSight]

Well, there we go! Open problem closed!

[@HYOKSU1]

So why Matt says @ 12:50 no one knows what happens if we increase the number? You should let him know as he is asking at the end of the video. Thanks for the derivation!👌🏻👍

[@patrickwienhoft7987]

@@HYOKSU1 Idk why Matt said this, it's very well known to approach 1 - ln(2) as the derivation isn't too hard. It even says it on the wikipedia page: en.wikipedia.org/wiki/100_prisoners_problem#Asymptotics

[@brachypelmasmith]

thanks

[@jackriordan1535]

He's Micheal Sheen......why is he literally just Micheal Sheen?

[@thomasshort182]

Jack Riordan thank you I was trying to find out who he liked like. It was annoying me soo much

[@DerNesor]

I was really getting ready to work out why you get a full cycle in 10% of cases . Then I wrote down one line and had 9! options and was sad I was done...

[@fabriziosantin7420]

Veritasium just posted the solution to the number of prisoners going to infinity, of anyone's interested

[@UnReaLgeek]

“How did you get into math prison?” “I attempted to trisect an angle using only a non-Euclidean compass and straightedge”

[@poldelepel]

If the number in a cycle (in this example 5) is bigger than the number of draws they can open, couldn't it be still possible to win? You make it like it isn't... If the cycle is 2-3-4-5-6-7-8-9-10-1 (first is first draw), and the prisonners go in this order: 1-2-3-4-5-6-7-8-9-10; all the prisonners will find their card on the second draw and still win, although the cycle is 10.

[@standupmaths]

In that case prisoner 1 would see the numbers 2, 3, 4, 5, 6 and fail.

[@poldelepel]

@@wagglebutt this cycle is not possible. The first prisonner will start in first drawer and get 10, go to drawer 10 and get 1. So you get a cycle of 2 numbers. This sequence is only possible when the first prisonner will not start at drawer 1 but at drawer 9. Prisonner 2 will have to start at drawer 10, prisonner 3 at 1 and so on. and they will succeed in this example. But this will only be a succes if the sequence of the prisonners is the same as the sequence of the the drawers, and the sequences are shifted or permuted (in the right amount). Starting at your own drawer number is part of the boundary conditions to have the biggest success rate possible.

[@hermannmuller7146]

This reminds me on how i tried to find the gamecube cd of the game i wanted to play.

[@lyrimetacurl0]

lol

[@omikronweapon]

just don't stack those suckers. I once opened ALL my boxes several times before I noticed the game I wanted was UNDER another disc.

[@shane8037]

Relatable.

[@dreamingwolf8382]

The fact that each person can observe what the others open will skew the result

[@insoYT]

This. This was going to be also part of my plan until i realized that it wasn't really part of the puzzle. :p

[@nopetuber]

Sorry why is that? They are allowed to plan a common method.

[@conoroneill8067]

@@nopetuber Say you were the last person to go, and you saw that no-one had yet picked one of the drawers - you would have to pick that drawer, or else it would be guaranteed that at least one person would not have found their card. As such, it is a different problem when people are allowed to observe than not. I don't know if being able to observe allows for a better solution than the optimal strategy shown here, though (I doubt it).

[@ragnkja]

Conor O'Neill If nobody had picked a specific drawer, that must have been the drawer with your number on it, which means it doesn’t matter if you saw the other prisoners open their drawers.

[@nopetuber]

​@@conoroneill8067 If you choose the correct strategy, there's only one last drawer left for you to pick -- the one marked with your prisoner number. Maybe you mean if by any chance they go with a different strategy (which is quite likely going to fail anyway).

[@ostrich_dog]

I shouldn't have watched VSauce2's video on this

[@bronsolo6941]

I thought the same thing. I was like, "oh I know this!"

[@TunesByAI2024]

Same. I didn't even know there was other solutions for this. 😅

[@andrewking2315]

Isn't the 35% incomplete? It shows how often the groupings are guaranteed to be successful. But, if a cluster has 6 entries it is not a guaranteed fail if every prisoner is only 1 drawer away from their number - or within 5 for that matter. So, the probability of success should be greater than 35%.

[@BoucheduFou]

This shows in the experiment, as they should find success on average about 42.7% of the time. The probability of them still succeeding with a loop of 6 is (5/6)**6 ˜= 0.33 The probability of them still succeeding with a loop of 7 is (5/7)**7 ˜= 0.095 etc Of course, for larger numbers of prisoners, the chance of success on loops greater than 50% of the number has much less of an impact, which is why they probably ignored this factor (since the problem presumably was formulated for a larger number of prisoners).

[@NotYourAverageNothing]

Andrew King What's an example of a 6-length loop with each number one box away?

[@martinmackey7191]

Variant: after the warden arranges the cards, the janitor gets to inspect all of them. Then janitor has strategize with the prisoners beforehand. After examining, the janitor may switch two cards, but doesn't have to. He then exits the prison without telling the prisoners what he did, then they begin. Question: what should the janitor do? Answer, spoiler alert: if the janitor finds a cycle greater than 5, he switches two cards at opposite ends of the cycle, creating two smaller loops, neither larger than 5, ensuring victory for the prisoners.

[@beliasphyre3497]

I'd probably be in maths jail for being a six offender.

[@aBetterMove]

Why was 6 afraid of 7? 6 has General Anxiety Disorder. He attends CBT workshops and counselling twice a week and is doing great. 7 doesn't really eat numbers; that's just a vicious rumour that 4 spread. 7 is however a maniacal arsonist. 🔥

[@FlorianLinscheid]

Got Derek'd again, Matt

[@nekogod]

Reverse-Derek ground zero!

[@hart-of-gold]

So, What are you in for? "I used to write italic x as a wiggly line crossed by a straight line. For all those years, I was a monster writing chi not x."

[@stargazer_and_co]

1:39 using tau instead of pi

[@pinicius]

"always round down" is a crime because it breakes the "pi equals euler theorem"

[@SpencerTwiddy]

Pi Master Mithos imagine calling e "euler"😅

[@pinicius]

@@SpencerTwiddy that's another crime. Crimeception.

[@OriginalPiMan]

Always round to 3. All numbers in the real set round to 3.

[@mgb360]

Also known as truncating

[@KuraIthys]

Meanwhile, if we were doing 'crimes against compute performance'... Doing anything OTHER than truncating a value would be a crime. ;p

[@00blaat00]

"Didn't pick a side in the Pi vs Tau debate ... Picked the wrong side in the Pi vs Tau debate."

[@kutsen39]

To be honest it kinda annoys me a little to find out that tau is 2pi, when it should be pi on 2, since the character tau is half of the character pi

[@Janokins]

Who doesn't like a good old linked list?

[@feelfreefpv]

Problem was really poorly described before solution was revealed.

[@gerritroseboom8621]

I am upset that "forgot to add +C while integrating" isn't in the list of crimes...

[@zuphix1802]

My strategy was: Each person looks at their own number on round 1, and go to the left if the number was odd, go to the right if their number was even. For round 2, each person would have a list of 5 drawers which contain either odd or even, depending on which one they're searching for, which leaves 5 boxes to check and they have 4 rounds left. They've already had a 1/10 chance to get it right and now they have 4x 1/5 chances. For round 2, each person will start searching for their own number, or they can skip if they already found it. They go to the left if the number they picked from round 1 was 1-5 or go to the right if the number was 6-10. Now people have had a 1/10 chance at finding it randomly, a 1/5 chance at finding it in half of the group. They can cross-reference their list of 5 numbers from before with the numbers above or below 5. Best worst-case scenario they have an odd number 1-5 or an even number 6-10 and have 3 more numbers to check with 3 attempts remaining. Then I un-paused the video and realized I misunderstood the rules.

[@girv98]

14:04 Number 6 is a critter confirmed

[@bg6b7bft]

Are they not allowed to watch how the previous prisoner's draw? That would make it much easier to survive.

[@to12]

That was my thought as well. I thought they should have had the first guy pick 5 from the same side, hoping to get his number but looking for the next person's. For example if he chose the left side and did not see the next guys he could hold up his right hand signaling to the next person where his card is. He then would go through the right side knowing he would get his number but looking for the next person's card again to signal them where their's is. They would be guaranteed to get 9 out of 10 correct and a 50% chance to get 10 out of 10. Although this would not work for the higher numbers of people that they were talking about.

[@bg6b7bft]

@@to12 I imagine signaling would draw the wrath of the evil warden, but as described, they can watch the order the previous prisoners open the drawers.

[@alonamaloh]

12:50 "[...] and fun fact: Nobody knows [...]". This is complete B.S. Anyone that has solved the problem for 100 prisoners on paper (as I did) knows the answer. The exact answer for an even number of prisoners N is 1/2-1/3+1/4-1/5+...+1/N, whose limit is 1-log(2)=0.3068528...

[@lordkazzakgeneral]

Matt, I would appreciate if you didn't turn your videos' volume level so low. My old(ish) laptop is struggling to keep up and i was really looking forward to watching your video while having dinner. Thanks!

[@joeeeee8738]

Fix your laptop, don't blame him

[@ashtonhoward5582]

@@joeeeee8738 that's a bit rude. Not everyone can get their laptop fixed. And it doesn't necessarily need to be fixed, the speakers could just be kinda quiet to begin with.

[@ashtonhoward5582]

You should find some laptop speakers. They should be cheap, and most can get pretty loud.

[@joeeeee8738]

@@ashtonhoward5582 it may sound rude but it's true. See how "if you didn't turn your videos volume level so low" sounds. That's basically saying it's Matt's fault and not his fault for having bad sound. Even worse is this! : "I was looking forward to watching your video while having dinner" like "your low volume has brought me only disappointment" when it should be the opposite

[@ashtonhoward5582]

@@joeeeee8738 that's fair

[@samuelporritt3413]

prob(there is a cycle of length > n/2) = sum_{i=n/2}^{n} prob(there is a cycle of length i) because you can have at most 1 cycle with length > n/2 = sum_{i=n/2}^{n} (n choose i) * (i-1)! * (n-i)! /n! because there are i out of n choices for the numbers in the cycle of length i, these can be arranged in (i-1)! ways in the cycle, then there are (n-i)! ways of arranging the others and n! in total = sum_{i=n/2}^{n}1/i ~ log 2

[@bzqp2]

They are in jail cause they divided by zero.

[@cedricluger7748]

I doubt that the limit of this strategie is an open problem, I just spent a couple minutes and came to the result that it is 1-ln(2), which is around 0.3069. One easily verfies that the chance of everyone out of 2n people dying is the sum over 1/m with m=n+1,...,2n. You can check that for n=5 you get exactly their result of 35.4365% survival chance. This goes against ln(2) with O(1/n). You're welcome :)

[@pyglik2296]

For a moment I thought his shirt is also a math's puzzle.

[@fabiansondh5342]

Should not the chance of surviving be at 4:33 to 5:11 the product of 5/10*5/9* ... 5/6. Becouse the sample size after will be 5 and then its a 100% chance of picking the right number. So the total chance by random be roughly 10%

[@enotdetcelfer]

And that folks, is how you get the dot in Jeremy Bearimy

[@ProgressiveMastermind]

Wouldn't be surprised if you found a 31,41592653....% probability in all those circles 😁

[@PointB1ank]

I'm forever annoyed by right handed people wearing watches on their right hand, but to each their own I suppose.

[@shanestories]

PointB1ank Do you mind if I ask why? I do it but I also feel I have a pretty good reason, though the story is long and rather boring

[@muthuvrpn]

It tends to 1 - ln(2) = 0.307 as the number of prisoners tend to infinity, Isn't it? It's also known for the case of 'n' prisoners, the strategy gives a surviving probability of 1 - (H_(n) - H_(n/2)) where H_n is the Harmonic number..

[@AngryArmadillo]

The limit is 1 - ln(2).

[@kered13]

Wikipedia has the proof: en.wikipedia.org/wiki/100_prisoners_problem#Asymptotics

[@deinauge7894]

it's not that hard to get it in a few minutes of calculation... i could not believe my ears when he sayd it is unsolved ;-)

[@kmacdough]

I assume this is just a fun way to encourage kids to play around with the numbers and feel that moment of joy when you feel like you've discovered something. Because that's what we're really about here.

[@jayvee4787]

Your answer fails to account for an additional factor of solutions. Which is even when the cycle is greater than 5 numbers, the inmates number is still able to be within 5 numbers of theirs within the cycle. Which I believe you would find brings the cycles pattern nearer to 50%.

[@neplatnyudaj110]

No. They always start on the node in the graph which is after their number.

[@kallewirsch2263]

I was surprised that no one committed the crime of having an odd number of sign faults.

[@drow27]

@12:51 I do think there's a limit...

[@RJSRdg]

Also - although the prisoners can't communicate with each other, if they can see the other prisoners opening the drawers using the pattern described (i.e. your own number, then the number that is in that drawer etc), they can work out which cards are in which drawers, which simplified the odds.

[@michaelgould6198]

This will actually work. If you see that the ten goes to 1 (you can peek or just memorise where they took their number from, and where they picked the next number) then you can find each specific loop, and then know which cards are where.

[@xTheUnderscorex]

The chance to win is higher than that though, regardless of whether you use that strategy or not. Even if you didn't find your number, you have a 1/5 chance to guess it correctly anyway. So giving the chance with no combined strategy as 1/1,024 chance is very wrong, it's actually 0.0060466176 which is more than 6 times as likely.

[@toxications]

Okay, so the rules aren't really clear to me, I like thinking outside of the box. Assumptions: 1. Prisoners know the order in which they are going. 2. Although no communication, they can see each other during the test. If assumptions apply, this would be my solution: - The first prisoner looks at the left five cards. - Aside from their own number, the prisoner also looks for the number for the next prisoner. - If the number of the next prisoner has been found, the prisoner faces them. If the number hasn't been found, they turn their back towards them. - The next prisoner goes to take a look and if the previous inmate is facing them their number is in the left pile, if they do not face them it's in the right.

[@TheBetterVersion]

First, in 2n prisoners, let's observe that the probability of having a chain of length k (k > n) is 1/k P(not finishing too early) * P(returning exactly) = [(2n-1)/(2n) * (2n-2)/(2n-1) * ... * (k-1)/(k)] * [1/(k-1)] so that solves problem #1 The chance of winning is 1 - [1/(n+1) + 1/(n+2) + ... + 1/(2n)] which can be calculated because H(n) = sum from 1 to n of 1/n A(2n) alternating H(2n) = H(2n) - 2 * H(n) / 2 = H(2n) - H(n) So we get the success rate = 1 - [H(2n) - H(n)] = 1 - A(2n) which approaches 1 - ln(2)

[@Absynthexx1]

Does the success rate change if they follow a different set of rules but stick to those rules? Like, what if they agreed that all the "prisoners" would only select the 5 left side drawers every time? Another way of posing the questions is, 'was the increase in their success rate a result of the method employed, or is it inherent to the parameters of the 'game'?

[@louismyers8845]

im prisoner number 7 - i actually forgot the +c which they didn`t mention

[@pugz3230]

TedEd did a video on this with band members in their riddle series

[@Dartnix]

"ALL SUCESSFUL" you didn't think I wouldn't notice, Matt

[@MJWhitfield]

For the limit as the number of draws tends to infinity, doesn't it just tend to 1-ln(2). Because you only fail if there is a cycle that is bigger than half the number of draws, and there can only be one such cycle so you just sum the probability for each possible cycle size. It is relatively straightforward to calculate the probability of getting a cycle of length m as 1/m (assuming that m is greater then half the number of draws); so this gives us a fairly simple formula for the probability of not succeeding. For example the probability of not succeeding for 10 draws is 1/6+1/7+1/8+1/9+1/10 ≈ 0.645635. For the case of picking opening n draws out of a total of 2n draws, we can rewrite the probability of getting a cycle length of n+m (where 1

[@ablazedguy]

I can't hear almost anything, then the music goes so loud it blows dust out of my ears. Come on!

[@jcughan]

David Vimr yeah the audio levels aren’t great on this vid, I noticed the same thing probably because I’m using headphones.

[@zaraak323i]

So, you can hear almost everything?

[@Anvilshock]

@@zaraak323i Sneaky!

[@Gold161803]

For l=51,52,53,... the probability that the longest loop is of length l is 1/l. The sum of 1/k to 1/2k approximates the integral of the reciprocal function from k to 2k, so as the number of prisoners gets large, the probability of failure tends to ln(2).

[@upsidedownwhale]

I've heard of this strategy but never understood the logic behind it, and now I do. Another great video, thanks Matt!

[@praveenb9048]

This guy is messing with so many peoples' brains, he's a menace. They should lock him up and throw away the key.

[@5hirtandtieler]

Great video! But might wanna tone down the level of the transitions (esp the one before 1:30) 😅

[@R2Cv1]

I didn't get the inside joke about rotating the 8 upside down. Is it just that it would remain the same or am I missing anything?

[@Marconius6]

If you write the top loop the same size as the bottom, you deserve to be in maths jail too.

[@travisscavoni369]

I write my eights in reverse. I wonder if that would get me in maths prison

[@Anson_AKB]

@@Marconius6 what about me, turning infinity (written as a single loop instead of two circles) by 90 degrees to write an 8 ?

[@1992WLK]

ACTUALLY! Cycles of 6 could also work. The first 5 prove fruitless but they could check the next box in the sequence when determining their fate and get their number on the 'final exam'.

[@1992WLK]

Expanding upon that it would explain a gradual decrease in chance for larger groups. Because seeing 60% (6/10) of the cards isn't the same as 51% (51/100).

[@Stray0]

1 is a valid prime number. am i in math prison now?

[@badlydrawnturtle8484]

1 is both prime AND composite. ...No, wait, I didn't mean it! Not the chair! Anything but the chair!

[@Jivvi]

Q: What is the prime factorisation of 75? A: 3×5²×1ⁿ Ooh, I'm in trouble.

[@coolnoah8183]

My sokution, which requires the prisoners to be able to see each other is to have some indicator for the next prisoner (i.e. where you stand afterwards) on whether or not you saw their number too, then they just check the same 5 or the other 5. That way it can only fail on the first prisoner and no others if the first prisoner passes, so the odds of them winning are just 50/50

[@irrelevant_noob]

It can still fail, if some prisoner has a very short cycle and can't provide any helpful information to the next one. :-B But it is indeed an improved version of the strategy. 👍

[@coolnoah8183]

@@irrelevant_noob Not necessarily, if they didnt see the next persons number, then the next person knows not to pick any cards the other person picked, which takes 5 options away from a total 10, leaving 5 options, of which they will see their card

[@irrelevant_noob]

@@coolnoah8183 except you don't explain WHICH 5 cards you go through if the loop length is small (like 1, 2, or 3)... And another flaw in your story: how do you know WHICH are the 5 cards the previous player looked through, so that you could choose the 5 "left" options? (And even if you get lucky and find your own number in there, how would you tell the next player whether you looked through your own loop, or the previous player's?) -.-

[@coolnoah8183]

@@irrelevant_noob That's what I mean that my solution is conditional, it requires this exact setup where the next players in line can actually see what the person before them is doing (i.e. which drawers they search). I understand it's not an elegant solution and I posted it in the opportunity to pause, before they gave away the solution

[@irrelevant_noob]

@@coolnoah8183 oh, i thought you just needed the final bit on info, whether it was found or not. And really... talking about it made me realize that it *_is_* indeed all you need: you could in fact not use the loop strategy at all, just have the 1st player check boxes 1 through N/2, and signal whether "2" was in there or not. And every other player would signal which half to search, based on whether they saw p+1 or not. Which gets you back to 50-50. Neat!

[@RigzoTV]

Steve Mould's twin brother.

[@HRRRRRDRRRRR]

Or Michael Sheen

[@baoboumusic]

I had to screw up my sound quite a bit to hear what they're saying. Am I the only one?

[@darjanator]

#6 has the best shirt. #howdoyouwanttodothis

[@udrichie]

I have a wonderful solution to the 100 prisoners problem, but there isn't enough space here to write it all down. /P.d.F.

[@mimzim7141]

if you give it to an AI will it find this strategy? Is there proof this is the best strategy?

[@IceMetalPunk]

Depends what kind of AI.