Dipublikasikan tanggal 29 Jun 2022

The 100 Prisoners Riddle feels completely impossible even once you know the answer. This video is sponsored by Brilliant. The first 200 people to sign up via brilliant.org/veritasium get 20% off a yearly subscription.

Special thanks to Destin of Smarter Every Day ( ve42.co/SED) , Toby of Tibees ( ve42.co/Tibees) , and Jabril of Jabrils ( ve42.co/Jabrils ) for taking the time to think about this mind bending riddle.

Huge thanks to Luke West for building plots and for his help with the math.

Huge thanks to Dr. Eugene Curtin and Dr. Max Warshauer for their great article on the problem and taking the time to help us understand it: ve42.co/CurtinWarshauer

Thanks to Dr. John Baez for his help with finding alternate ways to do the calculations.

Thanks to Simon Pampena for his input and analysis.

Other 100 Prisoners Riddle videos:

minutephysics: www.youtube.com/watch?v=C5-I0...

Vsauce2: www.youtube.com/watch?v=kOnEE...

Stand-up Maths: www.youtube.com/watch?v=a1DUU...

TED-Ed: www.youtube.com/watch?v=vIdSt...

▀▀▀

References:

Original paper: Gál, A., & Miltersen, P.B. (2003). The Cell Probe Complexity of Succinct Data Structures. BRICS, Department of Computer Science, University of Aarhus. All rights reserved. - ve42.co/GalMiltersen

Winkler, P. (2006). Seven Puzzles You Think You Must Not Have Heard Correctly. - ve42.co/Winkler2006

The 100 Prisoners Problem - ve42.co/100PWiki

Golomb, S. & Gaal, P. (1998). On the Number of Permutations on n Objects with Greatest Cycle Length k. Advances in Applied Mathematics, 20(1), 98-107. - ve42.co/Golomb1998

Lamb, E. (2012). Puzzling Prisoners Presented to Promote North America's Only Museum of Math. Observations, Scientific American. - ve42.co/Lamb2012

Permutations - ve42.co/PermutationsWiki

Probability that a random permutation of n elements has a cycle of length k greater than n/2, Math SE. - ve42.co/BaezProbSE

Counting Cycle Structures in Sn, Math SE. - ve42.co/CountCyclesSE

What is the distribution of cycle lengths in derangements? In particular, expected longest cycle, Math SE. - ve42.co/JorikiSE

The Manim Community Developers. (2021). Manim - Mathematical Animation Framework (Version v0.13.1). - www.manim.community/

▀▀▀

Special thanks to Patreon supporters: RayJ Johnson, Brian Busbee, Jerome Barakos M.D., Amadeo Bee, Julian Lee, Inconcision, TTST, Balkrishna Heroor, Chris LaClair, Avi Yashchin, John H. Austin, Jr., OnlineBookClub.org, Matthew Gonzalez, Eric Sexton, john kiehl, Diffbot, Gnare, Dave Kircher, Burt Humburg, Blake Byers, Dumky, Evgeny Skvortsov, Meekay, Bill Linder, Paul Peijzel, Josh Hibschman, Timothy O’Brien, Mac Malkawi, Michael Schneider, jim buckmaster, Juan Benet, Ruslan Khroma, Robert Blum, Richard Sundvall, Lee Redden, Vincent, Stephen Wilcox, Marinus Kuivenhoven, Michael Krugman, Cy 'kkm' K'Nelson, Sam Lutfi, Ron Neal

▀▀▀

Written by Derek Muller and Emily Zhang

Filmed by Derek Muller and Petr Lebedev

Animation by Ivy Tello and Jesús Rascón

Edited by Trenton Oliver

Additional video/photos supplied by Getty Images

Music from Epidemic Sound and Jonny Hyman

Produced by Derek Muller, Petr Lebedev, and Emily Zhang

Special thanks to Destin of Smarter Every Day ( ve42.co/SED) , Toby of Tibees ( ve42.co/Tibees) , and Jabril of Jabrils ( ve42.co/Jabrils ) for taking the time to think about this mind bending riddle.

Huge thanks to Luke West for building plots and for his help with the math.

Huge thanks to Dr. Eugene Curtin and Dr. Max Warshauer for their great article on the problem and taking the time to help us understand it: ve42.co/CurtinWarshauer

Thanks to Dr. John Baez for his help with finding alternate ways to do the calculations.

Thanks to Simon Pampena for his input and analysis.

Other 100 Prisoners Riddle videos:

minutephysics: www.youtube.com/watch?v=C5-I0...

Vsauce2: www.youtube.com/watch?v=kOnEE...

Stand-up Maths: www.youtube.com/watch?v=a1DUU...

TED-Ed: www.youtube.com/watch?v=vIdSt...

▀▀▀

References:

Original paper: Gál, A., & Miltersen, P.B. (2003). The Cell Probe Complexity of Succinct Data Structures. BRICS, Department of Computer Science, University of Aarhus. All rights reserved. - ve42.co/GalMiltersen

Winkler, P. (2006). Seven Puzzles You Think You Must Not Have Heard Correctly. - ve42.co/Winkler2006

The 100 Prisoners Problem - ve42.co/100PWiki

Golomb, S. & Gaal, P. (1998). On the Number of Permutations on n Objects with Greatest Cycle Length k. Advances in Applied Mathematics, 20(1), 98-107. - ve42.co/Golomb1998

Lamb, E. (2012). Puzzling Prisoners Presented to Promote North America's Only Museum of Math. Observations, Scientific American. - ve42.co/Lamb2012

Permutations - ve42.co/PermutationsWiki

Probability that a random permutation of n elements has a cycle of length k greater than n/2, Math SE. - ve42.co/BaezProbSE

Counting Cycle Structures in Sn, Math SE. - ve42.co/CountCyclesSE

What is the distribution of cycle lengths in derangements? In particular, expected longest cycle, Math SE. - ve42.co/JorikiSE

The Manim Community Developers. (2021). Manim - Mathematical Animation Framework (Version v0.13.1). - www.manim.community/

▀▀▀

Special thanks to Patreon supporters: RayJ Johnson, Brian Busbee, Jerome Barakos M.D., Amadeo Bee, Julian Lee, Inconcision, TTST, Balkrishna Heroor, Chris LaClair, Avi Yashchin, John H. Austin, Jr., OnlineBookClub.org, Matthew Gonzalez, Eric Sexton, john kiehl, Diffbot, Gnare, Dave Kircher, Burt Humburg, Blake Byers, Dumky, Evgeny Skvortsov, Meekay, Bill Linder, Paul Peijzel, Josh Hibschman, Timothy O’Brien, Mac Malkawi, Michael Schneider, jim buckmaster, Juan Benet, Ruslan Khroma, Robert Blum, Richard Sundvall, Lee Redden, Vincent, Stephen Wilcox, Marinus Kuivenhoven, Michael Krugman, Cy 'kkm' K'Nelson, Sam Lutfi, Ron Neal

▀▀▀

Written by Derek Muller and Emily Zhang

Filmed by Derek Muller and Petr Lebedev

Animation by Ivy Tello and Jesús Rascón

Edited by Trenton Oliver

Additional video/photos supplied by Getty Images

Music from Epidemic Sound and Jonny Hyman

Produced by Derek Muller, Petr Lebedev, and Emily Zhang

## Komentar

