# In simplest terms, what goes up, comes down?

The 100 Prisoners Riddle feels completely impossible even once you know the answer.

SchoolTube highlights high-quality Math videos that showcase the foundational subject of Mathematics or ‘Math’. Mathematics (from Ancient Greek μάθημα; máthēma: ‘knowledge, study, learning) is an area of knowledge that includes such topics as numbers (arithmetic and number theory), formulas, and related structures (algebra), shapes and the spaces in which they are contained (geometry), and quantities and their changes (calculus and analysis). Most mathematical activity involves the use of pure reason to discover or prove the properties of abstract objects, which consist of either abstraction from nature or—in modern mathematics—entities that are stipulated with certain properties, called axioms. A mathematical proof consists of a succession of applications of some deductive rules to already known results, including previously proved theorems, axioms, and (in the case of abstraction from nature) some basic properties that are considered true starting points of the theory under consideration. SchoolTube Math videos feature teachers academics, students, and publishing professionals sharing their knowledge and learning experiences.

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