The unbelievable solution to the 100 prisoner puzzle.
Vložit
- čas přidán 3. 11. 2019
- 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.uk/collections/b...
Thanks to Matt Scroggs and the Chalkdust folks for helping organise the volunteers and the maths.
chalkdustmagazine.com/
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.uk/standupmaths...
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.com/
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/ - Zábava
Nicely done! In case you want to see another version of this puzzle/explanation :)
czcams.com/video/eivGlBKlK6M/video.html and czcams.com/video/C5-I0bAuEUE/video.html
Yay! Crossover!
Watching sciency CZcams pays off. I knew the answer from watching this previously.
Aaaah, that's where I knew that from!
TED-ed had a similar riddle.
I thought I was having deja vu
It was a pleasure to host you! Although, next time, maybe a spa retreat for our staff, instead of a prison, yes?
But it's team building stuff! ( ͡° ͜ʖ ͡°)
Super interesting! I only wish they teached math like this at school lol.
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.
Asking for spa? Straight to gaol.
Not mentioning the time he was in a cave for chessboard puzzle
"prisons are great places for puzzles"
Future Aperture Science project lead right there
We do what we must, because we can.
@@fsmoura For the good of all of us, exept the ones who are dead.
And if at first you don't succeed, you fail.
There will be cake!
@@glados1750The cake is a lie!
1:22 I like how the on-screen text start to appear, but interrupted
Just came here again after the reverse-Dereked incident. Thank you for all the content Matt! Very entertaining, educational and hilarious!
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!
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...
in other news, 52! doesn't even fit in the universe, so your attempt was doomed.
"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!"
The reasoning at the end for them being there is too funny
Would have been hilarious to have Derek using the Parker adjective on this one !
12:50 Came from Dereks' (Veritasium) video to find another Parker Square statement
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.
Three Blue, One Brown is a national treasure. Agree!
he said international
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.
This comment got featured in his new video, nicely done
You mean length 50, right?
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?
@@zanti4132 lol
This is a nice version explaining that: czcams.com/video/iSNsgj1OCLA/video.html
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!
2 years later..
Veritasium did just that
No one forgot the +C when integrating? Impressive!
That's the reason Matt Parker is there with them.
@@sevret313 a Parker Integral
My first thought too 😂
i actually did (prisoner number 7) but they read out the wrong crime!
who cares about constants? they are soo boring. nothing ever changes
prisoner 11- the guy who wrote dreams paper and forgot the closing bracket
That was not even the worst error
HaRvaRD aStRopHysICisT
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.
It's true, but luckily in maths jail pesky things like old age and common sense aren't around :)
Hmm. Some sort of "Hilbert prison"?
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'....
The crimes at the end was hilarious. You are the best Matt
The philosophy of this problem is left as an exercise for the viewer
12:52 It's not an open bit. It is known, and the limit is exactly 1-ln(2)
Interesting. 1 - ln 2 = .30685... Surely Parker is blowing smoking when he claims there is no known solution.
Intrigued.. What is the proof of that?
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.
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).
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.
The fact that number 6 is wearing a "How do you want to do this?" shirt just brings a smile to my face.
Howdydoodiedoodis
@@diarya5573 It gave me the option to translate, and changed nothing? bruh
My idea for landing in Maths jail "let epsilon be less than zero".
I feel like "let epsilon equal 0" is far more scandalous.
Or the optimistic/pessimistic probability pair: (p>1, p
Let ε be greater than 1.
@@ZedaZ80 No, not more scandalous, but it hurts more, I can feel ist!
12:50 - The Parker Fun Fact
"Successful" is misspelled - a classic Parker square moment.
Came for this comment, was not disappoint.
Isn't "drawers" also misspelled in the thumbnail as "draws"
math and english arent on the same plane lol
Himme witha time stamp my boi
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)
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).
Well, there we go! Open problem closed!
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!👌🏻👍
@@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
thanks
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.
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 …
I'll get the rope.
@@rosiefay7283 "is the usual way"[citation needed]
@@rosiefay7283 Yeah, it's the usual way - if you're some kind of sick freak!
How are you supposed to distinguish it from × if you write x?
@@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.
Let's hope the limit spells out the digits of pi...
That'd be interesting
VeniVidiVelcro
It’s more likely to be 1/e
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
VeniVidiVelcro pi/10 also seems unlikely but would be so cool
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.
Thanks for using the visual, it made the reasoning clear to me.
I've heard of this strategy but never understood the logic behind it, and now I do. Another great video, thanks Matt!
Got Derek'd again, Matt
"Takes place in the Maths Prison!"
Ah, so my Calc 2 classroom
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
“How did you get into math prison?”
“I attempted to trisect an angle using only a non-Euclidean compass and straightedge”
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...
I appreciate you sharing your knowledge with us.
Love the ending bit!
"ALL SUCESSFUL" you didn't think I wouldn't notice, Matt
Fascinating maths. Also the crimes were too
Yes, #10 wrongly rounding down is regarded as a crime by some...
Biggest crime was disliking a 3blue1brown video!
Dividing by zero.
Totally worth it. XD
@@KuraIthys Judging by their expressions, I would say the culprits were unaware of the 'crimes' that they were responsible for.
Haha, number 4 looks shocked at the accusation :D
This is absolutely mind-blowing
Hey that guy has a How Do You Wanna Do This? Shirt. Hes a Critter!!
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
He's*
Hat Gloves Great, now I've got to look up the Prisoner.
Bidet!
Yup... I was about to post "Found the Critter," but I figured someone else would've also noticed. :D
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.
Veritasium anyone?
I have seen many of these, but I like this variation.
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).
The fact that each person can observe what the others open will skew the result
This. This was going to be also part of my plan until i realized that it wasn't really part of the puzzle. :p
Sorry why is that? They are allowed to plan a common method.
@@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).
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.
@@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).
"Didn't pick a side in the Pi vs Tau debate ... Picked the wrong side in the Pi vs Tau debate."
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
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).
Book looks cool and a great addition to my 2 signed books of you Matt! I have to say Humble Pi was such a great read. I hope this one doesn't disappoint either :)
This reminds me on how i tried to find the gamecube cd of the game i wanted to play.
lol
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.
Relatable.
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.
Brilliant , thanks for the video
8:55 Regarding the cycle, if you can remember the cycle of cards ( or which draw every person before you pulled, and in what order) you could separate the cycle in smaller "semicircles" removing the numbers that others had been released on, and thus help everyone succeeding you to cut down on the number of possibilities.
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.
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.
I was surprised that no one committed the crime of having an odd number of sign faults.
This is a great puzzle, though of course what is interesting about it is their strategy. Looking forward to learning it...
For the probability question posed around minute 13, it actually seems relatively simple.
A losing combination is any combination containing a cycle larger than n/2. We also know that, for each cycle length in that range, there can be no other cycle of size > n/2. This property is useful to avoid double counting.
For a given cycle of length k such that k > n/2, there are n!/(n-k)! possible permutations. However, we need to restrict that, since, in making it a cycle, all permutations that differ only by the starting point are equivalent. (1,2,3,4 === 2,3,4,1) There are k possible starting points within the cycle, so the number of possible cycle permutations of size k is n!/k(n-k)!
For the remainder of the cards that are not part of the cycle, there are n-k cards, and n-k slots, so there are (n-k)! permutations of those cards for a total of n!/k(n-k)! * (n-k)! or simply n!/k.
Given that there are n! possible permutations in the original problem, we can now see that the probability of a cycle of length k existing is (n!/k) / n! or simply 1/k, as long as k > n/2.
Since any k larger than n/2 loses, then the probability of losing is SUM(1/k, n/2+1, n)
Anyone here after Veritassium?
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."
Great video and signed/verified order placed for Alex Bellos;s new book 👍
Great shirt, Matt. Also, great video.
He's Micheal Sheen......why is he literally just Micheal Sheen?
Jack Riordan thank you
I was trying to find out who he liked like. It was annoying me soo much
It is really impressive how you can tell this in a so complicated way.
???
i thought this, explaining the puzzle when theyre going back and forth from each other had me baffled.
I'm proud to say I finally solved one of these puzzles without any hints--I worked out that when n = 4, guessing randomly gives the team a 1/16 chance of winning, but the "follow the trail" strategy ups the chances to 10/24, which extends in principle to any n.
1:39 using tau instead of pi
8:04 the moment he realizes a circle of 10 cant have 5 items on the first 3/4s :D
Who doesn't like a good old linked list?
For the bonus puzzle:
Pick a number from 1 to 10 to start with, it makes no difference which one.
The next number could be that same number (1/10) or a different number (9/10). Say it's a different number. The next number could be the first number and close the loop (1/9) or one of the remaining 8 numbers (8/9), etc. So we have (9/10) * (8/9) * (7/8) * ... * (1/2) = 9! / 10! = 1/10
Great T-shirt #6! May the Traveler be with you.
14:04 Number 6 is a critter confirmed
For a moment I thought his shirt is also a math's puzzle.
Came here to make a reference to Sattolo's shuffle algorithm. Accidentally solved the puzzle @11:28 without having an opportunity to think about it.
Sattolo's algorithm guarantees a full cycle every time, and it's only the subtlest modification on proper Fisher-Yates so people can easily do it by accident. This video demonstrates how a careless bug in a shuffle algorithm COSTS LIVES!
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)
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'?
I'd probably be in maths jail for being a six offender.
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. 🔥
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!
Fix your laptop, don't blame him
@@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.
You should find some laptop speakers. They should be cheap, and most can get pretty loud.
@@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
@@joeeeee8738 that's fair
I found a nice way of working out the probability of the chain strategy failing and some simple bounds for it.
We want to know the probability that there is a chain of length L when there are N card and N/2
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
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. 👍
@@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
@@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?) -.-
@@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
@@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!
Genuinely thought that was Michael Sheen for a second there.
And that folks, is how you get the dot in Jeremy Bearimy
I loved that finish. As more of a purist by heart but trained to program, I could relate. 😉
Answering at 4:00 if i remember correct the strategy is [if your #5] to open drawer [5] and then pull the drawer number on the card you drew [if you drew 3 open drawer 3] repeat unill you hit your number or you draw 5 cards.
I forget the reason is [often] works but its about as good a strategy as the "correct" prisoners dilemia solution in that you can still fail miserably.
I am upset that "forgot to add +C while integrating" isn't in the list of crimes...
I shouldn't have watched VSauce2's video on this
I thought the same thing. I was like, "oh I know this!"
Same. I didn't even know there was other solutions for this. 😅
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..
Nice one! I was expecting the hats problem which requires the prisoners to use the modulus function. You've probably got a video on that somewhere...
Are they not allowed to watch how the previous prisoner's draw? That would make it much easier to survive.
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.
@@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.
Since I'm horrible at math, I can only contribute this practical suggestion: If you use opaque boxes with protrusions instead of cutouts to open them, you could place the cards in the boxes face up and it would be quicker and easier to run the experiment (no need to take anything out to flip it)
number 6 has a "how do you want to do this" shirt ❤️ critters in the wild are great
The probabilities shown in the video can be gotten with the equation:
probabilityOfSuccess( k ) = 1 - SUM( 1 / n ; n = k / 2 ; n = k )
Although this is a guess as to what the correct equation is, if someone can show the probability of a ring of size n occurring is 1/n (for atleast n>k/2), that would mean this solution is correct as this asks how many of the combinations of answers has a loop of size n.
It is correct and can be proven.
I use the same example with ten prisoners, but it can easily be extended. Let's find the probability of failure: we have to count all the rings longer than 5.
Let's compute the probability of the longest ring =7 (for example)
How many arrangements can you make if max length ring =7?
Choose 7 cards out of 10 to make the ring =10!/(7!*3!) (ten choose 7)
Count in how many way you can place those 7 cards in a loop (remember: they cannot form a ring of length
"always round down" is a crime because it breakes the "pi equals euler theorem"
Pi Master Mithos imagine calling e "euler"😅
@@SpencerTwiddy that's another crime. Crimeception.
Always round to 3. All numbers in the real set round to 3.
Also known as truncating
Meanwhile, if we were doing 'crimes against compute performance'...
Doing anything OTHER than truncating a value would be a crime. ;p
Veritasium just posted the solution to the number of prisoners going to infinity, of anyone's interested
Love the Shirt!
Great video
A real Parker's hair cut you've got there, not gonna lie
im prisoner number 7 - i actually forgot the +c which they didn`t mention
I love how Matt’s shirt pattern matches the football pattern.
Always good to see a fellow football enthusiast. ;)
The "football pattern"? You mean just a plain old hexagonal grid?
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%.
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).
Andrew King What's an example of a 6-length loop with each number one box away?
I came up with a different strategy: you said they have to go stand on the other side of the room, but you didn’t say where on the other side. So, #1 goes over and picks a column: left or right. He’s looking for his own number sure, but mainly he’s looking for the next person’s number! If he finds #2 in the column he chose (left or right), he goes and stands in the corresponding corner of the far end of the room. If he does not, he goes and stands in the opposite corner. This now tells #2 which column his number is in. #2, knowing this, now goes and opens the column he knows his number is in, but he’s actually looking for #3, and he’ll go stand in the corresponding corner to signal #3 where his number is, and so on. Therefore, the only person whose selection is random is #1, who has a 50% chance of finding his own number. Therefore, half the time they will get 100% success, and half the time they’ll get 90% success. Bam.
I was thinking along the same lines trying to work out the puzzle. Nice!
Cool trick, but I don't see how you get the 90% value. If the first prisoner finds their number they all win, else they all lose, so 50% sucess rate.
The very first rule of this puzzle was no communications. Your method is breaking practically the only rule there was to this puzzle. If you want to enable communications like that, there are way simpler ways to solve the puzzle.
Torossian Jesse well yeah, but the 2 guys up front don’t know you’re communicating. It’s a secret. 😀
And if you have to go to the next room as soon as you find your number this strategy fails as well.
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?
If you write the top loop the same size as the bottom, you deserve to be in maths jail too.
I write my eights in reverse. I wonder if that would get me in maths prison
@@Marconius6 what about me, turning infinity (written as a single loop instead of two circles) by 90 degrees to write an 8 ?
the ending was very cute thank you