Something seems wrong at 9:00 What is the probability of a loop of length 1? (Can't be 1/1) Length 2?

@Veritasium Another way to word it is to say you would find your number in only 1 box out of 100 in a loop of 100. then 1 out of a loop of 99 and so on, but you then just calculate based on which scenarios you succeed vs fail. In case this helps anyone understand the math.

To find the probability that a loop of length p for a fixed p with p > n/2 you proceed like this: Select p values out of n, n chose p = n!(p!(n-p)!) ways to do so, then create a cycle of length p, (p-1)! ways to do so, then arrange the n-p values remaining, (n-p)! ways. So in total: n!/(p!(n-p)!)(p-1)!(p-p)! (call this A) to create a configuration with a cycle of length p. Divide A by n! to find probability to get 1/p. This work because we did not overcount configurations in calculating A If p is less than n/2, formula A would count several times any configuration that has more than one cycle of length p, of which there would be more and more as p decreases. So to get the actual probability of a cycle of length p (where p < n/2) you would have to use a more involved calculation using the principle of inclusion-exclusion. Note also that 1/(n+1)+1/(n+2)+....+1/(2n) converges to ln(2) = 0.69314718056. So whatever the value of n there is a probability of at least 30.6% that the convicts will be freed.

@John Smith you will always find your own number if you start with your number box since there are no duplicate number boxes and no duplicate numbers

@Arturas Liutkus since there are no duplicate numbers 1 number can only point to 1 box so if you start with your number box you will always be on the right loop

9:00 is sus

As somebody that's tried tracking down a CD left in the wrong CD case, I can attest that the loop strategy does indeed work 31% of the time. (The other 69% of the time it turns up weeks later on the kitchen table.)

LoL

@Mcroostr I have no idea what comment you’re replying to, but there’s no way I said that lol re-read whatever you thought I said

@alveolate hermeneutist also works for game cartridges and boxes.

@Tyler Grant so all humans can only use what their generation uses for music? I’m too old for Spotify?

Lol😂😂

If you think the riddle is hard, imagine trying to convince 99 fellow prisoners to follow the plan to the letter.

@Christian Krause Obviously we don't have enough information. We don't know if Martin is right handed, and we don't know if he prefers chocolate or strawberry ice cream. We also don't know if he bites his nails or has a birthmark on his left shoulder.

Then i have another riddle for you: You are sitting in a restaurant and listening to the neighbors table. You listen to three different woman talking. a) One says: I have two childs, Martin, the older child, just got his driver license. What is the probability for her other child also being a boy? b) Two says: I have two childs, Martin just got his drivers license. What is the probability for her other child also being a boy? c) Three says: I have two childs, Martin just got his drivers license. He was born on a wednesday. What is the probability for her other child also being a boy? SOLUTION: a) 1/2, b) 1/3 c) 13/27 Explanation: b) Not possible is the birth of G/G, possible is B/B, G/B (girl older) and B/G (boy older). Each of the three B/B , G/B and B/G are equal with a probability of 1/3, but only on B/B the other child is a boy, so it is 1/3. a) As Martin is the older child, the question is simple: What is the probability for a new born child being a boy. What is the probability for your own next child being a boy/girl. It is 1/2. The difference is, that Martin is "fixed" in the birthorder being said he is the older one. c) This one is really hard: The more you "fix" one of the child in the birthorder with detail information, the more the probability increases from 1/3 to 1/2 being a boy. In this situation we have to draw: B/B G/B B/G 1234567 1234567 1234567 1oooxooo 1oooxooo 1ooooooo 2oooxooo 2oooxooo 2ooooooo 3oooxooo 3oooxooo 3ooooooo 4xxxxxxx 4oooxooo 4xxxxxxx 5oooxooo 5oooxooo 5ooooooo 6oooxooo 6oooxooo 6ooooooo 7oooxooo 7oooxooo 7ooooooo The x marks all wednesdays and the "o" marks all other weekdays the second child could be born. The sum is 4x7 -1 = 27 possible birthdays. Only all events in the left diagram (2x7 - 1 = 13) marks the events where the other child is also a boy.

xd

@senni bgon you've clearly never been in prison. Or met someone with ADHD.

No letters, just numbers, ha ha.

I paused at 3:44 to try this method out using Python code. I ran the code 100 times, of which 32 runs were successful (every prisoner was able to complete the task under the given conditions). In other words, it achieved a probability of 0.32. Very close!

Bruh if u can code this I think I need u to be my tutor

@grys I hope you saw my c code for this riddle, if not, I can post it again for you.

@grys Welcome. c is a great computer language, but like anything else, has its flaws and limitations.

@David James True. I will go back one day hopefully to polish it. Thanks for your replies! As a beginner python coder (who knows nothing and picked python to start with), I do hope to be able to expand to other languages in future as well. Starting with C - seems practical.

I wanted to do this but I suck at coding XD

My Chemistry teacher was OBSESSED with this channel in his high school years (he's pretty young, yeah), and I just had to check it out for myself. I've always had a bad relationship with Math because most of my teachers were douchebags, but these videos are helping me see it through a new perspective. It's still frustrating and confusing at times, but it's oddly cool nowadays. It gets less tiresome to calculate stuff now. Thanks awfully, dude! 😄

Veritasium is amazing, but check out 3blue1Brown as well which is fantastic for learning and then Numberphile for more esoteric subjects.

@herlocksholmes1888 Oo nice! A heads up tho, organic chemistry tutor is more of tutorial/learning channel, great for clarifying things for exams and stuff. It's not an edutainment channel like action lab so it might be boring to some but he explains things so incredibly well that I don't really mind it

@Primus2004 I see what u did there 🤣

@Primus2004 Literature is a really interesting field of studying, I adore (most of) the classics I've read so far. I'm learning how to like Mathematics, slowly. My plans for the future are to be as good in one as in another, but if you want to especialise only in one, then hey, that's amazing! I'm rooting for you from where I am

Win I wuz yung I luvd math. But win I hit the age uv 5, I intird graed kindergarden. So I desided tue fokus strikly on literuchur. I think yue kan agrE, I maed the rite choi… the rite chio… the rite…… fuk it, yue no wut ime triing tue sae.

This is why I have such a deep appreciation for those who are great at math. I have no idea how this was figured out and I don't need to because we have people like this! Thank God!

can someone explain to me at 8:35 I dont understand that much, the unique loops of 100, and total permutations relate to the possibility of getting 100 numbered loops

randomly, what is the expected time until one population makes it through? Is there a meta-scheme of renumbering which raises your probability of success even more?

6:35 I like that Derek's "random" numbers were all odd numbers. We have a bias towards perceiving odd numbers as more random than even numbers. Even more so, of the 9 digits in these numbers, only a single one was even.

this is a random thing but i notice usually when asked for a random number, if they do use an even number people usually say something in its sixties

My guy didn’t even say the boxes were labeled in the text screen.

Wow..! mind blown again.

@Chance yeah thats what I also thought about

@Jynx 2.8% for total randomness, but for people its not like this. Derek could not even see that, but his mind for some reason picked them all odd. Also I think thats just because odd numbers seem more random to our brains.

I've seen this riddle so many times, but this is one of the most efficient way to explain "Why" rather than just an optimal solution. This is why I love this channel

@Kinglink Reviews it's not that simple. The video only provides a solution. There's no proof of it being the optimal one. Edit: I did look into it and there's a pay-walled article proving that this strategy is indeed equivalent to any optimal strategy possible.

@Sudeep Singh because this is one of the few that either solves it for everyone and maximizes the chance they win. Other solution doesn't guarantee the prisoners will ever find their number. If you think there is a better one you might want to propose it and change how people think about this problem.

But why is this the optimal solution?

strategy is a way to synchronize the wins and fails

I think the tricky part of finding the answer to this is realizing that even with this strategy it is more than likely they will not win. It's hard to consider different strategies because any one you think of will not be a "good" strategy and will not stand out to you.

@fallen neberu - Well, open up to 61 boxes.

a fair puzzle would be to allow prisoners to open as many as such that the probability converges to 50%. The answer is 60.65. So, prisoners should be allowed to open 60 boxes.

@Zara Bisho Explain how they're nonsense

all these strategies are complete nonsense, everything shows time

That’s why I would just cheat 🤷♂️ And if that fails then RIP me

As soon as I was presented with this puzzle, my first thought was to find a way to make the individual prisoners' chances of success correlate with each other (didn't actually find the trick by myself, though). Once you break independence between the guesses, you start making gains in overall success. It'd be interesting to see how the limit changes as you alter the proportion of the boxes each prisoner is allowed to open.

