The Riddle That Seems Impossible Even If You Know The Answer

The Riddle That Seems Impossible Even If You Know The Answer

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 https://brilliant.org/veritasium get 20% off a yearly subscription.

Special thanks to Destin of Smarter Every Day (https://ve42.co/SED), Toby of Tibees (https://ve42.co/Tibees), and Jabril of Jabrils (https://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: https://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: https://www.youtube.com/watch?v=C5-I0bAuEUE
Vsauce2: https://www.youtube.com/watch?v=kOnEEeHZp94
Stand-up Maths: https://www.youtube.com/watch?v=a1DUUnhk3uE
TED-Ed: https://www.youtube.com/watch?v=vIdStMTgNl0

▀▀▀
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. – https://ve42.co/GalMiltersen
Winkler, P. (2006). Seven Puzzles You Think You Must Not Have Heard Correctly. – https://ve42.co/Winkler2006
The 100 Prisoners Problem – https://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. – https://ve42.co/Golomb1998
Lamb, E. (2012). Puzzling Prisoners Presented to Promote North America’s Only Museum of Math. Observations, Scientific American. – https://ve42.co/Lamb2012
Permutations – https://ve42.co/PermutationsWiki
Probability that a random permutation of n elements has a cycle of length k greater than n/2, Math SE. – https://ve42.co/BaezProbSE
Counting Cycle Structures in Sn, Math SE. – https://ve42.co/CountCyclesSE
What is the distribution of cycle lengths in derangements? In particular, expected longest cycle, Math SE. – https://ve42.co/JorikiSE
The Manim Community Developers. (2021). Manim – Mathematical Animation Framework (Version v0.13.1). – https://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

You may also like...

42 Responses

  1. Dr. DJ X says:

    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.)

    • kato093 says:

      How? Usually if a CD is in the wrong case, you just look in the case and it’s empty lol. Where do you ho from there?

    • twocsies says:

      The chance is 0% because your CD isn’t in any box, it’s actually in the last place you look – the CD player itself.

    • phineas614 says:

      @N. Z. Saltz if you could open more than half, you could open every box and you wouldn’t need the loop strategy and you’d be freed every time no matter what. You can’t just remove that parameter 😂

    • Soulife says:

      I just realized the failure rate was 69%, nice.

    • mizo mint says:

      What’s a CD?

  2. Luke Gorman says:

    The loop strategy was very easy for me to understand once you gave the solution, because it is actually the same concept that is used to solve a Rubik’s Cube blindfolded. The pieces can be moved around into many different permutations, but they from loops (called cycles) which you can memorize the order of to solve it without even looking at the cube. Very interesting how two unrelated problems can be solved in the same way.

    • GainDamage says:

      Blindfolded, phew… Never even considered doing that, although beating it in 36 seconds at best. On avarage i’m around 50-70 seconds though.
      But blindfolded requires you to kinda solve it in your head before you even start to turn any side of it… Which i find impossible for me to do ^^

    • Dat Phan says:

      Yeah me too, thought about the blindfolded when heard the solution, though it’s not a similar problem.

    • oscaar_39 says:

      Wow I’ve always been scared of trying to learn blindfolded but this comment gave motivation, thank you:)

    • Rajitha Wijesinghe says:

      I still cant understand how you’d solve rubiks cube blindfolded. I mean i can do it in 40 seconds with carefully watching the thing.

    • Mike Barrientos says:

      @Luke Gorman ohh makes sense

  3. Corey Smith says:

    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.

    • QuestionedSanity says:

      @Hans Schwarz This is wrong. It is correct that determinism doesn’t matter, but the real reason the loop method is superior is that it coordinates successes among the group. In particular this means it does actually help if you only get to open one box, and in fact this situation makes it clearer why it works. If everyone opens one box they can only succeed if they all choose different boxes, it is therefore clear that you improve your probability of group success as long as you coordinate to never have 2 people open the same box. This means that coordination is the important part, it just happens to be the case that the optimal method of coordination in the many box case is the loop method.

    • Hans Schwarz says:

      a deterministic aproach doesnt make something more likely, just for being deterministic. It gets more likely, because the probability of the biggest loop being length 50 or less is higher than the random aproach. if every prisoner could only could choose one box to open the aproach wouldnt impact the result. So the deterministic nature doesnt have a part in it, but rather the finite setup and structure of this riddle in combination with the right strategy.

    • Chris Hillery says:

      So it turns it from a game of chance into Candyland.

    • Mark Muller says:

      Yep, in other words the strategy creates a finite system of loops that is predefined as a winning system or a losing system with a 30% – 70% ratio.
      The strength of the strategy is about that the individual actions doesn’t really matter, once the strategy is chosen the entire system of loops 4:45 is automatically determine and it’s either a winning system or a losing one (30 – 70)

    • Haithem Ghanem says:

      +

  4. Literally Shitler says:

    I like how _Smarter Every Day_ asked *”teach me.”* More people need this response in everyday life. Humility and the willingness to learn something you don’t know.

  5. BigPapaMitchell says:

    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.

    • reem asraf says:

      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

    • Flo says:

      @Irakyl I feel like Derek’s explanations often aren’t simple enough 😀 it’s much easier to explain when you just make clear that the exceptions to the “loop-rule” are impossible given the problem

    • Flo says:

      I thought that was kinda obvious as soon as Derek presented the strategy. Obviously there cannot be any dead ends when each number is still in one of the boxes. I.e. no empty boxes and no boxes with no number on them, which is obviously both not possible here

    • Daniel Reyes says:

      Your right everyone is on the chain, but not being on the chain is just a death sentence for the other prisoners, not the one who had just found his number. i dont really know what the point of this is besides just being an exercise. although when your sitting in front of a computer all day you start to come up with creative ways of thinking

    • godgige says:

      @MasterHigure interestlingly I found that explanation to be perfect for my taste, but it might be that I already understood why is that (the loops) beforehand. Anyways great video!

  6. Aaron S says:

    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.

    • Deynoh Muturi says:

      @AleXander 31%

    • Steven Garner says:

      @Hriday Desai Even if their number isn’t the 50th, they are still allowed to open 50 of the boxes. They wouldn’t have to, but if they were to check they could know whether it was success.

    • Werner Trügler says:

      @E B it’s the latest possible outcome if the first 49 are all on the same loop. very unlikely to happen. all know they have won as soon as the sum of successful loop lengths is 50 or more. so if prisoner 1 succeeds with a 30-box-loop, the second with a 17-box-loop and the third with a 4-box-loop they will succeed by 100%.

    • Werner Trügler says:

      @Urs Utzinger no, it means exactly that. finding your own number at position 50 sends you back to position 1 and the loop is closed

    • Werner Trügler says:

      @Nicole Fallen that cannot be a fact because it’s not true. there can be 5 20-box-loops.

  7. Wouter Pomp says:

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

  8. Dima T says:

    Feeling like this strategy of binding together multiple attempts might potentially work in so many other fields of science, not only in this question. Can be powerfull tool.

  9. Mark Pariente says:

    An intuitive way to understand why this strategy results in such a higher chance of success is that there is additional information present in the system in the form of “mappings” between the number/label of each box and the number contained inside the box. When every prisoner chooses random boxes this information is not used. The presented strategy uses the mapping information to allow prisoners to coordinate (create a shared fate) which increases their chances of success.

  10. Chad Eichhorn says:

    This happens on a much smaller scale when my family does Secret Santa presents! Most often, the loop of who-has-who includes all 6, but plenty of times there’s a loop of 4 and 2, or two loops of 3. Only once ever have we had 3 loops of 2.

    • IceCreeper28 says:

      @Chennebicken By chance, do you know one? Would really like to read up on it.

    • Chennebicken says:

      There are shuffling algorithms and protocols, you can use to randomly assign a name to each person, such that just one big loop will be formed.

Leave a Reply

Your email address will not be published. Required fields are marked *