The unbelievable solution to the 100 prisoner puzzle.
ฝัง
- เผยแพร่เมื่อ 3 พ.ย. 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/ - บันเทิง
![Recursive PowerPoint Presentations [Gone Fractal!]](http://i.ytimg.com/vi/b-Fa6HtvGtQ/mqdefault.jpg)
Nicely done! In case you want to see another version of this puzzle/explanation :)
th-cam.com/video/eivGlBKlK6M/w-d-xo.html and th-cam.com/video/C5-I0bAuEUE/w-d-xo.html
Yay! Crossover!
Watching sciency TH-cam 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!"
Would have been hilarious to have Derek using the Parker adjective on this one !
The reasoning at the end for them being there is too funny
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.
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
Three Blue, One Brown is a national treasure. Agree!
he said international
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
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: th-cam.com/video/iSNsgj1OCLA/w-d-xo.html
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 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.
prisoner 11- the guy who wrote dreams paper and forgot the closing bracket
That was not even the worst error
HaRvaRD aStRopHysICisT
The crimes at the end was hilarious. You are the best Matt
12:50 - The Parker Fun Fact
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
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.
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!
"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
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.
Thanks for using the visual, it made the reasoning clear to me.
I appreciate you sharing your knowledge with us.
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.
I've heard of this strategy but never understood the logic behind it, and now I do. Another great video, thanks Matt!
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...
Love the ending bit!
"Takes place in the Maths Prison!"
Ah, so my Calc 2 classroom
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
This is absolutely mind-blowing
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
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.
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
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).
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.
"ALL SUCESSFUL" you didn't think I wouldn't notice, Matt
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.
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).
I have seen many of these, but I like this variation.
“How did you get into math prison?”
“I attempted to trisect an angle using only a non-Euclidean compass and straightedge”
Veritasium anyone?
Brilliant , thanks for the video
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 :)
Got Derek'd again, Matt
I was surprised that no one committed the crime of having an odd number of sign faults.
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)
1:39 using tau instead of pi
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.
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).
Great video and signed/verified order placed for Alex Bellos;s new book 👍
This is a great puzzle, though of course what is interesting about it is their strategy. Looking forward to learning it...
Anyone here after Veritassium?
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.
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.
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
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.
14:04 Number 6 is a critter confirmed
Sorry I missed a part, but one the 100 version, how many drawers does everybody get to check? Half (e.g. 50) or still just 5?
Also you can boost the likelihood: 1st person opens all the drawers on the left, 2nd person opens all the drawers on the right. If you find an odd number, leave the drawer cracked; if even shut it all the way.
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.
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
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)
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
Great shirt, Matt. Also, great video.
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."
For a moment I thought his shirt is also a math's puzzle.
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
I'm wondering whether if you look at 3 and then use the numbers you've found in deciding where to look for your last 2 choices may increase the probability - i.e. if you do not see the number above yours then choose that one to start your last 2 choices. I suspect as there are many loops of size 4 and 5 which would be ignored if we did that, so it would probably decrease the probability - even if we try to use the values that we have found in the first 3 cards somehow.
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
Who doesn't like a good old linked list?
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..
There's a book called _Algorithms to Live By: The Computer Science of Human Decision_ that pretty much explains this very phenomenon and other. One that I found that was pretty cool is named The Secretary Problem. I encourage you guys to check it out. The solution is pretty neat!
"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
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.
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...
Great T-shirt #6! May the Traveler be with you.
8:04 the moment he realizes a circle of 10 cant have 5 items on the first 3/4s :D
Genuinely thought that was Michael Sheen for a second there.
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!
I loved that finish. As more of a purist by heart but trained to program, I could relate. 😉
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. 🔥
And that folks, is how you get the dot in Jeremy Bearimy
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?
Great video
I am upset that "forgot to add +C while integrating" isn't in the list of crimes...
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.
Guessing at 7:15 : there are most likely distinct "number loops". So if you start with the drawer that is your number you will eventually come to your number on a card, pointing to the drawer you started with. If you're lucky it's no more than 5 steps.
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 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. 😅
im prisoner number 7 - i actually forgot the +c which they didn`t mention
I always round down in my formulas because I made the ones that require rounding floor functions
Surely this is known: if a permutation of degree n has a cycle of length greater than n/2 then it has exactly one such. For k>n/2 the number of permutations having a cycle of length k is binom(n,k)*(k-1)!*(n-k)!=n!/k. Hence (as others have noted) the proportion of permutations having a cycle of length greater than n/2 equals sum(1/k for k in range(n//2+1,n+1)) approx log(2).
"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
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.
so my initial thought was to make these journeys (make people fail together) as well, but also to look at what the others pull (it wasn't clear to me if this is permissible)
If it is you can increase your survival chance (obviously with more info you wont perform worse, but the exact odds for this I am not gonna look into)
First person follows the strategy suggested here, but if the prisoners waiting are allowed to watch he will also by his moves be reveal the number of each box he is opening.
This means if you see him open the box with your number all you need to do is open the box he opened before he opened that box.
If you know your box you can use your first few moves to reveal some more boxes. Start with the lowest number that has yet to be revealed and you can reveal 3 boxes (after the 4th box you will open your own number to save yourself.
If your number has not been revealed but your box was opened by another prisoner you can start your journey with his 4th move, giving you far more reach to go home.
An example where this extra info will save the day could be
box1: 3
box2: 2
box3: 1
box4: 5
box5: 6
box6: 7
box7: 8
box8: 9
box9: 4
giving moves:
prisoner 1: 1 -> 3 -> 2 -> 1
prisoner 2 (knows content of boxes 1 2 and 3): 4 -> 5 -> 6 -> 7 -> 2
prisoner 3 (knows contents of boxes 1 2 3 4 5 6) 7 -> 8 -> 9 -> 4 -> 3
All remaining prisoners know their number and can just open their box
Without the extra knowledge the chain 4 5 6 7 8 9 4 is too long and most of the prisoners will not find their number