@Bradbury If we solve the equation 0.5 = 1 - log(1/x) for x we get x = 1/sqrt(e) which would be about x = 60.65%, so it checks out.

This was something I was curious about myself. I can't do the math, but I ran some simulations. After 40k iterations, I found that the longest loop was

yep, the solution is similar to the "lets make a deal" door solution. you're playing non-intuitive games with chance, to maximize your chance of winning.

If the proportion is some x between 0.5 and 1 the logic still works basically the same and you should get 1 - log(1/x) success probability in the limit. If the proportion is some x < 0.5 it seems to get more complicated. I don't know whether there is a nice expression for it in that case.

To me, the neatest thing about this is that by definition, getting on the loop with your own number will ensure that unless you are on a loop of 100 numbers, there are going to be boxes that you never have to open because they aren’t on your loop. It doesn’t tell you by how much your odds increase, but you necessarily make you own pool of options smaller unless all are on one loop.

When you factor in the odds of one nerd convincing 99 other convicts to go with this strategy, your chances quickly fall back to zero.

@Tomasz Roll charisma check.

Lol

Not really.

True. I keep thinking if I was a prisoner there's no way I can convince them all. Average humans are too stupid.

ROFL

For anyone confused thinking the loop could fizzle by going back on itself somewhere other than the starting number (I was)... remember that no box mid loop will reveal another box already opened, other than the starting number, because that box was previously revealed and so cannot be in a future box. 10 to 11 to 12, 12 cannot have 11 because 10 already did.

Thank you! This was my first thought, and I was struggling to look at it through the correct lens. Your explanation was clear and simple

@Leo Jacksom That would be a 1 box loop. Which is an option. If you mean what if you got to box n and it had n inside, it would not since the box leading you to box n had n inside it.

But what if box n has slip n in it

Thank you! That was exactly my question

@FenixxTheGhost i am stupid 😅

Okay I was really confused about the part that says your number is guaranteed to be in the loop but now I get it. If your number is say, 43, then the loop will be open until you open the box that takes you back to 43, the first you opened. There's no such thing as closing the loop, without opening the box that leads you to the first box you opened. Hope that makes sense.

Another way of thinking about it is that the slip and the corresponding box must be in the same loop because the slip takes you directly to the box. If the box must be in the same loop as the slip, the slip must be in the same loop as the box (noting that branching isn't possible).

You are right

"your number is guaranteed to be in the loop" by definition. A loop is formed only when the number slip pointing to the starting position/box is found.

Where people are getting confused is in language. You ARE guaranteed to be in your number's loop. You are NOT guaranteed to find your number in the loop within 50 searches,. That's where the probability factor comes in is in the limited times you are aloud to search. The more boxes you are aloud to search, the longer the completable loops can be. If your number is in a loop 67 boxes long and you can only search 66 boxes you won't find it in time but if you were aloud to search 67 boxes you'd find it! The only way to win is if NO loops are longer than the number of aloud searches. Which is apparently 31% of random permutations of number placements.

An easier way to get the point across is that you can't short circuit the loop by closing it early because the same number can't be in 2 boxes... 1, 7, 55, 18, 7 is not allowed because then 7 would be in 2 boxes...

So all it is is a 31% chance that all the loops are 50 or less as long as every one follows the same process. Seems pretty straight forward to me. You could use the exact same strategy if they only got to open 30 boxes(or whatever the number could be) , its just that you would hope that the loops are all 30 or less. It made cense once he explained the loop right at the beginning.

🐕 is 31% chance.

I love this video, it eliminates the “chance” grouping it in a loop, you’re predetermined to fail or succeed.

I think the chance of convincing 99 other prisoners that this strategy is their best chance of survival is much lower than 31%.

At least it cannot be worse.

@SmellMyKKPP The chance of the other 99 would still be the same 31%, but since all have to succeed to win you have to multiply it with the 1/2 chance of the rogue prisoner. So with one going rogue, it's around 15.5%, with two it's 7.75% and so on.

I find it discriminatory towards prisoners that they always get used for these kind of math problems. They have rights too.

@Urukosh ! unfortunately though, the alternative to escaping was being executed..

@tsv I think he meant that 50% is the overall chance of the strategy being successful and the whole group being released from prison. The outcome of the strategy depends completely on the first person finding their number which is a 50/50 chance. Of course, if the first person finds their number then all the other inmates are 100% guaranteed to find their numbers, but the overall chance of success with this strategy is still just 50% because if the 1st person doesn't find their number (50% chance), the whole group is doomed.

What people don't seem to get is, that you choose the box with your number, so you can only come back to it by finding your number on a letter. If you start the loop on your number, it can only end on your number.

Agree. The video was confusing. I paused it at that point and then found your comment.

@Mr D that almost doesn't describe why, if your not listening to that sentence^^

4:50 "When you start with a box labeled with your number, you are guaranteed to be on the loop that includes your slip."

Thanks, that was exactly what I stopped factoring in.

You would be a good teacher, your explanations are very straight forward and easy to learn.

An interesting thing to note, that makes things less counter intuitive is that on average as many people find their numbers with both strategies. It's easy to see with the naive strategy 50% find their number. With the loop strategy. The only ones that don't find their numbers are the ones in the biggest loop if it's bigger longer than 51. So in 1 case in 100, 100 dont find it, 1 case in 99, 99 don't find it. So on average 100*1/100+99*1/99+...+51*1/51 = 50 persons don't find it. So on average 50% don't find their number. This strategy is a way to synchronize the wins and fails

I feel like the question “how can you guarantee you’re on the right loop,” is people actually thinking you can guarantee it in the 50 moves. You’re absolutely guaranteed to find your number in 100 moves, and that’s what you’re saying here, you’re not guaranteeing that the prisoners will be freed. But no box or slip will send you to a box or slip you’ve already opened.

Interesting corollary: If prisoner #1 (or any other prisoner) finds that his own loop has a length of exactly 50, he immediately knows there's a 100% chance of success.

@Urs Utzinger when you find your number - the loop has closed - cos it sending you back to the 1st box you opened. If 1st prisoner finds his number on box 50 - everyone is a winner - but only if it exactly box 50

@HomerOJSimpson we don't. If the first one completes his loop om the 49th box - the other loop(s) could just be one big of 51 numbers. Its theoretically possible for the first 49 to survive (all being on a loop of the same 49) and the 50th (and all remaining prisoners) to fail and die

@Bhorg C No it doesn't. There could be one loop of 50 and 10 loops of 5 (or any other combination for the other 50) It does mean they all surviving though

@HomerOJSimpson The first prisoner can only know for sure they will survive if his number is in exactly the 50th box he opens. If he finds it in less, he will have no way of knowing if a loop of 51 plus is there or not.

True!!!

The most important part of coming up with a solution (if you didn't know the riddle solution already) was always how do you constrain the actions of your fellow prisoners so they open the boxes systematically. This is important - by opening up the boxes systematically you can attempt to remove randomness. So a 'valid solution' is something that (1) directs someone where to start (2) directs them afterward -> but it does so for everybody (3) people have to start at different places bc they only can open 50 boxes. The loop strategy satisfies these three conditions. The second / most important thing to note is that: your number has not disappeared out of the room. It exists somewhere in there in one of the boxes.

to come up with this solution you'd really have to think outside the box. on behalf of all the other prisoners' lives - be sure not to slip up edit: all jokes aside, this is a really fascinating problem. i actually found it extremely logical. it really made sense - admittedly it's very surprising how big that probability is at first.

This is a really cool strategy to boost the probability up from random chance that much, and I didn't expect the probability to change so little as the number of prisoners in the puzzle increased. My followup question is, is there a way to prove that this is the optimal strategy, or is it possible there's a better one? (Of course, as people pointed out here, if this was a real situation there would also be the issue of convincing everyone to follow the strategy - IIUC even one person deciding to choose at random immediately halves everyone's chances, even though their individual probability doesn't change. So I think this strategy is also pretty good for that because what an individual has to do is pretty simple to explain, even if the reason it works isn't so simple.)

@Flame of the Phoenix you are correct this would work without communication. But it is not possible to combine this with the strategy in the video. It enhances the odds of of picking the right box by 20. Which makes it good compared to random guessing but extremely bad compared to a ~30 percent chance using the loop strategy

@David James They don't need to communicate.

@Flame of the Phoenix Communication in ANY way is not allowed according to the rules.

@Kieley Evatt If you spent long enough I'm sure you could find a way to implement this into a strategy.

@David James They don't technically know that he found his slip, but if he didn't there's no point in trying anyway, and so assuming he did not, would be assuming you lost. In other words, yes you do know that he got his slip.

I've played and watched pokémon evolution rando, (every level, random evolution, the evolution chains are set when the game starts) so the idea of any large group of variables creating loops even without the restriction of only 1 leading to 1, isn't really that big a stretch for me considering how often it happens in evo rando.

This channel is amazing. It reinvigorates my interest and curiosity about rational thinking and mathematics that my father instilled in me decades ago. I didn't really ended up practicing those muscles in my life but they are still there.

It makes me miss high school/uni math and I regret I didnt go to math school

I actually think that this is quite intuitive once you hear it. I didn't know it before, but as soon as I heard the following the loop part of it everything made sense.

I actually think that this is quite intuitive once you hear it. I didn't know it before, but as soon as I heard the following the loop part of it everything made sense.

I think where people get confused is not understanding the slip of paper 72 and the box numbered 72 as being a single unit of the loop, so they get confused thinking "well what if I pick the wrong loop". Until that bit fully clicks, it makes no sense. For some of us that part is intuitive once it's told to us but for others it just doesn't. I think him giving the visual helped but still. Math concepts are one of those things where you don't get it until suddenly you do, even if it was explained to you exactly the same every time

Your explanation is definitely clearer and easier to understand. Thank you so much, now I can have a peaceful sleep.

It is a similar concept to the Monty Hall problem in that everyone views each person as unconnected choices. However, as you have now linked two boxes together by going to the next one with that number you have now shared information between chances and changed the probability. Just like in the Monthy Hall problem, revealing a door provides new information, it is just down to how you use it and in this case it is a cleaver way of using it in these loops.

each box points to the next

As someone that went to prison, I can tell you with 100% confidence, that they got more chances to win by randomly picking boxes (one in 8*1^32), than 100 of them to agree to ANY strategy.

That is one in 8 which is 12.5%.

@Aaron I only found this video because I'm trying to understand how Michael knew how to save us all that day. I'm so glad he wasn't shanked with a sharpened toothbrush that one time he took two servings on cous cous Friday, leaving none for one-eyed Emine.

@Aaron Kerrigan Yeah, I acknowledged the somewhere in the comments. But I'm necer editing my comments - an old prison habit. 😛 Trust me, even if the leader orders them to do something, many of them would do the opposite if the leader has no way to know that they disobeyed. And he wouldn't have a way to know.

@WCW 31% ??

I think you meant 1 in 8*10^32, not 1 in 8*1^32 because those odds wouldn't be so bad. Also, you know you just gotta convince each gang leader and the lackeys will follow. So maybe 1 in 5 chance. 😂

This is indeed one of your best videos from what I've watched so far, Veritasium!

Oh hey, it's pretty much thinning out a 100 card singleton deck. Experienced TCG players will be quite familiar with this. It's an exclusive pool that decreases via elimination as you draw cards (or in this case numbers), so your pool goes 1/100, 1/99, 1/98 so on and so forth. Or in our world "Where the hell is that one combo piece in my edh/100 card highlander deck".

strategy is a way to synchronize the wins and fails

Lmao, imagine a 50 length loop giving 50 people a heart attack.

@Bruce Ricard Imagine every prisoner getting to box 49 and having a heart attack from anxiety.

You could have 2 loops of length 50.

You have no idea how much I love Destin for the "Teach me ..." Just like that.

This is actually, in my opinion, the least controversial thing he has posted in a while. Good work. This makes alot of sense to me, I would never have thought of it but it works

@ILYES The Monty Hall problem is just maths and is pretty controversial too. I remember everyone going crazy in the comments after that Numberphile video

@ILYES spoken like someone who knows nothing about math

Correct! The beauty of math is that there cannot be controversial things. Math and logic are the final judges, deciding which is right and which is wrong. If you read carefully the comments, no one is questioning the strategy, they simply complain they cannot understand it.

@magica that’s a pessimistic view.

A lot. Two separate words.

I think I understand it in a way that makes it simple to explain: Going from slip to box label eliminates any chance of randomly picking a box with a slip the same as the box number. With those out of the way, your chances are higher. Going from slip to slip keeps making your chances better because you know you won't pick two boxes with their slips switched around, and so on and so forth.

No, it doesn't quite mean that - nearly, but not completely; because you could find your own slip in the first box you open, the one with your own number on the outside. But that's OK, not a problem at all. What you can't do, you're right, is find the same slip and box number together for any of the other prisoners' numbers - which is one of the consequences of the strategy. it makes sure that every box is opened by at least one prisoner and that does, as you say, improve their chance of survival compared with random picking - although that improvement is not additional to the increased survival chance provided by the strategy.

My dad actually asked me this question about a month ago when I was with a couple of friends that particularly like riddles. I somehow got the answer right after a lot of guessing and yet I still only kind of understand it. Funny how complicated simple things can get if you dive deep enough!

Marco Sarli, ok einstein, solve unification theory

What is the probability that all 100 prisoners understand and follow the instructions? The calculation assumes 100%, but if we ran trials with random participants, it would not be nearly that high no matter what the incentive or how well it is explained to them because people are bad at following instructions. If I were in this group and we had unlimited time to strategize, I'd be drilling every person to make certain they knew the strategy and how to properly execute it.

This is magic of maths and probability. Great video and analysis of this problem.

you've got to admire these mathematicians for thinking out of the box

POV: YKW

@Pluto : With all do respect for your opinion, my opinion is that gender studies don't solve any problems but rather create new ones. But I won't be posting this on a video about gender studies because it would be rather disrespectful. If you don't enjoy maths, no problem, just don't watch video's on the subject matter.

@Gamina Wulfsdottir Slipping could save your life in some situations though.

The danger of thinking outside of the box is that you might slip.

ba dum tss

Thanks so much legend !! Literally the only tutorial that actually WORKED!

This is quite interesting I'm curious as to how it may apply in a daily-life scenario.. perhaps one 'Game of Chance' 😅

If the first person goes and opens their box on the 50th try, you know there's a loop of 50, meaning the maximum size of the other loop would be 50. Therefore, you'd know after the first participant that they've already won.

as soon as I was presented with this puzzle, my first thought was to find a way to make the individual prisoners' chances of success correlate with each other (didn't actually find the trick by myself, though). Once you break independence between the guesses, you start making gains in overall success. It'd be interesting to see how the limit changes as you alter the proportion of the boxes each prisoner is allowed to open.

For proportions larger than 50% you can actually just derive a formula for the success probability using the same arguments as in the video: 1-log(1/x), if x is the proportion between 0.5 and 1. For proportions smaller than 50% it is not that nice because the probability of a large n-loop is only 1/n for loops that cover more than 50% of the numbers.

I feel that "Metersen's colleague" should definitely get at _least_ a name check here! So, hat tip to Sven Skyum, reader emeritus at Department of Computer Science, University of Aarhus.

@Jesus Saves! so when's the last time you LITERALLY went to scientists to prove to them how effective your prayers have been?

That's a pretty cool name. Sven Skyum.

Your worries (yes, anxiety), depression, suicidal thoughts, EVERYTHING will melt away and be NO MORE when you lean on God and put your trust in him! When I have physical pain, I literally pray and the Lord quells it, that I am healed!! Know that there is power in the name Jesus Christ! His name casts out demons and heals! People are bothered by his name. The world hates the truth and wants to continue living sinfully! God's children are set apart (holy) and righteous.

Hey! Did you know God is three in one!? The Father, The Son, and The Holy Spirit! Bless him! Jesus died for our sins, rose from the dead, and gives salvation to everyone who has faith in him! True faith in Jesus will have you bear good fruit and *drastically* change for the better! Have a blessed day, everyone!! ❤

I'd love to know the process by which Skyum arrived at this answer. Years of work in a field where this kind of "loop" structure has been studied already? Flash of inspiration after a night of pizza and cola? Or was it an immediate "well, duh..., isn't it obvious?" savant-level intuitive grasp? That's as fascinating as the original riddle.

I would close my eyes going into the room and charge into the room, breaking everything. Then, I would open my eyes, and look for my number. It did not say you could not break the boxes, and since I opened my eyes after running into everything, its how I found it. The remaining prisoners don't even need to open the boxes because they are all broken. Proof: Opening something and breaking something are two different things. If they are not, I will measure the walls to make sure I only break 50% of the room, and its still a win win. The prisoners could look in the 50 broken boxes and open the rest. "When I opened my eyes, this is what it was like. This is how i found it, guard. I don't know how it was."

I actually find this concept very intuitive. We've played what we call "The murder game" in church camps many times and it goes like this: You write the names of all participants on pieces of paper and hand them out randomly. For the next days your goal is to kill the person you got by handing something to them. If they take it, they're out and your next goal is to eliminate the person that they were onto. Eventually you're gonna kill the person who was after you and end up with your own name so you win. And it happened very rarely that there was only one winner meaning only one loop in the whole group. Cause how probable is it that all the names line up perfectly? So I was already familiar with the thought of those loops and instantly knew what you were up to once you told to open the box with your own number.

@Michael Fay That sounds amazing

Ive played this at university as a get to know people exercise in an RPG and LRPG group- called assassins.... however you have to "kill" your target - for example with a water gun, or rubber knife... and cos you assassins stealth rules. Organised by a non player - so just one loop of names........ When I played it though.... lectures had been declared safe zones following an "incident" the previous year! Brilliant when you realise and are trying to get away from your assasin at full speed in a Student Union bar

@Fabri Very cool too! In Europe we have the game Werwolf that works similar, just that there is more Wulfs/Killers. And to fight them the other people get a bunch of cool powers like healing or being able to see the the identity of one person per night. Big hit.

@Christina Busse I’ve also been to church camp and we had a similar game called “Mafia”. every participant is seated in a biiiiig round table. they all have to close their eyes, and then someone (usually a guide, not a player) will randomly pick 2 people: 1 cop and 1 killer. the killer can execute if he does a wink at his victims. BUT, if he accidentally winks at the cop, he’s caught and everyone else win. the tricky part is that, once the game start, everyone has the right to accuse someone of being the killer (without revealing your own identity, of course). then, there’s voting to determine, at certain points, whom is eliminated. if the killer is eliminated, everyone wins. if the killer take out everyone (by either voting or wink), he wins. so even though is not with probabilities or stuff, it’s still a really good game because everyone start blaming everyone and you really don’t know whom is who so it’s really fun

@Fabri Depending on the group from 8 up to 40 people. You play it over the course of a few days while you're going along your usual programm. In the beginning everyone is super aware of not taking anything someone is handing them. Friends are daring eachother to take stuff from them cause only the person with your name can kill you and "what are the odds". As hours and days pass people start to forget about the game making it easier to strike, but don't try to obvious or they'll know it's you. It's so much fun!

I was intrigued when Derek talked to three different people about the problem, but then it was quite sad when I saw only one of them appearing for the rest of the video.

I'd love to see this in an actual experiment lol

Incredible video, as always. 👏🏻👏🏻👏🏻

be solved. In the end we get back to where we started. If the cycle contains all pieces we are done memorizing. But most of the time there are more than one cycle...

This makes sense. It reminds me of two things. Family Christmas gift giving, and an encouragement thing my grade 4 teacher did a few times during the year. I would have never guessed the answer, but it does make sense to me.

strategy 50% find their number. With the loop strategy. The only ones that don't find their numbers are the ones in the biggest loop if it's bigger longer than 51. So in 1 case in

2:43 in, trying to solve on my own. so my first thought is that the first prisoner's odds of success are 50% no matter the strategy which means the 2nd prisoner's odds of success must be much greater if this is the case then I'd argue some strategy like arranging the slips in the boxes in sequential order and having the successive prisoners estimate the location of their slip based on that before using the rest of their box checks to rearrange most of the other half, or in the event that their slip is not in the first half, to search most of the other half to find it. This way if a random 50% are in the first half then prisoner 2 should be able to check the 1st and 2nd boxes and know based on that whether his number is in the first 50 or last 50, and then still has 48 or 49 checks left. or if prisoner 1 checks box 1 and finds a slip with a different number then he checks the box corresponding to that number and continues for 50 boxes then moves each slip to its proper box, starting over with some other box if he completes a loop Then prisoner 2 comes in, checks box 2, and if he finds his number proceeds to check successive boxes until he finds a box with the wrong slip and follows the procedure prisoner 1 did or if he doesn't find his slip then follows the procedure prisoner 1 did until he does.

dang, I was wrong. I guess my solution counts as breaking the rules of not leaving the room the way it was when you entered but at least I was on the right track that the loops had to be part of the solution. I just didn't think about it until he mentioned the loop sizes that no rearrangement was necessary to get odds so close to 1/3rd and my assumption that the 2nd prisoner's odds of success are higher was wrong since it's not that they're higher but rather that they're very likely shared

What happens if prisoners decide to swap 2 boxes (in example 1=100 and 100=1) and then use this string strategy? That would mean 70% time they have a good change to cut the too long string and 30% of time they has small change to cause too long string. For me it seems like they would double their changes to survive.

Assuming you mean before prisoner one begins it all? because the rules don't allow moving the boxes once the exercise has started. Swapping two of the boxes would make no difference whatsoever; you could swap as many boxes as you like, redistribute the numbers inside, none of it would make any difference at all.

If you think it through, even on a chain with 51 boxes, all prisoners would still be able to find their box. Reason being, even if you have opened 50 boxes and didnt find your number, all prisoners should just point at box 51, hoping thats their number. That strategy only begins to fail with chains of 52 boxes or longer. ... except we have a rule that each prisoner has to see their number, rather than naming the box that contains their number. But it probably wont change much at the overall chances.

Complete loops with their number can exist in the loop they didn't finish or in the other 50.

That's actually a really good point. One of the rules says "if all 100 prisoners find their number during their turn in the room", so it's unclear whether they have to see their number within the 50 picked boxes or just point at the box they think their number is in.

Imagine coming up with this massively smart idea and still only having 31% chance not to get executed.

@Roskal Raskal they are gonna die either way. It's not possible. Their best strategy is to find a way to not even get in this deal. I have had 50% chances and still lose consecutive times. Just do head and tails, do it until you fail. You won't get far even with 50%.

@Ducky Momo Exactly. If every prisoner gets to open 99 boxes, then the purely random strategy succeeds with 37%, while the loop strategy succeeds with 99%.

the limit of 50 is arbitrary. if you increase that it goes closer to 1 and if you decrease that, it goes closer to 0

@IHateUniqueUsernames Framing effect. lol

@L.F. M. For each person who opens 50 random boxes vs uses the strategy, the chance of succeeding goes down by a half. If one person decides to open randomly, you'll all have a half of 30% chance of success, or 15%. If there are two, then half of that, so about 7%. If 10 I would think 31% * (1/256), or a fraction of one percent. Having a few people be idiots doesn't totally ruin your chances, but much more than 10 and you're better off trying to win the lottery.

It’s effectively a linked list with circular reference. This would be an effective CS problem.

This reminds me of a few card tricks I used to do as a kid, using just a basic deck of cards without the Jokers.

Here's how I would explain why you will always be on the loop that has your own number. In order for the loop to not contain your number, that means that you ALWAYS get the box that doesn't contain your number. Now ask yourself: what happens if you find the wrong slip? You move on to the next one. This means that if you have the wrong slip, then one more box is added on to the loop. This can only happen until you exhaust the boxes, at which point you've opened them all. (Of course, you would've used your fifty tries by then.)

One thing really interesting about this problem to me is that there are 100! = about 10^158 unique arrangements of the 100 slips in the 100 boxes. No single computer can check all of those in any reasonable amount of time, however we don't have to. The beauty of Monte Carlo simulation is for something with fairly high probability like this (over 30% in this case but even something small like 0.03% would work too), we only need to take a tiny random sample to get a good approximation of the correct (exact) mathematical answer. Even as few as 100,000 = 10^5 is enough to get an approximation of about 31% for this prisoner riddle as stated. My simulation program takes about 0.15 seconds runtime to simulate 100,000 outcomes/decisions and about 1.5 seconds to simulate 1 million outcomes/decisions. The problem with Monte Carlo simulation comes when the expected probability of what we are trying to simulate is super tiny. For example, if we simulated 100,000 outcomes and got 0 "winners", what conclusion can we draw? What if we re-ran the simulation and then got 1 "winner"? Our results would still be inconclusive. This is why math and computers are both useful to solve these types of counting problems because they help complement each others weaknesses / limitations. Not all people know how to solve counting problems mathematically, and if the # of boxes opened was restricted to 25 (instead of 50), then even fewer people could solve it mathematically, yet a computer can easily solve it for ANY number of boxes (1 to 100 for example) allowed to be opened by each prisoner, simply by changing one number in the code.

To be honest, I didn’t struggle with understanding the strategy, or how the loops work. I was confused about the 31%, but after you explained that this all made a lot of sense, and it’s really fun maths.

It's really just about the fact everyone has the same 100 boxes.

Cool, I was confused by all of it. Still am, but I was, to.

@Nimrod - all geeky things oops, totally missed that fact…thanks. So you are saying that if the ratio of total boxes to box choices is above two, it is no longer able to be approximated by the area under the curve 1/x?

@Avana Vana it fails for ln(3) because the integrating function is wrong. The formula of 1/x only applies for half or more, so you would expect any ratio from 1 to 2 works. For anything more than 2, piecewise integration has to be performed and the ratio should not pop out this easily.

@Nimrod - all geeky things right, that is obvious, but what I am saying is that doesn’t apply for ratios beyond 2, for example, if 50 prisoners choose 50 out of 150 boxes. 1-ln(3) does not yield a probability that makes sense in the real world. It does hold for the simple case of 50 prisoners and 50 boxes, since 1-ln(1) = 1, ie 100%.

What i love about mathematitians is, they'v got the brain to turn numbers in every ways possible , finding astonishing strats, yet , they'v got the hardest time explaining why it works... In this cas , the trick is not explained by math , it's explained by how you think about this problem. If they choose the loop strat , prisoners do a bet, they bet there is no loop longer than half their number, in our case 50 for 100 prisoners. Thus if they win their bet , they will all find theyr number. but if it happen to exist even one loop longer, they'r all fucked. the question is no more, "are they able to find their own numbers" but: "is the random assorment of number in the box including an over 50 loop". if your mind continue to think about the first problem it can't seize how the loop strat shifted the problem. first statment, how can they all find the good box second statment , please make it that no 50+ loop has been created in the first place. it's a good exemple on how the riddles work, they focus your ming on one point of view wile the answer is clear if your shift how you lokk over the riddle :)

I find this easy to accept. I feel like most people that are confused miss the part where each prisoner is allowed to open 50 boxes.

opens box 1, has #50 in it, opens box 50, has #1 in it... this theory is based on a guaranteed loop system and is flawed.

set. Now the change is 50% iso 30.x%, just like timing in Spectre/Meltdown. P.S. I see now I’m not the first one with this idea…

Alright I'm putting a wild guess as to the strategy right now before I watch the rest, if the first guy looks in the first half, and finds his number there's a slightly higher chance that the second guys number is in the second half, this is because that means only 49 cards in the first half could be the second guys number where as 50 cards could be his in the second half, and since you know that if his card wasn't in the first half you'd be executed anyway you can go ahead and assume they're in the first half. While I still think I made a good guess, after all you have to assume the previous prisoner got it correct whether he did or not, but I'll admit you made a better method. Having enslaved a computer to calculate the odds it seems like my method though not the most effective is around 20 times better than just guessing.

This is probably the only time I've found calculus to have been worth learning

Alternative explanation for why you're guaranteed to be on the same loop as your number: Keep in mind each slip only exists once. If you start at the box labeled with your number and follow the loop, the only way you could NOT eventually find your number is if you come across a slip pointing you to a box you've already opened, which of course leads you on the same path you've already been on, trapping you in an infinite sub-loop. But that is impossible, because that box you would be pointed back to was already pointed to by the slip you found just before that, and you can't find that same slip again. The only way you'll be pointed back to a box you already opened is that it's the box you started with, because you went to that one without having found the slip that points to it yet.

@serhan cinar How Prisoner54 ended up opening box 36 if there's only one box containing slip 36 (box 45)? It's impossible

@serhan cinar Well, he was supposed to open the box labeled with his own number, 54... That's part of the whole strategy. If he doesn't do that, then yeah, there's no guarantee for him to be on the correct loop.^^'

Let's say Prisoner54 opens box 36 contains slip 45, then opens container 45 which contains slip 36... Prisoner54 is out of the loop. How come he is guaranteed to be on the loop?

ah thank you this made me understand it

you made me understand it

As a sophomore in CS it’s weird to me that this idea doesn’t seem more intuitive. Of course I didn’t get the answer right 😂 but because it’s in the same vein as circular linked lists I’m surprised it’s not easier for CS people much more experienced than me. Ik it doesn’t correlate with CLLs that well but it was immediately where my mind jumped to because each box points to the next

I’ll remember this on my next sentence in prison. I have a feeling, though, that explaining it to the inmates will get me beat up (or worse).

I’m still a bit confused about when you explain that every number is on a loop with it’s own number. If the boxes are randomly assigned, wouldn’t that create independence between two? Your example seems to link them and negates that. I’d be curious to run a simulation in Python to see how this actually plays out.

@Chris Jones To be fair - i thought this was expertly explained in the video.

@Abdullah Waris Because there aren't any duplicate slips. If prisoner 1 sees 2-3-4-5-6-..., to make a subloop would mean they'd need to see one of those numbers *again*. For example 2-3-4-5-6-3. But there are no duplicate "3" slips. When opening a new box, the only possibilities are either seeing a number they've never seen before, or seeing their number.

@Yassine B. Why can't there be a subloop that connects to a number the prisoner had encountered after his own number

@Chris Jones It's less complicated than even that: the smallest possible cycle of boxes is 1, where it has it's own number in it. The next smaller cycle is two boxes, where box A contains slip B and box B contains slip A, completing the set. It scales in this way all the way to a cycle of a hundred boxes, and every single set has its own number in it (any group of boxes that does NOT have a slip number for every box number is not fully counted and is incomplete, it does not cycle).

IMO he doesn't explain this part well. It's the combination of two facts. FACT ONE: every permutation can be decomposed essentially uniquely into disjoint cycles (why? the naive process of making them works). FACT TWO: the cycle with your box number also has the box GOING TO your box number (why? because THAT'S WHAT IT MEANS TO BE A CYCLE).

This actually makes me think of running Secret Santa gift giving :)

Writing a research paper and still telling the reader to figure it out for him or herself is peak professor energy.

@Rinnegone Happens sometimes. I'm guessing either they were removed individually, or the accounts have been poofed. 🤷♂️

Why are the replies gone?

What would happened if all prisoners make a deal to go to just one box starting by box 1 and change the content of the box with the right box number. Eventually by the end of the experiment all of them will know that their number inside the box is the same as on the box. Who would know that they changed anything? Beauty of quantum physics ;)

My intuition for the increase in probability when using the loop strategy is more qualitative. See if this makes sense. When we open the box labeled with the slip number we just found, we also remove the chance of coming across that number again--as a box label or as a slip. In a sense, this allows opening a wrong box to not go to waste because, at the very least, that number is out of the picture now. This doesn't happen when boxes are opened randomly, in which case, the labels of the opened boxes have some chance to be found as slips.

That is a very minor effect that you would also have when opening boxes randomly as long as you don't open the same box twice. The increase in probability occurs because you are synchronizing the prisoners successes and failures with this strategy. Note that if one person on a loop fails then all (> 50) people with numbers on that loop fail and if one person on a loop succeeds then all people on that loop succeed. This bolsters the chance for all prisoners to succeed simultaneously (which you need for a win) at the cost of also having lots or prisoners fail at the same time (which does differ from the case that only one prisoner fails).

I still want to see these two scenario's play out head one.. and a few times to see if it really is true. If we do 100 tests, this method should work 31 times.. and the other method will not work once. I would honestly be surprised if it is the outcome.

@Zizzy7 _"I want real people to try it!"_ Now this cynical setting of a "survival game in a concentration camp" is something that many people find funny. You're not the first in this comment section who demands to try this out with real people. Strange enough, the leftists and "Anti-Trumpists" find it funny, too. But that's not really a surprise.

In the linked video in the description by Stand-up Maths it is done in practice with 10 people.

@NSW HSC Maths I want real people to try it!

Plenty of people here have coded the simulation. It works.

I was really hoping you were going to have 100 people try this out in real life at some point in the video

Intuitively, the solution was difficult to grasp. But it makes a lot of sense when he explains the math behind the problem. Sometimes our intuition can only take us so far. This video has made me really appreciate the value of math as a problem solving tool in a way that no traditional math class could.

Figuring out this loop structure does not seem like math. I'm not sure what it is, but it isn't something you can pop into a calculator or slide rule. Math easily finds the odds (the permutations) and it is a really big number. Your calculator will probably choke on 100 factorial.

It becomes more intuitive when you first find a way to increase your odds _at all_ . A simple way to increase your odds is this simple method: First prisoner picks boxes 1 - 50. Second prisoner picks the boxes 51-100 If the rest picks at random, your probability of winning is higher than everyone picking at random. Why? Well, the first prisoner has a 50% chance of winning. No changes here. However, the second prisoner has a slightly higher chance because: if the first prisoner found his number, that means that numbers 51-100 DONT contain the first prisoners number. For the second prisonder, that is one guaranteed failing option removed. If the first prisoner did NOT fond his number, then it must be in one of the boxes that the second prisoner is checking. _This doesnt matter though because the first prisoner lost already_ Meaning: *decreasing your odds in the case that someone before you lost doesnt decrease the odds of the whole game* . Thats also why the loop strategy works: It trades individual win% to increase collective win% because if one prisoner already lost, then the rest of the prisoners also losing doesnt hurt your odds

I thought of a nice way to phrase why the strategy works: the strategy works to reduce the amount of variation between prisoners' sets of guesses. This reduces the amount of things that have to go right for a successful outcome, just like flipping 3 coins instead of 10.

As a Mathematics major, I loved watching this video

What happens if we use the loop strategy but starting with random number(s) ? It feels like you possibly raise your chances of landing on a shorter loop to your number, is it compensated by the risk of "passing" your number or burning your chances on wrong loop(s) ?

If you use the loop strategy but starting with a random number then there are two big potential problems; (a) you make it less likely that you find your own number, because you are not guaranteed to be in a loop that includes it, (b) you might open a box that has its own number inside, meaning you will be forced to make another random choice (this might happen more than once); any additional random event always reduces the probabilty of you finding your own number compared to adhering to the strategy. The strategy is optimal, given the rules of the exercise; any deviaton from the strategy will only reduce the prisoners' chance of survival.

Your designated starting number has exactly the same chance as any other, randomly chosen number to land on a short loop so you would not see any effect in that regard. But you would reduce the coupling between the prisoners and thus the survival probability would drop as a result. The original paper actually proves that you can not do better than with the presented strategy, so most modifications to it will actually be detrimental or at best equivalent.

Best ever! I feel like this is more "fascinating" than it should be regarding the fact that the probability of success converges with an increasing number of prisoners. I'm challenging myself to come up with an intuition-based analogy where this will seem more obvious.

Me too!!

You would be a good teacher, your explanations are very straight forward and easy to learn.

Well, to be fair - I didn't knew about loops and stuff, but the only solution that I thought about - was to open your cell number and follow numbers, without knowing that this is the solution and how it works...

I think the most important thing to note about this is the prisoners' choices are no longer random variables. It's the setup of the boxes that is the random variable. If the prisoners' follow their strategy on a good setup they are guaranteed to succeed and on a bad setup they are guaranteed to fail. So it doesn't seem that surprising that they have a much better shot than if they are randomly choosing boxes.

I tried to make the first prisoner take 1-50, the second 2-51, and so on. And it doesn't work just because everything is determined. The chance is still (50%)^100. You still need the right strategy.

It’s similar to the Monty Hall problem. Avoiding complete randomness increases your chances.

@Blox117 That wasnt my point, but if you use a deterministic strategy, then that is the case.

Yes! Thank you for putting it that simply, I understand better now.

@Hans Schwarz its only random before the boxes are placed. once they are placed everyone's fate is sealed

The mathematical graph points to the science of chance. It lines up perfectly

I witnessed something strange. I watched this Video before but I didnt quite got it. About 2 weeks later I randomly thought of this problem and decided to watch it again. And surprise: It‘s really not that difficult if you let it sink in and then „redo it“/ rewatch it. Conclusion: If you find something difficult, let it sink in for a while and takle the problem, idea, …, you name it after some time has passed. It‘ll do miracles!

I feel like the biggest problem would be trying to convince every other prisoner to follow the strategy.

of next prisoner, he leaves the room after a long time. 5a. Next prisoner searches the same set of boxes as his successor. 5b. Next prisoner searches the other set of boxes.

Amazing video! I totally understood! But my question is : how do you know this strategy is the best?

@Entropie - Thank you!

There is a paper called "The locker puzzle" with the proof. In short the argument works as follows: Essentially when using the loop strategy the game is equivalent to a variant of the game with looser rules where you allow all prisoners to be present in the room and opened boxes stay open but the prisoners stop opening boxes after finding their number. In this new variant you can no longer influence the outcome with strategy, it is purely random. If there would be an even better strategy than the loop strategy it would imply that there also would be a way to improve the chances of the new variant which can not be done. For a more detailed argument I suggest seeking out the aforementioned paper.

Destin's "Teach me." is possibly the greatest example of doing science right. Or, you know, something to that effect. :D Possibly both most humble and most epic answer ever.

@TheMrVengeance As I said, that has nothing to do with doing science, exclusively. I’m not saying it’s not an important for a scientist to have, in fact I believe it is an important quality for anyone to have, but not a necessary or sufficient precondition for “doing science right”.

@Avana Vana - "Teach me" implies humbleness, a willingness to learn, curiosity, not being scared to perhaps be wrong about something. Without those qualities in a person, the scientific method does f*ck all for them.

@TheMrVengeance obviously not, but it’s the foundation, and the point is that asking someone “Teach Me” is not exclusive to science, nor is it an example of “the greatest example of doing science right”, as OP claimed.

Destin's "Teach me" gave me a Morpheus' "Show me" vibe.

@Avana Vana If you think the only thing you need to do good science is the scientific method, you've never done good science. Or more likely, never done science at all.

Everything else was explained really well, I still don't understand how a slip is must/ is likely to be within the loop that the box itself is in. It seems like that would require a setup in which it's set up by 1 person who already has each slip in its proper box, then they remove one slip, switch it with another slip in its own box and move on. It makes more sense to include another probability in which the slip is either in a loop with its own box or not. My apologies if he has already mentioned such a probability or if I'm mistaken

The prisoners number slip has to be in the loop because the prisoner starts with the box that has their number. The only way to close the loop is to get back the the first box which is only possible by finding the number.

Still needs a bit more of explanation on why if you open the box with your slid number you'll still find the box with your number inside. If you draw it, it becomes a lot simpler. The key is that you can't have loops within loops as the numbers within boxes are not repeated. There's only 1 and only 1 box containing your slid number.

This made sense to me just because I used to put the wrong dvds/videos in their cases and I would come up with ways to find what I was looking for as quickly as possible.

Puzzle @2:42 Best strategy: Refuse to participate, don't go into the room, don't attempt in the 1st place. Think about it. If they don't, they will all live! Sure in that life, they might have to lower their expectations but at least the chances of dying is lower. I am not an expert but the probability of them dying seems much below 50%. So basically the doubt is whether to choose to go through the room & take a chance of >>50% dying &

12:20 I have a better intuitive explanation: The only way you could start on a chain and not eventually reach itself is if either that chain forms a line with an endpoint, or that chain loops back on itself in the middle. The first one requires a box to have no number in it, which is impossible, and the second requires that two boxes have the same number, which is impossible, meaning that it must be the case it loops back on itself.

@M I think if you have very high IQ you can come up with it, this has 50 different stages for your brain to remember and think about in a same time to come up with a solution, 20 different stages leading to logic was around 140 IQ which is already genius. Paper might help and time but if you come up with that solution with your head and fast... very few.

My initial reaction was the same as Destin's, but then it slowly started to dawn on me. It's one of those things that's simultaneously intuitive and nearly obvious, but it just doesn't sound right at all. (And I feel like VERY few people would actually come up with the solution themselves, even if they've encountered an analogue before, I love things like this)

it could also happen if the numbers dont actually represent the boxes. box 50 could have number 999 on it, in which case you are screwed

Proof by contradiction. Assume it doesn't loop. You'll see very quickly that isn't possible. W e learned it like that at uni :)

a chain cant go back on itself in the middle cause in order to be on the chain the only slip with that number must be on the box previous to that number

I love this! The strategy really reminds me of linked lists

I don't find this to be unintuitive at all frankly, it makes a lot of sense, if every prisoner is starting from a different number, and following a set numbered path, then every prisoner is guaranteed to open entirely different boxes, which means there's 0 chance of redundant choices in relation to the other prisoners.

When you watch some science fun video, and there is question, "Where is the limit?". Opening 1000 boxes is already big task you mad man! :D

Loved this. Brain candy. And brilliantly explained.

my thoughts exactly

As a programmer, this reminds me of cyclic sort, and we deal with cycles all the time. Once you explained the strategy, it instantly blew my mind. Very clever solution!

@Klaus Meier After the first door is revealed, that game is over. There is no longer any chance out of 3. There are now only 2 doors, with a 50/50 chance. Changing doors will not, cannot change the odds. You're trying to force 2 different rule sets together that are mutually exclusive. You must factor the odds based on the new rules, because it's a new game.

@Loading yeah that is very clear! Yeah sorry i just replied to the last person who discussed this 🤣. Have a great day Loading!

@Loading Yeah, it’s my self proclaimed to be “Asia’s finest” university that put these core concepts in senior-level electives because compulsory common core courses take up more than 1 year worth of credits in a 4 year curriculum

@Harry Tsang May as well use a basic array at that point. No need to overcomplicate things. Also, this might just be for my university but fsm or fa are taught in 2nd year as part of the core courses.

@jon c yes Im aware, perhaps you meant to tag someone else? Edit: I think a more convinning way to explain what you just did was introduce the 100 door variation of the monty hall problem - you pick 1 out of 100 doors and monty reveals 98 other doors that are empty. If you choose to switch, you will win 99/100 times, if you dont, you win 1/100 times. Just ask them to try it themselves and they will quickly be forced to concede. Then raise the point that no matter how the number of doors change, the pattern of probability will stay the same where the remaining (y-1)/y probability will collapse on the other choice, weather it is 100, 50, or 3.

I still don't understand why a key to a box must be in the same loop as the box. It seems to me that a key could just be swapped with another key in a different loop.

Math is great if you can understand it. Personally it's not my strong suit, so I would just tell the prisoners to ignore the numbers on the boxes, and check the 1st 50 boxes they get ahold of. Place the numbers in a 10x10 square with their true value so the rest can find them without guessing.

Moral is that its is more efficent to do things in some order then random. In general, this avoids same mistakes then others do

I feel like a really interesting calculation would be with the hypothetical situation where if a prisoner guesses their number correctly, it removes it from the box and their number from the pool that the next prisoner would pick from.

What do you mean if the prisoner guesses their number correctly? How many guesses is each prisoner allowed?