Yes it is 1/1 but you have to treat it as an expected value. On average in any arrangement of 100 slips in boxes you should expect one loop of length 1. But sometimes you won’t get one. Sometimes you’ll get two or three etc. So if you had 1000 random arrangements of 100 numbers, you’d expect to find 1000 loops of length 1 500 loops of length 2 333 loops of length 3 etc. 10 loops of length 100 In the graph we show something slightly different, the probability that a loop of length L is the longest loop. If L>50 it must be the longest loop so the probability it exists and the probability it’s the longest are the same. If L
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.)
lmaooo what an amazingly real-life example of this! unfortunately... CDs are no longer common enough for most people under a certain age to really get this example :(
Hmmmm!!!?! Where theoretical maths meet the "real world" and provide the opportunity to show that the human species' success is tied to cooperation within the species as well as groups within that species...like family units. When we cooperate as a family to follow known solutions to problems we have a 1/3 chance of succeeding. Where as groups who refuse to cooperate towards a goal have an almost zero chance of success!!
The main point here is that "failing hard" comes with no harsher penalty than "failing little"....hence, you can redistribute your loss function to take advantage of this. Great video, btw!
I like to think that the people constructing the test purposely made no loops of >50, so that the prisoners could go free if they are intelligent enough to be worth returning to society (if they figure out the loop method then they will be given 100% chance)
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.
@@Ryuseigan Yes, because then the other 49 on that loop will obviously also succeed, and anyone else is on a loop of *at most* 50 (two loops of 50 is all there is), and thus will also succeed.
@@Ryuseigan yes really. The largest loop size of the remaining boxes cannot exceed 50, because 50 has already been used in that first loop prisoner #1 found.
@@Ryuseigan Yes, because there cant be same box on different loops. So a loop of 50 boxes would imply that remaining boxes at max can be 50 so no loop goes above 50 in size, hence 100% success
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.
As a former professional gambler, the key to understanding this in real-world terms is at 9:48. Every prisoner's individual chance of success is still 50%. The strategy works by making the prisoners' individual chances contingent on each other: linking them together. Imagine a related puzzle - the sadistic warden has been told that the median human heart rate is 75 beats per minute. He devises a game where he measures the 100 prisoners' heart rates. He has two large bins marked "UNDER 75 BPM" and "75 OR OVER", and he places each prisoner's ID tag in the bin corresponding to their measured heart rate. But there are two catches. Firstly, he has privately flipped a coin before the game to decide which will be the winning bin: the prisoners don't know which is which. And secondly, *all 100* prisoners have to win the game for them to be freed. So each prisoner's chance of winning is 50%. And with no collective strategy, the chance of everyone winning is 0.5 to the power 100. Tiny. But the collective strategy is simple: everyone does extremely vigorous exercise immediately before getting tested. Now *everyone's* heart rate is above the median. So although each person's individual chance of winning the game is still 50%, now the collective chance of winning is also 50% - because *everyone is now in the same bin.* Basically, that's how to grok the video's strategy for the boxes problem - in a sense it puts everyone "in the same bin" - and the bin is marked *"Are all the loops shorter than 51 ?".*
Notice that the Skyum "loops" strategy works because the room *is the same room for everyone.* And the strategy takes advantage of a particular mathematical property of the way the numbers are sorted into boxes *in that one particular room.* If there were 100 *different* rooms, with the numbers in the 100 boxes sorted randomly in each one, then the chances of *everyone* succeeding would again be huge. Because now all of the 100 outcomes would be statistically independent.
Did you retire early and because of success in that? One of my brothers learned a roulette betting strategy, something about (a) betting on 1/3 of the numbers each time and (b) setting a predetermined loss limit at which you'll stop betting. You win more often than lose, but do lose. He was kicked out of casinos for using it, even though it breaks no rules. I've been tempted for years to try such things but have always resorted to status quo of work a job for a paycheck....
I appreciate this version of the explanation to point out where the "magic number" comes from by reminding us that the criteria for "the bin" is arbitrary
They're all just people who went to jail for maximum time for possession of weed in the US and one of them happens to be a math professor who explains how it works to the other 99. (This is literally a thing that occurs in the US and especially among black and latino communities because racism! I'm being sarcastic, but this is true. You're less likely to end up in prison for possession alone if you're white and I hate that that's true still.)
The way I like to think about the solution: you're no longer betting that each individual prisoner will find their number with a pattern that they choose (arbitrary or intentional), but you're betting on the probability that a pattern (a loop exceeding a length of 50) does not exist in the set of boxes. And that's a static property of the set you're betting on, in contrast to rolling the dice every time on 50 different prisoners. So, in a way, you've already succeeded or failed by choosing the loop strategy, whether you know it or not. Random chance no longer has anything to do with the prisoners' choices (unless they mess up the execution of the loop strategy), but entirely on how the box set is arranged and the loop strategy that the prisoners decide to employ at the start. Fascinating mathematics! Thanks for sharing this!
With the implementation of the strategy you change an element of randomness in the problem. The randomness of the prisoners behaviour. Just like a conductor changes noise into order with the swing of a wooden stick based on mutual understanding of the symbolism of the stick. The power of cooperation, hence the saying a bad plan is better than no plan.
@@sonkeschmidt2027 I mean with this one, it's so much about the magnitude of difference if you notice this behind the hood pattern of loops. You could also create a very bad plan where everyone cooperates, like maybe prisoners might think that each should go 1. 1 - 50. 2. 2 - 51. 3. 3 - 52. ... 50. 50-99. 51. 51-100. 52. 52-1. 100. 100-49. thinking this is better than completely random. This is for example the first idea I thought to test if it would have any influence at all, what if they increase number one by one. I'm not sure if this actually will increase odds in any meaningful way. Didn't actually test it out, but I knew it definitely won't give near 1/3 odds. So I would say it's more about noticing this really obscure but effective strategy rather than cooperation really. You of course need cooperation to carry it out.
@@enzzz what is this obscure strategy going to do without cooperation? How you going to implement it? Or even find it out? You would need someone to come up with it and convince everyone to follow a strategy with just 30% chance of winning. That is not a good plan. It might be the best but it's not a good one. To get this to happen requires a shitton of cooperation.
_"that someone would decide this is stupid and just pick boxes at random"_ That's frequently a problem in real life. Not so much in the fabricated setup of the video. Persons with a strong determination are usually the ones which make the decisions, and not always they are very smart. Like this example from recent (and many others from less recent) history: Smart mind says: "Don't go to war against xxx, IT WILL NOT WORK." Strong will says: "Of course it will, you're a coward and a traitor." 20 years later, it did not work. Strong will says: "Nobody could have known that, therefore it was the right decision at that time."
Exactly. Every idiot deciding to go for random nubers roughly halves the chance of winning. Anyway, here is some useless math I spent half an hour on (what am I doing with my life?). Theoretically even with googol or googolplex people (assuming that we just don't worry abut time it would take to open half a googolplex boxes gogolpex times) you would have an over 30% chance of winnig, but when talking abut actual people, not idealized beings, this just doesn't work. Even with the googol people case and (10^-48)%, wich is 0.000000000000000000000000000000000000000000000001% people being idiots and choosing randomly, your chance would be(3/2^(10^50))%, wich i think is way under 1/10^10000, or 1/googol^100. When I plugged this into calculators (even the most precise ones I could find), they straight out gave me 0, witch speaks for itself.
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
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.
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.
@@christiankrause1594 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.
2:41 My strategy is that a prisoner picks a box and the number inside is the next box you should open. Example : 26 = 74, 74 = 36, 36 = 92, 92 = 11 and so on...
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.
I was thinking the same thing, his explanation with the link at 11:25 wasn't very helpful. He should have instead hammered on the point that you could never fail to find your number, you will never have to try again and find a different loop. When Dustin said "I feel like it's possible that you start with the loop but don't end up finding your number", Derek should have said "And what would that look like?" at which point you realise pretty quickly that it's impossible, and thus loop length is the only factor that determines your succes. Perhaps Derek could also have spent a little more time analysing the situation before starting his explanation. If the viewers felt like they discovered the properties of the loops themselves it would feel much more intuitive. Edit: if you still feel like this is unintuitive, like this is cheating math somehow, that this shouldn't be possible, consider the following: there is only one 'check' to see if the experiment is a succes or a fail, it's right at the beginning, if the starting configuration has a loop of 51 or higher. Imagine if the box configuration was rondomised for each individual prisoner, then the chance of all 100 of them passing would be astronomically low again, and all is right in the world.
@@irakyl Derek should've said "Then how would you manage to loop back to the box you started at?" Assuming we all agree beforehand that these are closed loops, I think that's the easiest argument for why you must be in the correct loop.
@@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!
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
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
Love this! The concept of loops does break the mind slightly, but is very logical once you look at it with a reduced number of boxes. I would never come up with this solution myself, however - eliminating randomness of prisoners' choices in this manner is truly ingenious.
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.
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.
A really incredible feature of the loop strategy is comparing how well it works even against random guessing with more chances to open boxes. For example, if each prisoner were allowed to open 99 of the 100 boxes, instead of 50, to find their own number, the total probability of success by randomly guessing is only 0.99^100, or 36.6%! (Whereas the loop strategy gives a comparable chance of success while only opening 50 boxes, and succeeds 99% of the time if you can open 99 boxes) If you were allowed to open 98 of 100 boxes, the chance of winning via random guessing drops to 13.3%, and to below 5% for 97 boxes!
I think the key to understanding why you are always in the loop that contains your number is that the slips are all unique. The only number that can complete the loop is your own because that's the only slip that can point back to another box you have already opened. If you open box 3 and find a 5 and then open box 5 to find a 7 you can't open box 7 and find another 5. It will either by 3 to complete the loop or a number you haven't seen already.
I think the key to understand is "there are only loops". And loops always go back to your start. --- My first thoughts viewing his proof are: Then why there are always only loops? => Or in other words why only loops can fullfill the requirement for a set of 1 to 1 pair to be all contained? => OR why the 1to1 and one-direction basic structure can only form a line or a loop? oh, this can be easily proven with induction. --- So we have the basic: there can be only lines and loops. --- why there are only loops is because the structure can only form lines and loops. Since lines has slip outside of box which is invalid in our scenario, there can only be loops.
For me, it was simpler to consider that the box and the number must be part of the same loop regardless of its length. Any box must be part of a loop that points to itself since all numbers are unique and are just a permutation, the worst case is just having to go through all the boxes. So if you start with the box with your number you know it is part of the correct loop.
For me, I just tried to break the strategy. How? By imagining that I didn't find my number for the first 99 boxes. That final box MUST complete the loop, there's no possible alternative and that's the WORST case. Every other combination (loop) containing fewer boxes will terminate faster at my number because that's the terminating condition.
Actually, it is because of the definition of the loop, all boxes and corresponding numbers must be part of the same loop. Since the number in the box gives you the box that gives the next number and so on and the loop can only end with the original box and the loop has to end.
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.
Your "intuition" definitely leads you down the wrong path in probabilities at least 76% of the time. The human brain is just not wired to deal with probabilities intuitively (and also 95% of statistics are completely made up)
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.
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
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's a small thing but I find Destin's response to your claim (5 seconds of deep thought followed by "teach me") is inspirational. He switched gears so fast from peer to student, it's the kind of attitude I want and he makes it look so simple.
Instead of having separate peer/student relationships, perceive every relationship as potential for learning, we can learn from young children, learn from old wisdom, learn from other perspectives, learn from animals, which is why Destin's reaction appears so simple, because he is always seeking to learn, it's not being in a learning mode, it's just a constant way of living/learning. This will sound trite, but instead of being inspired by it/want to do it, instead just do it, seek out what you might learn from any interaction, there's always something!
I like this warden. He has reasoned out that if he can turn all his prisoners into math wizards or at least willing to work together and trust one another, he can let them out.
After watching 3 times and then doing something else entirely, I finally understand the logic. The heart of this problem is in the sentence that begins at 5:30 minutes. Listen carefully to the few seconds before that and follow the logic for WHY all other prisoners in that loop will fail to find their number. That is what I originally missed. In this case, I chose several prisoners in this loop and convinced myself that, indeed, ALL prisoners in that loop fail to find their number, missing it by 1 box. Their number is in the 51st box that prisoner would have opened. I need to try a similar exercise for the nice guard to breaks the loop into two loops by switching just the contents of two boxes, but I think my brain is strained enough for one day. Hope this is helpful for others. It was a revelation to me. Thanks to the poster of this video!
This type of content is unbelievable! As an AP Calc and AP Stats teacher, it keeps me motivated to learn more and find more interesting problems for my students to keep them motivated.
@@ibrahim-sj2cr I dont think in this situation you are supposed to go to box 6. You stil go to your box 1, it is just some other box than before. I have not thought this through, but just from the top of my head, I dont see any issues with this.
I work in irrigation and we actually use closed loops like this! If I have zones numbered from 1-10 (for houses 1-10) but the stations do not follow the order of the houses, we just pick the first wire and move it to the correct order (for example: station 5 is house 1; put station 5 wire into station 1 slot, and station 1 into the next assigned order; repeat until finished). I’ve had 2-3 closed loops and always thought it was fascinating, really neat to see a video that carries into the profession!
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!
@@markingraham4892 Uh... no, that's not true at all. It's true that other systems CAN have equally good results (nothing better) but not ALL systems will. Take, for example, the system of "everyone search the first 50 boxes." That's a consistent way to search, but it would obviously fail.
Bravo, well explained! At 2:51 minutes where the problem is stated, the second line must state for completeness that the boxes are either numbered or will be arranged in a known preset configuration so the prisoners can prearrange using a numbering system that assigns each box a consistent number. I imagined all blank boxes with a number in it randomly placed somewhere in the room (not even adhering to a nice grid pattern) in which case this loop method would not work, nor the pairing that is explained later.
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!
@@Harshil_Uppal Maybe have an array of numbers, size 100. Fill the array randomly with values from 1 to 100. Then, every prisoner searches the array. Every prisoner can have up to 50 attempts. You use the strategy of "index_to_search = array[index_to_search]", where on the first attempt, "index_to_search = prisoner_number". Each search must last less than 50 attempts. If prisoner_number != array[index_to_search] and attempt > 50, the experiment fails.
The real “magic” of this solution is that it ties the probability of success to one single condition (the state of the “loops” in the boxes) instead of a repeated condition (the odds of each prisoner finding the correct number). You’ve immediately removed the exponential scaling of the probability. So even if you choose a sub-optimal method. Any method that is based on a single fixed condition is immediately an improvement.
That is quite certain indeed. But i think vertasium forgot that not everything will form a loop as a set of boxes can end up with a box that has its own number.
@@duitakarbhat that is only for the only for the prisoner that has the number of the box containing its own number. But not for the x - amount of boxes leading up to that one in the pointer line-up. For example : Box 1 points to box 2, box 2 points to box 3, box 3 points to itself. Hence, not everything needs to be a loop ( it can be a finite non looping set ), unless u put up the constraint that no box can contain its own number. Just handling this case asif it could only be closed loops therefore seems not logical.
for me it was clearer to see it in this way: the reason the loop ends with your own slip is because, excluding the starting box, you only open a box if you already have its corresponding slip, so no other loop is possible (no slip can point to a box you already opened because you already got that slip pointing to that box)
@@assemblywizard8 well you also will always find your slip if you can open 100 of 100 boxes. you will also not open the same box twice because you already opened it and see that it is open. this alone isnt really the "aha" moment
This is actually exactly how the turtle and hare algorithm works for arrays .Given an array on N+1 elements with numbers 1 to N, with only 1 element being repeated, you can actually find the repeated element using this concept. Though the algorithm is a little different, the concept is very similar. You can maybe make a video on that. It's a very interesting problem and a beautiful variation of Floyd's algorithm.
I wonder how you could find the one duplicate element using Floyd's algorithm. You may find it by chance if you use a random element to start with, but usually it would require to examine the complete loop structure. Or doesn't it?
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.
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)
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.
@@hansschwarz1338 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.
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
@@ngotranhoanhson5987 It is indeed bit tricky to understand, you can use a simpler analogy to understand it, suppose you roll a dice, the total possible outcomes would be 6, and lets consider we have to find the probablity of getting a even number. Here the sample space would be 6 (All possible outcomes), and the set of all even numbers on the die {2, 4, 6}, is of size 3, hence the probablity 3/6 i.e. 1/2. Similarly in the above case, the sample size would be all the possible ways we can put 100 numbers in 100 boxes and that is 100!. As we are finding the probablity of finding a loop of length 100, we will need a set of all possible unique loops of length 100. As explained in the video, that set will contain 100!/100 loops, so we divide that with the sample size of 100!. Hope that's helpful.
This riddle definitely seems impossible but the brute force approach confirms. Ran a program that played the scenario 50,000 times and yep... 3,450,000 prisoners died. Survival rate was 31% of the time. Nice work and as always, thanks for teaching us something new Derek!
I'm writing my own simulation for this, and I'm not getting the same results. Could I see your code please? I'm thinking I'm doing something wrong and looking to learn.
Works with 2 prisoners too who can both open 1 box each. If they don't discuss anything before and open one random box each, the probability of success is: 0,5 x 0,5 = 0,25 = 25% If they agree to both open the box labeled their number, then either they will both be wrong (because the guards swapped box 1 and box 2) or both be right if the box numbers match the slips. So a 50% chance
15:57 Whenever that music starts I know my mind has just been expanded. Been watching you since high school Derek and just about to finish my degree in Physics. Thanks for all the knowledge and inspiration over the years!
I think the counter-intuitiveness stems from the fact that the loop is no better than random selection for each individual attempt, but is way better for the riddle's success. Remember, the riddle is only concerned about ALL 100 people succeeding. It doesn't care for the 50 people who succeed on average. Anything that is not 100, is effectively 0. 100 is what the loop algorithm optimizes for. Despite not being allowed to communicate, prisoners can use the design of the riddle itself to collectively follow the same set of loops. Like putting all your eggs into one basket, following the same loops maximizes the chance of all 100 people succeeding. This is illustrated with the probability distribution at 10:24
what makes people think they dont get the correct loop is becausee they forget to start on their own number, if they choose a random number then they can get the wrong loop
Actually not at all. The loop strategy GUARANTEES that the prisoner is on the way to find his number. Because the box that had his number is by definition the last in the loop. The only thing that would stop him is if the loop is greater than 50 numbers. Random choosing strategies NEVER guarantee getting your number. If you phrase the problem this way, everyone thinks the answer is obvious.
WOW!!! That just blew my mind!!!! I was watching solving mystery videos because my teacher recommended it for the topic we were learning, and i came across this video and thought, "I MUST watch this", and it left me speechless. I subscribed just because of this.
You'd use up your strategy time trying to convince them it's smart and gives a 31% chance at success then someone will speak louder then you saying "all that work for less than the 50% chance we get picking randomly?" And then everyone dies
Same here. I had the same question that Destin did, but as soon as I realized that, unless the box you start with contains it's own (and hence your) number, you are guaranteed to be on the proper loop. It's only a question of how long that loop is. As soon as I was able to wrap my head around that, it made perfect sense.
I have a different solution that grants greater than a 31% chance. It approaches this as if it were a trick question, and still completely satisfies all the rules/requirements. "Each must leave the room as they found it." They found it with 100 closed boxes. They didn't "find" any boxes open nor did they find any information or clues regarding which numbered slips were in which boxes. On that premise, #1 (beforehand tells all of this strategy), and opens 1/50 (a 50% chance). He then takes ALL numbered slips placed in boxes 1-50 and he stuffs all of them in box #1 (just as he had told the rest of the group beforehand that he would do...Mind you; this is a "trick answer," but according to the rules, NOTHING specifies this is not allowed). Then, prisoner #2 (who was beforehand told of this overall strategy-and understand/assume the rest were as well for the sake of time), then opens boxes 1 (which now has all numbered slips which were originally placed in boxes 1-50) and he opens boxes 51, 52, 53.... (you get the point) to box 99 (50 boxes). As long as HIS number (2) isn't in box 100 (a 1% chance which lowers our overall group chance only to 49%!!!!), everything is still a go. Then, he also places all numbered slips he has now discovered (in boxes 1 & 51-99) all into box 1 (just like the first prisoner did). Now, prisoner #3 has a 100% chance now as he just checks boxes 1 and 100 (which have all the numbered slips in them as the remaining boxes are empty) and then he places the numbered slip located in box 100 into box 1 as well! (So now ALL numbered slips are now located in box 1). Prisoners #4, 5, 6 and so on only have to check box 1 and their chance is 100%, thus keeping our risk level/chance at 49%! All the way to prisoner 100. This way completely plays by the rules by the way according to the information/restrictions that was given us. As we only talked strategy beforehand, only one entered at a time, we did not communicate during, and we each left the room as we found it; with 100 closed boxes that never got moved. Yes, the SLIPS got moved, but we "left the room as we found it," because prisoner #1 FOUND the room with 100 closed boxes in such order. Also matching the approach of a "trick question/trick answer," you could also have prisoners 2-100 arranged tightly around the open doorway as prisoner 1 goes in, and all 2-100 could watch as he opens each box. They could each take notes on what box he opened and what number they witnessed him discover. And so on and so forth. This still allows for them entering 1 at a time as well as not communicating in any way with any of the others. Another way is to say ok the room is sealed but with glass walls. Just the way my mind works and another way of looking at it. These answers give me more peace about it than the one discussed in this video. However, the solution discussed in this video is more fascinating and I'm sure true math experts (I am NOT one I'm just someone who greatly enjoys strategy and basic wisdom/philosophy) will prefer it the way it is in the video for the math aspects!
@@user-bu9xh4sg6v they open what ever number is in the box then open that box see what number is in that then they go to that number and open that box’s d so on until they find there number
It actually becomes very clear and obvious when you understand the answer in full, it seems like what limits our understanding of how best to solve the problem lies within our understanding of the problem itself. Very cool and interesting problem and video, thanks for the education!
I actually had to pause the video and just sit back because my mind was so blown. I don't remember a video ever having this kind of effect on me. Very well explained. Thank you
Excellent video, but I think the question at 10:35, although answered with a very effective visual demonstration, is even more intuitively clear to answer. Simply ask the person to give you an example of such a loop where you start with your number but the loop ends without reaching it. They cannot, because it is logically not possible. By definition, the loop ends only when a paper slip redirects you to the original box, and if you started with the box that has your number, then that paper slip is your slip. In a worst-case scenario, the slip chasing takes you on a scavenger hunt across all 100 boxes (although the 50 box limit would have stopped you before then), but there is never any case where you enter a "wrong" loop. By definition, if you start with your box, then you're in the correct loop, because eventually *some* box has to have your slip, and then the slip for that box has to be somewhere else (because it's clearly not in the mentioned box, since that box contains *your* slip) and this goes on across either all 100 boxes or less. Problem solved.
Yep I would ask destin to come up with a scenario where the loop is closed, but doesn’t include yours. Like actually have him make up the numbers in the boxes and get that scenario He would soon realize you can only close the loop where it started (which is your number). It’s pretty intuitive
That's exactly what I thought. The visual demonstration didn't stick to me quite well so I instead tried to imagine a loop where you don't end where you started. I imagined 5 boxes to make the problem more simple, that way it's easy to see how you would always eventually end up with the initial number.
This is also the key to the probability being so high with this strategy - because all 100 prisoners start on a different number, you collectively guaruntee to enter every possible loop, and therefore find every number (unless there is a loop greater than 50).
I was imagining a "loop" that starts at my box, and then instead of coming back to my box, it reenters the loop at some later point. For example, 1..2..3..4..2. But that's impossible, because it would require two different boxes to contain the same number ("2" in the example). Thus the loop must eventually come back to my box.
Haha I got to that guy's reaction and now I'm not thinking these guys are as qualified to talk about statistics if they're racking their brains *that* hard thinking that the most unintuitive part of this problem is that your loop always contains itself. I guess if you aren't realizing that each box only has one slip pointing to it... But that was vital to the premise!
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.
And not created by them at all. Its a category theory loop. Took this s over 35 years ago. The same problem but worded different as in not prisoners is shown and proven in elementary category theory. Don't need all that stats to prove or show s. All one needs to know is how to categorize the problem and check where the functions associate then if s running link function appears. Lol category theory is like a cannon that swats fly problems like that
right? I love it, it gave me chills to hear because I feel like it's such a rare thing these days for people to admit they don't know something, let alone for them to actually ask to learn it
Really great explanation! Another way to see that boxes always form a loop when you follow the algorithm is that a box will always have a different number inside of it then the box's index (unless you happened to start with a box that has your number in it). There for since the boxes always have a different number inside it (and numbers aren't repeated), you will always be taken to a new box (until you've made a loop)
It would be really awesome to see the original reviews of that paper (from when is was submitted to publication). I bet those reviewers were also beaming with professor energy 😂😂
I was really confused at first on how whatever number you start with is guaranteed to be in your loop, but once I started to type out a comment questioning it I totally realized how it works. In order to finish your loop you have to end up back where you start, and since none of the boxes can be empty, you're guaranteed to be in some sort of loop.
Then you have two boxes which contain “3”… Every number occurs exactly once in all the boxes. If box 1 contains “3” then no other box have “3” you are guaranteed at this point that your loop you are on cannot have box which contains the same number (1 has 3, 3 has to have something else ie 5, then 5 has to have somethine else and so on, until you find box pointing you back to 1)
Try it with something small like 3 or 4 boxes. Whatever you try you will always see only loops. No dead ends. If you find dead end it means there are duplicates and some number is missing (duplicate took its place)
@@nicolass.5849 You have to end up back where you start in a loop. And since in this case you start at your own number, one of the boxes in your loop must also contain your number. If none of them did, you would never be able to finish the loop.
10:55. Because the system was explained so well I did not find this confusing at all. You're gonna be on the right loop as long as you pick the box with your number. The only question remaining is how long that loop is.
I finally understood WHY it still seems Impossible/Wrong even AFTER learning the answer to the riddle. And my god it's profound. Because when someone asks (After learning what the solution is) that "What makes you think you'd necessarily be on the correct loop?" and then you respond with the logic of it, The logic of it, [even though it's accurate and mathematically sound/proven] is "CIRCULAR"; so no wonder it seems false to us because circular logic usually IS false, Except when talking about the things that are circular in nature, like a freaking loop. Remember how in your video "Math's fundamental flaw" You explained how paradoxes arise from self reference? Well a loop, by definition Must reference itself. So because our brain will still want to reject it, we say "Yeah i know it's not random and you're opening the box with your number on it but what prevents you from ending up on the wrong loop?" And the response is "Because you're opening the box with your number on it". See the "Problem"? that was part of the question but that is apparently now the ANSWER ?!! Even your explanation in this very video can be summarized in "Because a loop is a loop, it must be a loop". It's kind of like learning God is real and asking him how do you exist?! and God telling you "Because I am God and i am infinitely intelligent and powerful i created myself into existence". The logic could be true but it still seems like WTF...!
Imagine being the prisoner trying to sell this plan: "Now we still have a 70% chance of failure, and it's much to difficult to explain, but you all need to follow my instructions exactly for us to have any chance." Then every dissenter lowers your chance by half agian. At this point, I'm starting to think this time would be better spent coordinating a riot.
I was very confused for a minute, until i realized you were trying to say "dissenter". Descent is going down, decent is not a verb, dissent is disagreeing.
Wow you're very smart with a great understanding of spelling and grammar. It's a shame those won't win you any friends or help you communicate effectively with those you manage to piss off.
@@BenjaminRonlund yep, the problem is definitely with making literally any corrections to anybody ever, not with the people who go "ur dum that's not a word". It's 100% not allowed to comment on spelling or grammar, even when it will help make the original post more clear to future readers and you fully explain what the correct word is and why it's correct. Explaining things never helped anybody, especially those learning an extremely difficult language like English, whether it be as a first language or a second.
The best thing about this loop strategy would be if someone finds their number in their last chance of opening a box, they make sure that they will be freed since if one 50 length loop exists, the others can be maximum 50 length
Friend! None of the other comments or the video itself allowed me to understand this. But your comment just did! Just visualized what you said and now I get it. Sincere thanks!
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.
Same, I knew that it had to be able to be related to some nice little expression. Now I’m trying to figure out how and if the “2” in 1 - ln(2) is related somehow to the ratio of choices per total boxes the prisoners are allowed to make
🎯 Key Takeaways for quick navigation: 00:00 *🧩 Introduction to the 100 Prisoners Riddle* - Introduction of a counterintuitive riddle that challenges perceptions, even after the solution is known. - Mention of widespread confusion and incorrect explanations on the topic. - Setup of the riddle involving 100 prisoners and a unique challenge they face. 02:02 *🤔 The Counterintuitive Solution* - Explanation of how a seemingly impossible probability can be significantly improved with the right strategy. - Introduction of the concept of mathematical strategy to solve the riddle. 03:11 *🔄 The Loop Strategy Explained* - Detailed explanation of the loop strategy for prisoners to increase their survival odds. - Illustration of how this strategy transforms theproblem and its solution. 05:44 *📊 Probability and Loops* - Analysis of how loops determine the success of the strategy. - Introduction to the calculation of success probability based on loop lengths. 09:46 *🤝 Impact of Strategy on Individual Probabilities* - Discussion on how the loop strategy affects individual and collective probabilities. - Clarification of misconceptions regarding loop participation and success rates. 12:43 *🛡️ Countermeasures and Adaptations* - Exploration of scenarios involving external interference with the strategy, and how prisoners can adapt. - Insight into the resilience of the strategy against manipulation. 14:15 *📈 Scaling the Problem* - Examination of the problem's scalability and the consistent success rate across different prisoner numbers. - Explanation of the mathematical limit of the strategy's success rate. 16:44 *💡 Learning from the Riddle* - Conclusion highlighting the educational value of the riddle and its implications. - Promotion of a platform for further learning and problem-solving skills development. Made with HARPA AI
I was confused when the guy asked how you know you're in the right loop because my mind never questioned that part. I was more fascinated by the graph, and how it worked that either everyone succeeded, or less than half did. After some thinking, that made sense to me too.
But in some ways, it's a sign of your good intuition that you didn't consider that: it's a blunder (in the sense that it just violates the conditions of the problem: if you go to box n_1, it directs you to box n_2, box n_2 directs you to box n_3, and box n_3 directs you back to box n_2, the slip reading n_2 has appeared twice). I think the video doesn't point this out as forcefully as it could (the ensuing explanation is pretty indirect).
The reason that either most people succeed or less than half is because if a loop of over 50 exists, that means at least 50 prisoners will be on that loop, and will all fail.
Hello i'm 14 years old and your videos are really interesting and cool !! rn i'm meant to be doing school hw :) i saw this riddle on another youtube video about 5 years ago and forgot about it but watching this video gave me a flood of memories of watching many riddle videos in my younger days I commented to say: I liked how at 8:48 you said "THIS IS A GENERAL RESULT" and then I had to use my brain (Drew) ^_^ Therefore the following graph with .31 and .69 was the only part of the video where I didn't immediately understand how we got there, which is not necessarily a bad thing? Also does 21142 on your prisoner costume have a hidden meaning??? To random strangers on the youtube: what should I study at Uni (atm I'm thinking medicine but what if I regret not doing maths or something else in the future) ik i have a long time to decide but i need to choose my a levels soon so do you have any good advice? Thank you for reading my comment
It's hard for anyone random to tell you what you should study. You should study what you want to do as a job, but it's hard to know what you'll want to do in 10 years. Had I known I wanted to do software engineering when I was 14 years old, I'd probably be a far better software engineer today than I actually am.
To me, the simplest way to explain the effect is… if a there is 1 that box is looked in 0 times, everyone fails. This method keeps that from happening. After the experiment, if you look at the boxes all the prisoners chose to look through, box 20 may have been looked in 5 times, box 21 was looked in 78 times, box 22 was looked at 61 times. The more a box is looked in, the more likely it is to be found by the right person, and the opposite is true. This method allows everybody to look at each box 50 times. Could also just take the prisoners ahead of time, line them all up, and number them 1 to 100. Tell them to open their number, and the following 50 numbers. So prisoner 6 opens 6 and 7 and 8, etc. Or you could tell them to open their number and add 2, so 6 and 8 and 10..
I agree. When Destin said "Teach me." I thought, "...and that's why I like him." Their honest amazement and fascination with learning make these two great teachers for the layman.
Really? I think Derek explained the solution in a really fantastic way, but he did not go into detail why those chances are calculated that way (that wasn't the point anyway... although I do think the title of the video is very clickbaity as usual and so who knows what was the point - more views?)... Anyway, maybe you should check the channels of Matt Parker (Stand-up Maths) and 3Blue1Brown
i made a smaller version of this riddle by decreasing the number of participants to 4 and i made artificial intelligence to randomly pick numbers for me with the loop strategy they succeeded 5 times out of 10 with random picking they didn't succeed in 10 trials. it was really fascinating.
Omg, it finally clicked for me!!! 😃 What it came down to for me was one very important realization: If you start with your own box number, you are GUARANTEED to always be on the loop that contains your slip! It's literally impossible for your slip to be inside any other loops. Let's say your number is 66, and you first open box #66. If slip 66 WASN'T in your box, then what was? Maybe slip 13? Okayyy.... Then what's in box #13?? It can't be slip 13 because that was in box #66, so let's go check... You open box #13 and it has slip 2 inside. Okayyyyyy, then what's in box #2?? Surely it's not 13, and it's not 2, because we already found those slips in the last two boxes... You can keep following the strategy, going box to box as the numbers on the slips lead you around, and every time you check a new box, there are only 2 outcomes: Either you find slip 66 which "completes the loop" and takes you back to box #66 (winning the game), or you find every single other number in the process, until you eventually get to the very last box to check, which WILL have slip 66 inside, because every box has a slip, there are only 100 boxes, and all 100 slips were used. No boxes are empty, and no boxes contain the same number as any other. While following the strategy, there is no possible way for you to reach a dead end, because every number you pull is a NEW number. You COULD get stuck in a loop, but the only way for that to happen is if you find a number which leads you back to the FIRST box you opened, which will be the number we're looking for, meaning you've won! You will never find a number leading you back to any other boxes you previously opened, because you've already located those slips that point to those boxes, they are in the trail "behind" you. Knowing that, now we're simply relying on the random chance that when the numbers were initially scrambled, no loops greater than size 50 were created. And as long as that's the case, it will be the same for all 100 players since the numbers were only scrambled once, and everyone will be able to locate their slip in 50 steps or less. Thanks to Derek already doing the math on this for us, we know there is roughly a 30% chance this will happen. On the contrary, 70% of the time that the game is set up, we will instead have a situation in which a loop greater than 50 will exist, meaning some players whose numbers fall inside that unforseen large loop will follow the strategy and eventually run out of picks before they can follow the loop all the way back to their number. Alas, I can sleep tonight 😊
Here's an analogy, which I think will be easier to comprehend: Imagine you have a class of 20 students. You ask each student to write their name on a piece of paper, then fold it up and toss it in a hat. You then have all 20 students randomly choose a paper from the hat and hold onto it (no peeking!). One at a time, you then give each student 10 guesses each to find their own name, which also includes the piece of paper in their own hands since they might've grabbed their own name by random chance. Taking this set up, what do you think would be the wisest strategy? If you ask Timmy to reveal his paper, he might have Tommy's name. If you then ask Tommy to reveal his paper, he could have Susan... Then if you ask Susan to reveal HER paper she could have Timmy, so now that loop is a dead end for poor Travis, who is just lost 3 of his guesses trying to find his own name. He could ask another random classmate, but that could end up with him getting stuck in another loop which doesn't contain his own name... Ie, he might ask Billy, who has his own name by chance. Or he might ask Chad, not knowing that Chad and Jeff have each other's names already.... So again, what's the best strategy?? Well how about Travis checks his OWN paper? Either it contains his own name, which makes him a winner, or it contains someone else's name, in which he can guarantee that person doesn't have THEIR OWN name. So Travis opens his own paper and see's Timmy's name. His best option is to now ask Timmy who's name he has, because Travis know's that Timmy must have either "Travis", or someone else in the class, but not "Timmy". Asking Timmy will always lead to Travis either finding his own name, or finding another potential guess from a new student, in which he knows that person wont already be holding their own name, nor any of the names of the students he has already asked. As he approaches his 10th guess, his odds become better and better at finding his own name. Now, he might run out of guesses before he finds his own name... BUT, as long as there are no chains (or "loops") of names which exceed 10 people before circling back around to the first, then every student in the class will be able to play the game and find their own name using this strategy, in 10 guesses or less. Derek's math tells us that roughly 30% of the time that the students randomly choose a name from the hat, we will have a winning circumstance where no "name chains" exceed 10 people in length.
You said: "a loop greater than 50 will exist, meaning some players whose numbers fall inside that unforseen large loop will follow the strategy and eventually run out of picks before they can follow the loop all the way back to their number." No. ALL of the prisoners on that loop will fail, not just some of them.
the rules are impossible by themselves. One of the rules say: "they must leave the room exactly as they found it". Once you enter the room, the room is not the same as it once was. Since prisoners are allowed to open and close the boxes to look for their number, the room can't be exactly as they found it. Which means, the own problem is a fraud. Another rule says: "If all 100 prisoners find their number "during" their turn in the room, they will all be freed, but if even one fails, they will all be executed." Its a paradox. Its impossible to 100 prisoners to find their number "during" their turn, since they are getting inside the room one after another.
@@athletico3548so with the first rule point you explained; you mean that if a prisoner knows the numbers, the math fails? But the prisoners arent allowed to share info with each other. It's still random for each individual. Also, idont really get the second point you made, can you elaborate?
@@athletico3548 how would you rephrase the rules then? Im having a hard time understanding, i do understand the chess lore and heraclitus' river, i dont understand the second point. Maybe its because my main language is not english, but i dont see it :( This is some qualia stuff right here
@@SublimeWeasel rephrasing it: "If each of the 100 prisoners find their number during their turn in the room, they will all be freed, but if even one fails, they will all be executed."
@@athletico3548this just seems like semantic nonsense. Also how does leaving the room exactly as they found it not make sense? Open and close boxes simple. They are closed as before. Seriously what are you trying to say
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.
So in order to get back to the initial box picked, with your number on it, you have to find the right slip. If you find the slip you are good. So your number HAS to be in the loop that also contains the box with your number. Hence, if the longest chain is 50 or less, everyone will find their number. Damn it actually makes sense now
@Any Body The way the riddle is set up this shouldn't be possible. If each slip exists only once, box 23 can't have slip 54, because that slip was already in box 7.
10:32 regarding Dustin's comment, to get onto a self-closed loop from outside the loop would require the same number appearing twice (say the loop you're going into is ab...ca, and you go from d to a, then c and d contain a).
I was in shock when he flipped the whiteboard over again at 8:17. The contents were no longer the same as what he wrote earlier on that side of the board. And then I remembered that cutting is a thing. When done right, you don't notice them. Props to the editor!
Demonstrating, yet again, just how elegant and, frankly, satisfying mathematics can be. What got me through applied mathematics in college was the idea that there may be 100 different ways to get to a solution, but there's only one specific solution. Now, the solution may involve a set of solutions (a la differential equations), but if you're a fan of mathematics, you'll know what I mean. Enjoyed this one, Derek. Great work, as always.
I was surprised by the "what if you're on the wrong loop" question, because that part seemed the most intuitive to me. The part I struggled with was how the likelihood of everyone winning was ~30%. The math to reach that number makes sense, but the result still seems really unintuitive to me.
It’s easier if you don’t think about the prisoners at all, just loops. If there is no loop > 50, every prisoner makes it. And there’s a lot more ways to make small loops than big loops, so any given random loop is more likely to be small than large
I felt the exact same way. The probability works out from graph theory and combinatorics though. You have to sum the number of ways you can make unique loops (cycles) of greater than half the number of boxes and divide by full number of permutations of the boxes
I asked about this. You could (maybe - not sure) derive it from normal distribution.. all the loops are random so it follows a random distrib meaning 68% of the time the loops will be in the 1 standard deviation but as the group needs to be right (100% of the prisoners need to find the right number) they will be right only 31% of the time (100% of them) and 68% of the time they will be in the 1 standard dev.. (meaning a part of them will lose so all of them lose)
2:45 Basically pick a random box,if the box says a number thats not yours,count the boxes till to that number u go and open it, example: u have number 6, if u opened the 5th box out of 10 boxes and the fifth box shows the number 2,go to the 2nd box and open it,if shows 8 then go to 8th,repeat all that process untill u get ur number,even luckier if u got ur number less than 50.
@J Boss Well in the case of the prisoners, the warden will notice the box swapping And probably execute them all In the case of the sympathetic prison guard, the warden probably thinks "oh they're just checking the boxes"
@J Boss I think the issue is that the sympathetic officer needs to intentionally know about the >50 loop and needs to swap 2 boxes that render both halves of the loop to be less than 50 (versus just swapping 2 boxes randomly). I don't know the math to solve it but, logically, if Derek were to swap boxes 78 and 57 he would've made an even longer loop (combining the small loop to the right). Or, if he were to swap boxes 80 and 42 (or any 2 boxes that are close together on the loop) then he would create a loop of 3 but potentially leave a loop greater than 50.
Since, like the monty hall problem, this benefits from other ways of explaining, here's another way to think about how every box must form a closed loop: for it to NOT form a closed loop, it'd have to be something like 1 -> 2 -> 3 -> 4 -> 2, where 1 never gets repeated and instead leads to a smaller loop. this, however, indicates 2 slips that point to 2, which isn't possible, since it means no slips point to 1.
@@hishaam5429 There are 100 unique numbers and 100 unique boxes so having 2 numbers that are the same is a contradiction Thus there cannot be 2 boxes pointing to 2 Which further implies that there must be one box pointing to the number 1
@@hishaam5429 you could have a loop with 99 slips that don't point to 1, but then box 1 would have to contain a slip that pointed to box 1 -- a loop of size one.
I feel like the really cruel thing to do would be to allow the prisoners to look at 95-97 boxes, with the same thing. If they figure out the stragegy, it's like a >95% chance of success. If they guess randomly, it's
exactly! try to convince your inmates now! the indivudual 97% seem so much more intuitive than trying to grasp even only that you'll always be on your own loop.. :D for nerds who want to avoid using their calculator: (97/100)^100 = 4.75525% (rounded since there was a 0 after the last digit)
if they opened them randomly at 95 choices each, that would give them a 0.592% chance. similarly, you could do this with 4 boxes and 10 friends. let them open up 3 boxes each to try to find something in one of the boxes. If the goal is to win if every one finds what was in the box, then they would have about the same odds.
Miltersen: "Hey, i made this riddle. Anyone want to try it?" Everyone: "Dang, it is kinda difficult. What is the answer?" Miltersen: "Idk go figure it out"
That's what I love about Destin. He is always so humble and willing to learn from other people. He would be a good dude to hang out with, I feel. Btw, "humility" is the form of the word you were looking for.
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.
@@mikebarrientos5085 No, because you can look through the whole thing. Essentially, the 31% chance is if there is a cycle greater than half of the total number of pieces, and that is not important in the rubik's case, because there is no constraint about only looking at half the pieces.
@ 10:44 - As far as the question of not coming back to your own number: One short answer is - remember that YOU (and the prisoners' group) are the one defining these "loops." Hence, by having faith in these loop definitions, you can be *certain* that, given enough chances (as an individual prisoner), you will ALWAYS find your number. The PROBLEM is, that, 69% of the time, *one* of the loops will be 51 numbers long - or longer. So, 69% of the time, because of the unfortunate "luck of the draw," the 100 prisoners are going to die, for certain. They will discover this fate with the first prisoner's number to fall on the "51+ length" loop, as he will use up all of his 50 chances before finding his number. However, the positive flip-side, as seen on the (Z-factor?) diagram above, is that 31% of the time, ALL of the "prisoner-defined" loops are 50 numbers long, or *less.* This guarantees that, following the "prisoner-defined" loop definition system, and loops defined therein, EVERY SINGLE PRISONER will be *guaranteed* to find his number 100% of the time - in 50 chances or fewer. This is what thus also guarantees that, as a group, the prisoners will certainly succeed, 100% OF that 31% of the time! And compared to (1/2)^100, the standard odds of such a thing happening at random, that's really quite an amazing improvement! 😉👍
In thinking about the looping, I had to realize that the loop couldn't end early by the slip refering to its own box or one already visited because you reached them with the single refering slip (but you can start with the lucky loop of one by finding the right slip in the first box you open). This seems crucial to why the probability is so counter-intuitive. The set-up is highly non-random, low entropy, high information in that there is only one slip for each number, and this solution takes maximal advantage of that. Because of the single slip principle, each one is in a loop, and you can't get on the wrong loop if you start by choosing the number you are seeking. Each time you jump to a new number, that is the only way you can get there, and you will always be sent to another new, not previously reached number from that point.
Right. If you start with Box 2 and get Slip 1, you move to Box 1, but there's no way you'll find Slip 1 in there because you already (just) found it. The shortest loop you could get at that point is a length of 2 by finding Slip 2, etc, etc.
The bit I don't get is how adding numbers to boxes or slips somehow ensures you can find your own slip. Yes it kicks you onto a different loop strategy. But it doesn't explain how you ensure you find your targeted loop as opposed to ending up on someone else's loop. After all the reason the loop strategy works is because of the fact there are no branching paths on your loop as it is unique and contains your own number. If you mess with the starting loop pattern yes you find a new unique loop. But your number could Very well be on some other loop. Unless somehow slip +5 strat is somehow guaranteed to find your box +5 as opposed to your original box. I would expect it just left you on another person's loop. Of course the correct way to ensure failure is to make all prisoners remove their slip from the containing box upon finding it. Even a loop of size two will break as soon as the first prisoner finds his slip as the second prisoner will be offered no clues about how to find his own slip.
@@glenmcgillivray4707 how could you end up on someone else's loop if the core gameplay is still here? You re-numbered all boxex but there're still hundred of them, from 1 to 100. And you still can't get the number you've already found (because you've already found it, there're no twins). You just can't create a loop where there IS box with your number ON it but WITHOUT box with your number INSIDE it. It is impossible unles there's two boxes with the same number or smth like that. Basically, you can randomly mix box numbers without breaking the rule. The only reason why all of them have to add one specific number, because they can't mix boxes physically and have to be sure they won't make a mistake mixing numbers in their mind. Re-numbering boxes adding any constant number is solid way to do that. I'm not sure why this break the loop created by guard, tho, can't imagine it or do math... But sounds right, I just need to draw this to see, the picture in video were too small for me.
@@inter_acies they were saying that should your warden cheat by making loops longer than 50. Say intentionally making it go to 100. You can shift the box numbers to create an entirely new sequence of loops. This i believe. What I struggle with is how to ensure your number is within the specific loop you create in this manner. If you open your box +5 and it contains itself. You aren't free. So what's the trick here. How do we mess with the loop of say 99 and 1 to find your reordered loop.
Here’s how I thought about the must be on a loop issue, and it might help others. When you look into your numbered box you have started a path which must end. the only way the path ends is by reaching a box you have already opened. This can happen in two ways, you find a box with the starting number or you find a number which points you back to a number you were previously on which would mean you found a number twice in your path, but finding a number twice is not possible as each number only appears once. The only way your path ends is by completing the loop and finding the box with your starting number.
This is the key: You can't enter a loop from outside the loop. It's impossible to have "tails" attached to a loop because it would mean two separate labels point to one box. (it would also imply there is a box with nothing pointing to it.) This isn't allowed per the rules of the game.
Why is that any different than stating at box 1 and ending at box 50? I’m slow cause I’m not understanding the difference. Why is moving around to boxes based on the number in a box any more special…. Now I realize it must be because all the smart people get it, but I just can’t make sense of it…opening a box and reading a number inside, then going to that box seems just as random..
@@ediartiva By the rules of the game you're not allowed to keep looking after 50 boxes, but if you ignore the rule and keep on then you will ALWAYS eventually find your number, in the worst case it would be in the very last box that's not opened. If there are no duplicates and no empty boxes there's no way you end the loop without finding your own number.
I love the tools used for demonstration, either if they were shown on screen as a graph, its coloring, or actual objects. It helps so much to figure out whats going on
STEINER VOICE: When you don't use this strategy your odds drastic go down. This is a great video! Very interesting and incredibly well editted
2 ปีที่แล้ว +229
The puzzle is even more interesting if it's modified to say that the first prisoner is allowed to check all boxes and make one swap. Then telling that there exists a strategy which guarantees success sounds even more incredible.
I love it Still we most hope that the prisoner in question swaps the longer loop instead of a smaller one
2 ปีที่แล้ว +13
@@markmuller7962 prisoner only needs to check 50 boxes to guarantee they can always swap in a way that ensures no chain is longer than 50 after the swap. The only reason the first prisoner needs to be allowed to check all boxes is so that they themselves are guaranteed to find their own number. The puzzle can also state that all prisoners can check only 50 boxes, but the first one can do a swap, while the rest must find their number.
@ I know how the riddle and the riddle solution works. Thing is, if the first prisoner swaps a loop of 4 boxes he only creates 2 loops of 2 boxes while the eventual 50+ loop stays intact and it's gonna kill the prisoners. The benevolent guard in the video either knows all the numbers inside the boxes or gets "lucky" by swapping the cards of the longest loop
the question at 10:40 is explained by that a prisoner will always start from the box of his own number assuming that the last slip of the loop will be his numbered slip as explained at 5:17 , so it is a 100% chance that the prisoner numbered slip exists in the loop, but only a 31% chance that the loop is smaller than 51. I think this is the simple explanation to this question.
Thank you so much i had a hard time digesting that one. I initially thought that the explanation only justifies the existence of the loops, but does not ensure the prisoner to be in the 'correct loop'.
If the loop has all the numbers, Why do you care that the last number is yours or not? Your number can be inside the loop. if you randomly choose any box at the beginning the probabilities of finding your number are the same as if you choose to start with your number box.
I still dont understand why you have to find your number in the loop you pick? You have 31% to have largest loop at 50. You still have to choose the RIGHT LOOP.
@@minhtrinh3646 I am convinced that this is incorrect, because it assumes that the boxes will be ordered in a "loop", so in reality it is pre-ordered, that is, it is not random. That 30% chance is only possible if someone previously ordered the boxes as a "loop". In a real case where the numbers are ordered randomly, this strategy is useless.
Ironically, this also changes what the prisoners want to see when they're looking for their number. If you're picking randomly, you want to find your number as quickly as possible. But after coming up with this strategy, you want to see chains that are decently long, but still under 51. You don't actually want to see short chains. It's good for you, personally if your number is in a short chain, but the more short chains there are, the higher the probability that one of the other, longer chains is gonna be above 51 numbers. Since it doesn't really matter how fast you find your number since all prisoners either fail or succeed together, what you want to see is a long chain, because every other prisoner in your chain is also GUARANTEED to find their number with the same strategy. In fact, taken to its logical extreme, although the individual prisoner would probably be stressed if they're on box 49 and still haven't found their number, if they hit box 50 and find their number, they can celebrate right then and there, because a chain of 50 is a guaranteed win, because none of the other chains can be more than 50 in a set of 100.
@@mediagirl There's no way to start on the wrong loop, since they're picking the loop that contains their number by default. They're picking the box with their number on it, meaning the loop will always end with their number, since that's where it loops back around. The only factor is then whether or not their loop is less than 51 numbers long, because they can only open 50 boxes. If one loop is 50, then no other loop can be 51 or higher, meaning every prisoner is going to pick their loop, and they will always be able to complete their loop, since none are more than 51.
You all need to watch the video again. You are ALWAYS, 100% of the time, going to pick your own number's loop if you start on the box with your number on it, because that's what makes it a loop. You literally cannot start on the wrong loop if you pick your own number, since picking your number MEANS starting on your own loop. The only question then is "if I'm only allowed to open 50 boxes, is my number's loop less than or equal to 50 boxes?". If you find a loop of 50, you know it is, and you know everyone else's is too, because you can't have a loop of 50, and then a loop of 51 or more, if there are only 100 boxes.
5:55 As a mathematician and who loves ridles, until this point everything makes sense, And i had kinda same idea when i saw first at this videos this ridle but i didnt make calculations like this. But this makes sense, I havent watched till the end but i have one big math idea. So if u are in a loop of 10 numbers it means all of them are safe like u, and the biggest save will be if u find the loop of 49 numbers, that makes the chances impossible to fail everyone, bcz each the bigger loop smaller than 50 guarantees that other loops may be smaller. The biggest loop X, where X < =49 is the best loop in this riddle.
I also had the question "what if you're on the wrong loop" My reasoning is the last box in the loop must contain the same number as the first opened box due to the definition of the loop. Otherwise, if the "last box" contains a different numbered slip, it just means that it is not the last box, and the loop is longer. So there are 2 possible outcomes after opening a box: a) it contains the prisoner's number and the loop is completed or b) it does not contain the prisoners number and they must repeat the steps for the next box until the loop is closed. And the loop has to close because there are a finite 100 boxes. If there is a single loop of 100 boxes each with a unique slip, after 99 boxes/slips, the 100th slip is guaranteed to have the number of the first box. It was nice to revisit this riddle!
@@voidmayonnaise If the random arrangment has no more than 50 loops (31% chance by the video) then first prisoners has 100% chance to get it right. I disagree with Veritasium saying it's 50%. The probably already determined when the loop is set with this trick
exactly what @KahaiMitram said, if you're not on the right loop, it's not a loop. And, by the definition of the all unique numbers being "renumbered", it has to be a loop. The only question is, is the loop shorter than or equal to 50. (edit) the above is still valid, but nm to anything after that. My sleep addled brain did the math wrong. The unique permutation of a loop is (n-1)!, which is the same as n!/n, which, if n=100, is 100!/100.
The easiest way for me to understand this strategy is that when choosing boxes randomly, the prisoners as a group need to be lucky 100 times to win their freedom (each person basically come in with only 50/50 chances) While with the loop strategy, the prisoners as a group only need to be lucky ONCE. That is because if the boxes arrangement doesn't produce a loop longer than 50, then they're all GUARANTEED to win. Therefore they only need to be lucky when the boxes were shuffled, and the probability of the arrangement they need come out of the shuffle is about 31%.
The interesting thing is that if you drop the number of prisoners to 2, the probability goes to 50% if you use this strategy, as opposed to 25% by choosing randomly. If both prisoners agree to pick either their own or the other's box, then both ensure that they don't accidentally pick the same box, meaning that if the correct number is in the box they chose, they both find it, while if the wrong number is in the box, neither of them finds it.
Where are you getting this 50/50 business. Remember the chances randomly had 31 zeros to the right of the decimal. That's stretching the definition of the word lucky a bit far.
@@mperhaps It's because only having 2 prioners is a completely different scenario than having 100. Doing the strategy will remove the 2 possible ways the 2 prioners can chose their 1 box that we know will always fail, i.e. both opening 1 or both opening 2. Out of the two remaining, alternatives, there is a 50% chance since either both pick the correct box (1->1, 2->2) or both pick the wrong one (1->2, 2->1).
> Therefore they only need to be lucky when the boxes were shuffled Not exactly. Prisoners can be the masters of own destiny, by adding an arbitrary number to every box, and therefore create a new shuffe. 12:56
The reason I love Destin so much is because of his mindset at 2:27 - Instead of being boggled and/or arguing, hes completely open to just learning the facts of what was just told to him with his simple 'Teach me' - many people could learn from Destins attitude in today's day and age; probably one of the main reasons hes in my top 3 of favorite youtube channels!
I understand they're friends and Veritasium is trying to throw Destin some viewers but I wonder if they ever flip the script. Where Destin is trying to solve one of his own puzzles and calls Veritasium so that he's the one saying "Ya I don't know the answer."
The first time a friend told me this, my reaction was _"No, I don't believe you. You're obviously wrong. It's impossible that it's over 30%. That's ridiculous. You've made a mistake."_ A few minutes later and I'm eating my words.
![CAMPปลิ้น | รวม Highlight 2024! PART [1/2]](http://i.ytimg.com/vi/6hnvNnvYloU/mqdefault.jpg)
Something seems wrong at 9:00
What is the probability of a loop of length 1? (Can't be 1/1)
Length 2?
That calculation applies only for n>50.
Yes it is 1/1 but you have to treat it as an expected value. On average in any arrangement of 100 slips in boxes you should expect one loop of length 1. But sometimes you won’t get one. Sometimes you’ll get two or three etc.
So if you had 1000 random arrangements of 100 numbers, you’d expect to find
1000 loops of length 1
500 loops of length 2
333 loops of length 3
etc.
10 loops of length 100
In the graph we show something slightly different, the probability that a loop of length L is the longest loop. If L>50 it must be the longest loop so the probability it exists and the probability it’s the longest are the same. If L
@@veritasium Agreed
@@veritasium I think one should applies a variation of the fixed point theorem here. i.e., a function mapping a domain to itself has a fixed point.
@@gc852 Only applies to continuous functions.
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.)
Best comment, 10/10
lmaooo what an amazingly real-life example of this!
unfortunately... CDs are no longer common enough for most people under a certain age to really get this example :(
To be fair, it should work 100% time if you don't have a warden forcing you to only open half.
Omg I forgot about that. Lol I swear we all did this for CDs, DVDs, video games. The loop has been right in front of us all along :)
@@NZsaltz Wait? You _don’t_ have somebody execute you if you open more than half of your CD cases?
Memorizing this just in case I'm ever trapped in a prison with a sadistic mathematical prison warden
Well - are you Korean? ;)
@@spyro440 you win. 🤣🤣🤣🤣
Lmaooooooo
The only way you're coming out alive foso is you're the only participate , otherwise you're fucked 😂
Thanks for the suggestion. Also, bring canned fool.
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.
Underrated comment
Yeah
You need a nerd with charisma.
Hmmmm!!!?!
Where theoretical maths meet the "real world" and provide the opportunity to show that the human species' success is tied to cooperation within the species as well as groups within that species...like family units.
When we cooperate as a family to follow known solutions to problems we have a 1/3 chance of succeeding. Where as groups who refuse to cooperate towards a goal have an almost zero chance of success!!
That shows your bias. Thanks to TH-cam, Derek and Brilliant, we're heading towards a bright future were all prisoners are going to be nerds. Wait...
The main point here is that "failing hard" comes with no harsher penalty than "failing little"....hence, you can redistribute your loss function to take advantage of this. Great video, btw!
I think the chance of convincing 99 other prisoners that this strategy is their best chance of survival is much lower than 31%.
@@pokejinwwi one? Out of 100? That's even more impossible.
We're talking inmates here,
Some guy will want to go on his lucky number and a lot of other dumb stuff would happen
at least 7 of them will pray to jesus for the which boxes to open
One will try to escape and get everyone killed.
@@tvao9010 the play there is to add (lucky number - inmate number) to all boxes and proceed as usual : )
Imagine being the first inmate and not finding your number. “Oof, we tried”
or the last!
@@Andy-lm2zp if you were the last one and you failed, then there should've been MANY others also failing.
@@funnygreenguy only when you follow the strategy mentioned in the video...
@@ramuroy6088 yeah, I automatically assumed it from the original comment 😀
I like to think that the people constructing the test purposely made no loops of >50, so that the prisoners could go free if they are intelligent enough to be worth returning to society (if they figure out the loop method then they will be given 100% chance)
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.
Really?
@@Ryuseigan Yes, because then the other 49 on that loop will obviously also succeed, and anyone else is on a loop of *at most* 50 (two loops of 50 is all there is), and thus will also succeed.
Because then there would be no other loops that can be greater than 50. Any other loops guaranteed to be lower than 50 so its guaranteed win.
@@Ryuseigan yes really. The largest loop size of the remaining boxes cannot exceed 50, because 50 has already been used in that first loop prisoner #1 found.
@@Ryuseigan Yes, because there cant be same box on different loops. So a loop of 50 boxes would imply that remaining boxes at max can be 50 so no loop goes above 50 in size, hence 100% success
I needed this. I woke up this morning not feeling sufficiently stupid. Problem solved.
😂
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.
Your observation is not necessarily true. It could just be that Derek randomly picked 5 odd numbers, and this has a probability of 2.8%
They are called *odd* for a reason
Raoodnm
@@jynx619 how did you calculate that probability
@@josenobi3022 I'd do 1/2⁵ but that's 3.1% 😕
As a former professional gambler, the key to understanding this in real-world terms is at 9:48. Every prisoner's individual chance of success is still 50%. The strategy works by making the prisoners' individual chances contingent on each other: linking them together.
Imagine a related puzzle - the sadistic warden has been told that the median human heart rate is 75 beats per minute.
He devises a game where he measures the 100 prisoners' heart rates. He has two large bins marked "UNDER 75 BPM" and "75 OR OVER", and he places each prisoner's ID tag in the bin corresponding to their measured heart rate. But there are two catches. Firstly, he has privately flipped a coin before the game to decide which will be the winning bin: the prisoners don't know which is which.
And secondly, *all 100* prisoners have to win the game for them to be freed.
So each prisoner's chance of winning is 50%. And with no collective strategy, the chance of everyone winning is 0.5 to the power 100. Tiny.
But the collective strategy is simple: everyone does extremely vigorous exercise immediately before getting tested.
Now *everyone's* heart rate is above the median. So although each person's individual chance of winning the game is still 50%, now the collective chance of winning is also 50% - because *everyone is now in the same bin.*
Basically, that's how to grok the video's strategy for the boxes problem - in a sense it puts everyone "in the same bin" - and the bin is marked *"Are all the loops shorter than 51 ?".*
Notice that the Skyum "loops" strategy works because the room *is the same room for everyone.* And the strategy takes advantage of a particular mathematical property of the way the numbers are sorted into boxes *in that one particular room.*
If there were 100 *different* rooms, with the numbers in the 100 boxes sorted randomly in each one, then the chances of *everyone* succeeding would again be huge. Because now all of the 100 outcomes would be statistically independent.
Ok, that was an AWESOME example! Mind = blown 🤯🤯
Absolutely stunning example.
Did you retire early and because of success in that? One of my brothers learned a roulette betting strategy, something about (a) betting on 1/3 of the numbers each time and (b) setting a predetermined loss limit at which you'll stop betting. You win more often than lose, but do lose. He was kicked out of casinos for using it, even though it breaks no rules.
I've been tempted for years to try such things but have always resorted to status quo of work a job for a paycheck....
I appreciate this version of the explanation to point out where the "magic number" comes from by reminding us that the criteria for "the bin" is arbitrary
really sad that these prisoners were so good at math and cooperation, yet still ended up in jail 😢
White collar criminals no doubt.
Lmao laughed too hard at this
May be all are in for stock market manipulation
They're all just people who went to jail for maximum time for possession of weed in the US and one of them happens to be a math professor who explains how it works to the other 99.
(This is literally a thing that occurs in the US and especially among black and latino communities because racism! I'm being sarcastic, but this is true. You're less likely to end up in prison for possession alone if you're white and I hate that that's true still.)
Political dissidents: First time being genocided? :Ü™
I've seen a variation of this some years ago. Didn't remember the way to solve but it came back quickly when you gave the solution.
The way I like to think about the solution: you're no longer betting that each individual prisoner will find their number with a pattern that they choose (arbitrary or intentional), but you're betting on the probability that a pattern (a loop exceeding a length of 50) does not exist in the set of boxes. And that's a static property of the set you're betting on, in contrast to rolling the dice every time on 50 different prisoners. So, in a way, you've already succeeded or failed by choosing the loop strategy, whether you know it or not. Random chance no longer has anything to do with the prisoners' choices (unless they mess up the execution of the loop strategy), but entirely on how the box set is arranged and the loop strategy that the prisoners decide to employ at the start.
Fascinating mathematics! Thanks for sharing this!
Yeah exactly. For a video that set out to make a complicated thing understandable, there is room for considerable improvement...
51 would be set of three boxes. : 5.0999011. Or 352319696. You can’t jump 51
With the implementation of the strategy you change an element of randomness in the problem. The randomness of the prisoners behaviour.
Just like a conductor changes noise into order with the swing of a wooden stick based on mutual understanding of the symbolism of the stick.
The power of cooperation, hence the saying a bad plan is better than no plan.
@@sonkeschmidt2027
I mean with this one, it's so much about the magnitude of difference if you notice this behind the hood pattern of loops.
You could also create a very bad plan where everyone cooperates, like maybe prisoners might think that each should go
1. 1 - 50.
2. 2 - 51.
3. 3 - 52.
...
50. 50-99.
51. 51-100.
52. 52-1.
100. 100-49.
thinking this is better than completely random. This is for example the first idea I thought to test if it would have any influence at all, what if they increase number one by one. I'm not sure if this actually will increase odds in any meaningful way. Didn't actually test it out, but I knew it definitely won't give near 1/3 odds.
So I would say it's more about noticing this really obscure but effective strategy rather than cooperation really. You of course need cooperation to carry it out.
@@enzzz what is this obscure strategy going to do without cooperation? How you going to implement it? Or even find it out?
You would need someone to come up with it and convince everyone to follow a strategy with just 30% chance of winning. That is not a good plan. It might be the best but it's not a good one. To get this to happen requires a shitton of cooperation.
My actual concern if this ever somehow became a situation I got myself into is that someone would decide this is stupid and just pick boxes at random
_"that someone would decide this is stupid and just pick boxes at random"_
That's frequently a problem in real life. Not so much in the fabricated setup of the video. Persons with a strong determination are usually the ones which make the decisions, and not always they are very smart. Like this example from recent (and many others from less recent) history:
Smart mind says: "Don't go to war against xxx, IT WILL NOT WORK." Strong will says: "Of course it will, you're a coward and a traitor."
20 years later, it did not work. Strong will says: "Nobody could have known that, therefore it was the right decision at that time."
Exactly. Every idiot deciding to go for random nubers roughly halves the chance of winning.
Anyway, here is some useless math I spent half an hour on (what am I doing with my life?).
Theoretically even with googol or googolplex people (assuming that we just don't worry abut time it would take to open half a googolplex boxes gogolpex times) you would have an over 30% chance of winnig, but when talking abut actual people, not idealized beings, this just doesn't work. Even with the googol people case and (10^-48)%, wich is 0.000000000000000000000000000000000000000000000001% people being idiots and choosing randomly, your chance would be(3/2^(10^50))%, wich i think is way under 1/10^10000, or 1/googol^100. When I plugged this into calculators (even the most precise ones I could find), they straight out gave me 0, witch speaks for itself.
If that happened in real life to you u would have a better chance just starting a jailbreak
A legit concern.
If one person did it, it would just reduce the odds of sucess by 50%, 15% still isnt bad
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
Just by the title I thought Parkers video of the same puzzle.😀
It's just maths, it's either right or wrong, it can't be controversial.
Yeah same makes perfect sense to me
I'm disappointed, honestly. I was looking forward to more angry ElectroBOOM response videos.
@@ELYESSS
Erm. Have you heard of the -1/12th video?
Mentally filing this away next to "the mitochondria is the powerhouse of the cell."
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.
I actually had this happen to me in a Turkish prison. I came up with it on the spot and saved us all.
@Michael Ritsema sure dude. Whatever.
@@aaron2112 He save hundreds of us! I owe my life to michael for his solution!
@@aaron2112 it's true, I was one of the inmates and Michael is a true genius
@@aaron2112 Michael saved my life in that Turkish prison, he isn't lying
8:25 - That flip to unexpectedly new stuff on the whiteboard was so smooth. Nice job.
Hah! I was thinking the same thing!
If you think the riddle is hard, imagine trying to convince 99 fellow prisoners to follow the plan to the letter.
No letters, just numbers, ha ha.
@senni bgon you've clearly never been in prison. Or met someone with ADHD.
xd
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.
@@christiankrause1594 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.
2:41 My strategy is that a prisoner picks a box and the number inside is the next box you should open. Example : 26 = 74, 74 = 36, 36 = 92, 92 = 11 and so on...
Don't forget to start with your own number, otherwise this will fail.
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.
I was thinking the same thing, his explanation with the link at 11:25 wasn't very helpful. He should have instead hammered on the point that you could never fail to find your number, you will never have to try again and find a different loop. When Dustin said "I feel like it's possible that you start with the loop but don't end up finding your number", Derek should have said "And what would that look like?" at which point you realise pretty quickly that it's impossible, and thus loop length is the only factor that determines your succes.
Perhaps Derek could also have spent a little more time analysing the situation before starting his explanation. If the viewers felt like they discovered the properties of the loops themselves it would feel much more intuitive.
Edit: if you still feel like this is unintuitive, like this is cheating math somehow, that this shouldn't be possible, consider the following: there is only one 'check' to see if the experiment is a succes or a fail, it's right at the beginning, if the starting configuration has a loop of 51 or higher. Imagine if the box configuration was rondomised for each individual prisoner, then the chance of all 100 of them passing would be astronomically low again, and all is right in the world.
@@irakyl Derek should've said "Then how would you manage to loop back to the box you started at?" Assuming we all agree beforehand that these are closed loops, I think that's the easiest argument for why you must be in the correct loop.
@@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!
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
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
you've got to admire these mathematicians for thinking out of the box
literally this time
I see what you did there!
But why where they in jail to begin with 😂
Or out of the loop!
@@abinbaby4044 actually, into the loop xD
Destin had my favorite response ever, "teach me!" I love that.
Love this! The concept of loops does break the mind slightly, but is very logical once you look at it with a reduced number of boxes. I would never come up with this solution myself, however - eliminating randomness of prisoners' choices in this manner is truly ingenious.
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.
* Tips Hat*
"Skyum's protocol" sounds a bit like a namecheck...
I live in Aarhus!
@@ApequH tips fedora m'skyum
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.
A really incredible feature of the loop strategy is comparing how well it works even against random guessing with more chances to open boxes. For example, if each prisoner were allowed to open 99 of the 100 boxes, instead of 50, to find their own number, the total probability of success by randomly guessing is only 0.99^100, or 36.6%! (Whereas the loop strategy gives a comparable chance of success while only opening 50 boxes, and succeeds 99% of the time if you can open 99 boxes) If you were allowed to open 98 of 100 boxes, the chance of winning via random guessing drops to 13.3%, and to below 5% for 97 boxes!
If this is true thats absolutely awesome. Missed chance to point that out in this video
Maybe
if you open 99 of the 100 boxes, then by elimination you can guarantee which box your number is in
@@RockyRoad213well yeah but if you don't actually open it you lose
What if the evil warden gave an empty box
I think the key to understanding why you are always in the loop that contains your number is that the slips are all unique. The only number that can complete the loop is your own because that's the only slip that can point back to another box you have already opened. If you open box 3 and find a 5 and then open box 5 to find a 7 you can't open box 7 and find another 5. It will either by 3 to complete the loop or a number you haven't seen already.
I think this might be a better explanation than the video
I think the key to understand is "there are only loops". And loops always go back to your start.
---
My first thoughts viewing his proof are:
Then why there are always only loops?
=> Or in other words why only loops can fullfill the requirement for a set of 1 to 1 pair to be all contained?
=> OR why the 1to1 and one-direction basic structure can only form a line or a loop?
oh, this can be easily proven with induction.
---
So we have the basic: there can be only lines and loops.
---
why there are only loops is because the structure can only form lines and loops. Since lines has slip outside of box which is invalid in our scenario, there can only be loops.
For me, it was simpler to consider that the box and the number must be part of the same loop regardless of its length. Any box must be part of a loop that points to itself since all numbers are unique and are just a permutation, the worst case is just having to go through all the boxes. So if you start with the box with your number you know it is part of the correct loop.
For me, I just tried to break the strategy. How? By imagining that I didn't find my number for the first 99 boxes. That final box MUST complete the loop, there's no possible alternative and that's the WORST case. Every other combination (loop) containing fewer boxes will terminate faster at my number because that's the terminating condition.
Actually, it is because of the definition of the loop, all boxes and corresponding numbers must be part of the same loop. Since the number in the box gives you the box that gives the next number and so on and the loop can only end with the original box and the loop has to end.
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.
Your "intuition" definitely leads you down the wrong path in probabilities at least 76% of the time. The human brain is just not wired to deal with probabilities intuitively (and also 95% of statistics are completely made up)
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.
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
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's a small thing but I find Destin's response to your claim (5 seconds of deep thought followed by "teach me") is inspirational. He switched gears so fast from peer to student, it's the kind of attitude I want and he makes it look so simple.
I actually think 5 second of thought is still too short
The best teachers never stop being students.
Instead of having separate peer/student relationships, perceive every relationship as potential for learning, we can learn from young children, learn from old wisdom, learn from other perspectives, learn from animals, which is why Destin's reaction appears so simple, because he is always seeking to learn, it's not being in a learning mode, it's just a constant way of living/learning. This will sound trite, but instead of being inspired by it/want to do it, instead just do it, seek out what you might learn from any interaction, there's always something!
Dudes so honest and genuine. I strive to be like him
A true master is an eternal student.
I like this warden. He has reasoned out that if he can turn all his prisoners into math wizards or at least willing to work together and trust one another, he can let them out.
Then you get something like Vento Aureo. Basically a group of criminal with a prodigy and are willing to work together
The wardens watching too much saw and squid game
The missing part of the strategy is, if the first prisoner fails, they implement plan B and break out.
@Tee Emm
And now probability has been in creased to 100% cus there’s like 1 warden
After watching 3 times and then doing something else entirely, I finally understand the logic. The heart of this problem is in the sentence that begins at 5:30 minutes. Listen carefully to the few seconds before that and follow the logic for WHY all other prisoners in that loop will fail to find their number. That is what I originally missed. In this case, I chose several prisoners in this loop and convinced myself that, indeed, ALL prisoners in that loop fail to find their number, missing it by 1 box. Their number is in the 51st box that prisoner would have opened. I need to try a similar exercise for the nice guard to breaks the loop into two loops by switching just the contents of two boxes, but I think my brain is strained enough for one day. Hope this is helpful for others. It was a revelation to me. Thanks to the poster of this video!
This type of content is unbelievable! As an AP Calc and AP Stats teacher, it keeps me motivated to learn more and find more interesting problems for my students to keep them motivated.
@@ibrahim-sj2cr I dont think in this situation you are supposed to go to box 6. You stil go to your box 1, it is just some other box than before. I have not thought this through, but just from the top of my head, I dont see any issues with this.
@@nejnovejsii yes you are correct...had to get the pen and paper out on his one
@@nejnovejsi all the numbers were changed, that was what i didnt realise
@@nejnovejsi and thanks
I work in irrigation and we actually use closed loops like this! If I have zones numbered from 1-10 (for houses 1-10) but the stations do not follow the order of the houses, we just pick the first wire and move it to the correct order (for example: station 5 is house 1; put station 5 wire into station 1 slot, and station 1 into the next assigned order; repeat until finished). I’ve had 2-3 closed loops and always thought it was fascinating, really neat to see a video that carries into the profession!
Do you get executed if you mess it up?
that is so cool
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!
Linked lists :))
@@rachadelmoutaouaffiq5019 The worst kind of list!
It's a idiotic video. Any system to consistently search boxes would have the same result.
@@markingraham4892 Uh... no, that's not true at all. It's true that other systems CAN have equally good results (nothing better) but not ALL systems will. Take, for example, the system of "everyone search the first 50 boxes." That's a consistent way to search, but it would obviously fail.
@@markingraham4892 care to elaborate?
Bravo, well explained! At 2:51 minutes where the problem is stated, the second line must state for completeness that the boxes are either numbered or will be arranged in a known preset configuration so the prisoners can prearrange using a numbering system that assigns each box a consistent number. I imagined all blank boxes with a number in it randomly placed somewhere in the room (not even adhering to a nice grid pattern) in which case this loop method would not work, nor the pairing that is explained later.
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!
Good stuff.
Bruh how do you even code that?
@@Harshil_Uppal it would be easier in javascript
But it's very easy anyways
nice
@@Harshil_Uppal Maybe have an array of numbers, size 100. Fill the array randomly with values from 1 to 100. Then, every prisoner searches the array. Every prisoner can have up to 50 attempts. You use the strategy of "index_to_search = array[index_to_search]", where on the first attempt, "index_to_search = prisoner_number". Each search must last less than 50 attempts. If prisoner_number != array[index_to_search] and attempt > 50, the experiment fails.
The real “magic” of this solution is that it ties the probability of success to one single condition (the state of the “loops” in the boxes) instead of a repeated condition (the odds of each prisoner finding the correct number).
You’ve immediately removed the exponential scaling of the probability. So even if you choose a sub-optimal method. Any method that is based on a single fixed condition is immediately an improvement.
ok
That is quite certain indeed. But i think vertasium forgot that not everything will form a loop as a set of boxes can end up with a box that has its own number.
@@daburnd lol no he didn't forget that. In fact, you start off with that. Hence, in your scenario, you'd find your number in the first attempt.
@@duitakarbhat that is only for the only for the prisoner that has the number of the box containing its own number. But not for the x - amount of boxes leading up to that one in the pointer line-up. For example : Box 1 points to box 2, box 2 points to box 3, box 3 points to itself. Hence, not everything needs to be a loop ( it can be a finite non looping set ), unless u put up the constraint that no box can contain its own number. Just handling this case asif it could only be closed loops therefore seems not logical.
@@daburnd if both boxes 2 and 3 point to box 3, it means they both contain the same number, 3. that's not allowed
Great explanation, actually totally makes sense! The visualisation with the numbers and loops only ending with your own number was so clarifying.
for me it was clearer to see it in this way: the reason the loop ends with your own slip is because, excluding the starting box, you only open a box if you already have its corresponding slip, so no other loop is possible (no slip can point to a box you already opened because you already got that slip pointing to that box)
@@assemblywizard8 well you also will always find your slip if you can open 100 of 100 boxes. you will also not open the same box twice because you already opened it and see that it is open. this alone isnt really the "aha" moment
@@assemblywizard8 That is another great way to word it that would have helped my brain when it was imploding in on itself
This is actually exactly how the turtle and hare algorithm works for arrays .Given an array on N+1 elements with numbers 1 to N, with only 1 element being repeated, you can actually find the repeated element using this concept. Though the algorithm is a little different, the concept is very similar. You can maybe make a video on that. It's a very interesting problem and a beautiful variation of Floyd's algorithm.
I wonder how you could find the one duplicate element using Floyd's algorithm. You may find it by chance if you use a random element to start with, but usually it would require to examine the complete loop structure. Or doesn't it?
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.
+
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)
So it turns it from a game of chance into Candyland.
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.
@@hansschwarz1338 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.
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
@@ngotranhoanhson5987 It is indeed bit tricky to understand, you can use a simpler analogy to understand it, suppose you roll a dice, the total possible outcomes would be 6, and lets consider we have to find the probablity of getting a even number. Here the sample space would be 6 (All possible outcomes), and the set of all even numbers on the die {2, 4, 6}, is of size 3, hence the probablity 3/6 i.e. 1/2. Similarly in the above case, the sample size would be all the possible ways we can put 100 numbers in 100 boxes and that is 100!. As we are finding the probablity of finding a loop of length 100, we will need a set of all possible unique loops of length 100. As explained in the video, that set will contain 100!/100 loops, so we divide that with the sample size of 100!. Hope that's helpful.
This riddle definitely seems impossible but the brute force approach confirms. Ran a program that played the scenario 50,000 times and yep... 3,450,000 prisoners died. Survival rate was 31% of the time. Nice work and as always, thanks for teaching us something new Derek!
I'm writing my own simulation for this, and I'm not getting the same results. Could I see your code please? I'm thinking I'm doing something wrong and looking to learn.
Yes please a github link would be appreciated. More to learn
Following
@@ace10414 he lied
I did a simulation and got about 29% chance. So seems pretty accurate. I'll share my code if anyone wants to see it
Works with 2 prisoners too who can both open 1 box each. If they don't discuss anything before and open one random box each, the probability of success is:
0,5 x 0,5 = 0,25 = 25%
If they agree to both open the box labeled their number, then either they will both be wrong (because the guards swapped box 1 and box 2) or both be right if the box numbers match the slips. So a 50% chance
15:57 Whenever that music starts I know my mind has just been expanded. Been watching you since high school Derek and just about to finish my degree in Physics. Thanks for all the knowledge and inspiration over the years!
does someone know how it's called?
@@marcobirra4455 firefly in a fairytale by Gareth Coker
@@homerpasha thank you so much
I think the counter-intuitiveness stems from the fact that the loop is no better than random selection for each individual attempt, but is way better for the riddle's success. Remember, the riddle is only concerned about ALL 100 people succeeding. It doesn't care for the 50 people who succeed on average. Anything that is not 100, is effectively 0.
100 is what the loop algorithm optimizes for. Despite not being allowed to communicate, prisoners can use the design of the riddle itself to collectively follow the same set of loops. Like putting all your eggs into one basket, following the same loops maximizes the chance of all 100 people succeeding. This is illustrated with the probability distribution at 10:24
what makes people think they dont get the correct loop is becausee they forget to start on their own number, if they choose a random number then they can get the wrong loop
Or you can just buy a new one. The old one always shows up moments after you buy the new one.
Thanks, this is definitely the trick to why this seems to not make sense.
Actually not at all. The loop strategy GUARANTEES that the prisoner is on the way to find his number. Because the box that had his number is by definition the last in the loop. The only thing that would stop him is if the loop is greater than 50 numbers. Random choosing strategies NEVER guarantee getting your number. If you phrase the problem this way, everyone thinks the answer is obvious.
@@HerculesBallsInc only if he chooses the right loop, so it's not a guarantee
Thanks for teaching me.
You're welcome
Hey destin when is your 2nd part of "Kodak film making" video coming ?
There you are!
Thanks , @SmarterEveryDay ,, you just questioned the same questions we had watching and following by you 👍🏻
2:23 "Teach me." is one of the best responses ever
WOW!!! That just blew my mind!!!! I was watching solving mystery videos because my teacher recommended it for the topic we were learning, and i came across this video and thought, "I MUST watch this", and it left me speechless. I subscribed just because of this.
Imagine coming up with this massively smart idea and still only having 31% chance not to get executed.
Life do be like that sometimes
Imagine trying to explain probability to a bunch of prisoners. I put the actual real-world chance at something around 0.001%
Imagine knowing this for a fact and no one listens 🤣
You'd use up your strategy time trying to convince them it's smart and gives a 31% chance at success then someone will speak louder then you saying "all that work for less than the 50% chance we get picking randomly?" And then everyone dies
31% chance of success is a hell of a lot better than effectively 0%.
The minute you mentioned loops, it no longer seemed impossible and actually seemed retroactively obvious. Math is so damned cool.
Same here. I had the same question that Destin did, but as soon as I realized that, unless the box you start with contains it's own (and hence your) number, you are guaranteed to be on the proper loop. It's only a question of how long that loop is. As soon as I was able to wrap my head around that, it made perfect sense.
I have a different solution that grants greater than a 31% chance.
It approaches this as if it were a trick question, and still completely satisfies all the rules/requirements.
"Each must leave the room as they found it."
They found it with 100 closed boxes. They didn't "find" any boxes open nor did they find any information or clues regarding which numbered slips were in which boxes.
On that premise, #1 (beforehand tells all of this strategy), and opens 1/50 (a 50% chance). He then takes ALL numbered slips placed in boxes 1-50 and he stuffs all of them in box #1 (just as he had told the rest of the group beforehand that he would do...Mind you; this is a "trick answer," but according to the rules, NOTHING specifies this is not allowed).
Then, prisoner #2 (who was beforehand told of this overall strategy-and understand/assume the rest were as well for the sake of time), then opens boxes 1 (which now has all numbered slips which were originally placed in boxes 1-50) and he opens boxes 51, 52, 53.... (you get the point) to box 99 (50 boxes).
As long as HIS number (2) isn't in box 100 (a 1% chance which lowers our overall group chance only to 49%!!!!), everything is still a go. Then, he also places all numbered slips he has now discovered (in boxes 1 & 51-99) all into box 1 (just like the first prisoner did).
Now, prisoner #3 has a 100% chance now as he just checks boxes 1 and 100 (which have all the numbered slips in them as the remaining boxes are empty) and then he places the numbered slip located in box 100 into box 1 as well! (So now ALL numbered slips are now located in box 1).
Prisoners #4, 5, 6 and so on only have to check box 1 and their chance is 100%, thus keeping our risk level/chance at 49%!
All the way to prisoner 100.
This way completely plays by the rules by the way according to the information/restrictions that was given us.
As we only talked strategy beforehand, only one entered at a time, we did not communicate during, and we each left the room as we found it; with 100 closed boxes that never got moved. Yes, the SLIPS got moved, but we "left the room as we found it," because prisoner #1 FOUND the room with 100 closed boxes in such order.
Also matching the approach of a "trick question/trick answer," you could also have prisoners 2-100 arranged tightly around the open doorway as prisoner 1 goes in, and all 2-100 could watch as he opens each box. They could each take notes on what box he opened and what number they witnessed him discover. And so on and so forth. This still allows for them entering 1 at a time as well as not communicating in any way with any of the others.
Another way is to say ok the room is sealed but with glass walls. Just the way my mind works and another way of looking at it. These answers give me more peace about it than the one discussed in this video. However, the solution discussed in this video is more fascinating and I'm sure true math experts (I am NOT one I'm just someone who greatly enjoys strategy and basic wisdom/philosophy) will prefer it the way it is in the video for the math aspects!
But how will the prisoners know the loops to find their numbers? Like which number to open next to get to their loops?
@@user-bu9xh4sg6v they open what ever number is in the box then open that box see what number is in that then they go to that number and open that box’s d so on until they find there number
@@nomoneyball5423 wait what if the first person cant find his number...
It actually becomes very clear and obvious when you understand the answer in full, it seems like what limits our understanding of how best to solve the problem lies within our understanding of the problem itself. Very cool and interesting problem and video, thanks for the education!
I actually had to pause the video and just sit back because my mind was so blown. I don't remember a video ever having this kind of effect on me. Very well explained. Thank you
Excellent video, but I think the question at 10:35, although answered with a very effective visual demonstration, is even more intuitively clear to answer. Simply ask the person to give you an example of such a loop where you start with your number but the loop ends without reaching it. They cannot, because it is logically not possible. By definition, the loop ends only when a paper slip redirects you to the original box, and if you started with the box that has your number, then that paper slip is your slip. In a worst-case scenario, the slip chasing takes you on a scavenger hunt across all 100 boxes (although the 50 box limit would have stopped you before then), but there is never any case where you enter a "wrong" loop. By definition, if you start with your box, then you're in the correct loop, because eventually *some* box has to have your slip, and then the slip for that box has to be somewhere else (because it's clearly not in the mentioned box, since that box contains *your* slip) and this goes on across either all 100 boxes or less. Problem solved.
Yep I would ask destin to come up with a scenario where the loop is closed, but doesn’t include yours. Like actually have him make up the numbers in the boxes and get that scenario
He would soon realize you can only close the loop where it started (which is your number). It’s pretty intuitive
That's exactly what I thought. The visual demonstration didn't stick to me quite well so I instead tried to imagine a loop where you don't end where you started. I imagined 5 boxes to make the problem more simple, that way it's easy to see how you would always eventually end up with the initial number.
This is also the key to the probability being so high with this strategy - because all 100 prisoners start on a different number, you collectively guaruntee to enter every possible loop, and therefore find every number (unless there is a loop greater than 50).
I was imagining a "loop" that starts at my box, and then instead of coming back to my box, it reenters the loop at some later point. For example, 1..2..3..4..2. But that's impossible, because it would require two different boxes to contain the same number ("2" in the example). Thus the loop must eventually come back to my box.
Haha I got to that guy's reaction and now I'm not thinking these guys are as qualified to talk about statistics if they're racking their brains *that* hard thinking that the most unintuitive part of this problem is that your loop always contains itself.
I guess if you aren't realizing that each box only has one slip pointing to it... But that was vital to the premise!
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.
And not created by them at all. Its a category theory loop. Took this s over 35 years ago. The same problem but worded different as in not prisoners is shown and proven in elementary category theory. Don't need all that stats to prove or show s. All one needs to know is how to categorize the problem and check where the functions associate then if s running link function appears. Lol category theory is like a cannon that swats fly problems like that
it's not that deep or interesting to want to be taught something lmao
@@DevinDTV But it‘s humble and epic.
right? I love it, it gave me chills to hear because I feel like it's such a rare thing these days for people to admit they don't know something, let alone for them to actually ask to learn it
I felt the same
Really great explanation!
Another way to see that boxes always form a loop when you follow the algorithm is that a box will always have a different number inside of it then the box's index (unless you happened to start with a box that has your number in it). There for since the boxes always have a different number inside it (and numbers aren't repeated), you will always be taken to a new box (until you've made a loop)
Writing a research paper and still telling the reader to figure it out for him or herself is peak professor energy.
T h e p r o o f o f t h i s i s t o o m a g n i f i c e n t f o r t h i s b o o k.
And people still wonder why math graduates tend to hide in the woods sending bombs to people
Why are the replies gone?
@@Khaerulbtg Happens sometimes. I'm guessing either they were removed individually, or the accounts have been poofed. 🤷♂️
It would be really awesome to see the original reviews of that paper (from when is was submitted to publication). I bet those reviewers were also beaming with professor energy 😂😂
Had to try it myself, thanks for such thorough explanation!
function prisonersFindTheirBoxes(numberOfBoxes) {
const boxes = Array.from({ length: numberOfBoxes }, (_, i) => i + 1);
const shuffledBoxes = shuffleArray([...boxes]);
function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
const map = new Map();
boxes.forEach((value, index) => {
map.set(value, shuffledBoxes[index]);
});
return {
map,
boxes: shuffledBoxes,
};
};
function getAwayFromPrisonOrDie() {
const numberOfBoxes = 100;
const numberOfTries = Math.round(numberOfBoxes / 2);
const { map, boxes } = prisonersFindTheirBoxes(numberOfBoxes);
for (let prisoner = 1; prisoner
Well yes, does work. Thanks for posting.
I was really confused at first on how whatever number you start with is guaranteed to be in your loop, but once I started to type out a comment questioning it I totally realized how it works. In order to finish your loop you have to end up back where you start, and since none of the boxes can be empty, you're guaranteed to be in some sort of loop.
Then you have two boxes which contain “3”… Every number occurs exactly once in all the boxes.
If box 1 contains “3” then no other box have “3” you are guaranteed at this point that your loop you are on cannot have box which contains the same number (1 has 3, 3 has to have something else ie 5, then 5 has to have somethine else and so on, until you find box pointing you back to 1)
Try it with something small like 3 or 4 boxes. Whatever you try you will always see only loops. No dead ends. If you find dead end it means there are duplicates and some number is missing (duplicate took its place)
@@TheJakoubecek Oh man you are right🤯 i somehow didn't see that Thanks!!
In a loop, yes. But why in your loop ? I don't understand it...
@@nicolass.5849 You have to end up back where you start in a loop. And since in this case you start at your own number, one of the boxes in your loop must also contain your number. If none of them did, you would never be able to finish the loop.
10:55. Because the system was explained so well I did not find this confusing at all. You're gonna be on the right loop as long as you pick the box with your number. The only question remaining is how long that loop is.
Well, Destin still didn't watch the Veritasium video back then
@unfaithfulevil 🅥 Your a joke. You have no content!
@unfaithfulevil 🅥 that checkmark looks slightly off and then I realized lmao
but like also thats a bit of a silly question, as is derrick's answer. The only way to complete the loop is to find the correct slip.
For me he has a false title
I finally understood WHY it still seems Impossible/Wrong even AFTER learning the answer to the riddle. And my god it's profound.
Because when someone asks (After learning what the solution is) that "What makes you think you'd necessarily be on the correct loop?" and then you respond with the logic of it, The logic of it, [even though it's accurate and mathematically sound/proven] is "CIRCULAR"; so no wonder it seems false to us because circular logic usually IS false, Except when talking about the things that are circular in nature, like a freaking loop.
Remember how in your video "Math's fundamental flaw" You explained how paradoxes arise from self reference? Well a loop, by definition Must reference itself.
So because our brain will still want to reject it, we say "Yeah i know it's not random and you're opening the box with your number on it but what prevents you from ending up on the wrong loop?"
And the response is "Because you're opening the box with your number on it".
See the "Problem"? that was part of the question but that is apparently now the ANSWER ?!!
Even your explanation in this very video can be summarized in "Because a loop is a loop, it must be a loop".
It's kind of like learning God is real and asking him how do you exist?! and God telling you "Because I am God and i am infinitely intelligent and powerful i created myself into existence". The logic could be true but it still seems like WTF...!
Imagine being the prisoner trying to sell this plan: "Now we still have a 70% chance of failure, and it's much to difficult to explain, but you all need to follow my instructions exactly for us to have any chance." Then every dissenter lowers your chance by half agian. At this point, I'm starting to think this time would be better spent coordinating a riot.
I was very confused for a minute, until i realized you were trying to say "dissenter". Descent is going down, decent is not a verb, dissent is disagreeing.
Wow you're very smart with a great understanding of spelling and grammar. It's a shame those won't win you any friends or help you communicate effectively with those you manage to piss off.
@@BenjaminRonlund I'm sure going full roid rage in a TH-cam comment section is the correct way to make friends?
@@BenjaminRonlund too bad your misspellings is actually not going help you communicate effectively.
@@BenjaminRonlund yep, the problem is definitely with making literally any corrections to anybody ever, not with the people who go "ur dum that's not a word".
It's 100% not allowed to comment on spelling or grammar, even when it will help make the original post more clear to future readers and you fully explain what the correct word is and why it's correct.
Explaining things never helped anybody, especially those learning an extremely difficult language like English, whether it be as a first language or a second.
The best thing about this loop strategy would be if someone finds their number in their last chance of opening a box, they make sure that they will be freed since if one 50 length loop exists, the others can be maximum 50 length
Friend! None of the other comments or the video itself allowed me to understand this. But your comment just did! Just visualized what you said and now I get it. Sincere thanks!
I’ve read this multiple times and each time I flip flop between understanding and not understanding
@@lethalwolf7455 Happy to have helped you to understand because I, too, hardly understood it after reading some comments
@@Ren-fo4lg lol me too
This comment is 🙌🏻
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.
Especially going the opposite direction to shoe that approximately 69% of the time, the prisoners get executed.
Rather morbid problem 😅
@@kevinbean3679
69?
Nice!
Same, I knew that it had to be able to be related to some nice little expression. Now I’m trying to figure out how and if the “2” in 1 - ln(2) is related somehow to the ratio of choices per total boxes the prisoners are allowed to make
So out of hundred groups made up of 100 Prisoners, only 31 groups will get all the answers and go home, the rest 69 groups will have to die.
@@AvanaVana It is obvious if you do the integration. int^2n_n 1/x dx = ln (2n) - ln (n) = ln 2, and that upper limit of 2 is the ratio you mentioned.
🎯 Key Takeaways for quick navigation:
00:00 *🧩 Introduction to the 100 Prisoners Riddle*
- Introduction of a counterintuitive riddle that challenges perceptions, even after the solution is known.
- Mention of widespread confusion and incorrect explanations on the topic.
- Setup of the riddle involving 100 prisoners and a unique challenge they face.
02:02 *🤔 The Counterintuitive Solution*
- Explanation of how a seemingly impossible probability can be significantly improved with the right strategy.
- Introduction of the concept of mathematical strategy to solve the riddle.
03:11 *🔄 The Loop Strategy Explained*
- Detailed explanation of the loop strategy for prisoners to increase their survival odds.
- Illustration of how this strategy transforms theproblem and its solution.
05:44 *📊 Probability and Loops*
- Analysis of how loops determine the success of the strategy.
- Introduction to the calculation of success probability based on loop lengths.
09:46 *🤝 Impact of Strategy on Individual Probabilities*
- Discussion on how the loop strategy affects individual and collective probabilities.
- Clarification of misconceptions regarding loop participation and success rates.
12:43 *🛡️ Countermeasures and Adaptations*
- Exploration of scenarios involving external interference with the strategy, and how prisoners can adapt.
- Insight into the resilience of the strategy against manipulation.
14:15 *📈 Scaling the Problem*
- Examination of the problem's scalability and the consistent success rate across different prisoner numbers.
- Explanation of the mathematical limit of the strategy's success rate.
16:44 *💡 Learning from the Riddle*
- Conclusion highlighting the educational value of the riddle and its implications.
- Promotion of a platform for further learning and problem-solving skills development.
Made with HARPA AI
Now please let Harpa AI explain how this peculiar 1/n formula works, and where this 31.18% winning chance comes from.
This is super cool.
It's amazing things
DO NOT POST ANY REPLY! DO NOT MENTION ANYTHING ABOUT TIMEBUCKS OR I WILL REJECT YOUR SUBMISSION, JUST THUMBS UP AND THATS IT
Nice
Can we wait for a moment and appreciate the crazy animations done by the editor 👏
who is Ve editor, thats the biggest Q of all.
@@fundemort check the bottom of the description, where the credits are.
@@soupnowplease3825 ah. never cared to read credits until you pointed it lol.
Who says the editor even did the animations? Maybe he just put the animations in the edit -,-
@@Seawolf159 yea I’m pretty sure the animator(s) are different from the editor
I was confused when the guy asked how you know you're in the right loop because my mind never questioned that part. I was more fascinated by the graph, and how it worked that either everyone succeeded, or less than half did. After some thinking, that made sense to me too.
But in some ways, it's a sign of your good intuition that you didn't consider that: it's a blunder (in the sense that it just violates the conditions of the problem: if you go to box n_1, it directs you to box n_2, box n_2 directs you to box n_3, and box n_3 directs you back to box n_2, the slip reading n_2 has appeared twice). I think the video doesn't point this out as forcefully as it could (the ensuing explanation is pretty indirect).
The reason that either most people succeed or less than half is because if a loop of over 50 exists, that means at least 50 prisoners will be on that loop, and will all fail.
But I thought that about 3 second before he told
OK but why is it a given that my number is in my loop?
@@griffinbur1118that will cause a Pigeon-Hole issue and that means number is missing , failing everyone , everytime
Hello i'm 14 years old and your videos are really interesting and cool !!
rn i'm meant to be doing school hw :)
i saw this riddle on another youtube video about 5 years ago and forgot about it but watching this video gave me a flood of memories of watching many riddle videos in my younger days
I commented to say:
I liked how at 8:48 you said "THIS IS A GENERAL RESULT" and then I had to use my brain (Drew) ^_^
Therefore the following graph with .31 and .69 was the only part of the video where I didn't immediately understand how we got there, which is not necessarily a bad thing?
Also does 21142 on your prisoner costume have a hidden meaning???
To random strangers on the youtube: what should I study at Uni (atm I'm thinking medicine but what if I regret not doing maths or something else in the future) ik i have a long time to decide but i need to choose my a levels soon so do you have any good advice?
Thank you for reading my comment
It's hard for anyone random to tell you what you should study. You should study what you want to do as a job, but it's hard to know what you'll want to do in 10 years. Had I known I wanted to do software engineering when I was 14 years old, I'd probably be a far better software engineer today than I actually am.
at first I was like mind blown, but then as Derek explains how it works, my mind unblowned down to normal. Fantastic work my friend!
To me, the simplest way to explain the effect is… if a there is 1 that box is looked in 0 times, everyone fails. This method keeps that from happening.
After the experiment, if you look at the boxes all the prisoners chose to look through, box 20 may have been looked in 5 times, box 21 was looked in 78 times, box 22 was looked at 61 times. The more a box is looked in, the more likely it is to be found by the right person, and the opposite is true. This method allows everybody to look at each box 50 times.
Could also just take the prisoners ahead of time, line them all up, and number them 1 to 100. Tell them to open their number, and the following 50 numbers. So prisoner 6 opens 6 and 7 and 8, etc. Or you could tell them to open their number and add 2, so 6 and 8 and 10..
you just got mind imploded!
_MIND QUAD!_
I love the Destin cameos. His reactions very much mirrored my own, despite him being a LOT more knowledgeable about math than I am.
I agree. When Destin said "Teach me." I thought, "...and that's why I like him." Their honest amazement and fascination with learning make these two great teachers for the layman.
This is quite possibly the most down-to-Earth math video I've ever watched. I'm going to send this to anyone I geek out about combinatorics to.
Woah, it's Gingy! Big fan, mate
@@the-thane cheers mate
I am jealous if you have such friends.
@@MegaJohny777I am indeed lucky to be a CS student :-)
Really? I think Derek explained the solution in a really fantastic way, but he did not go into detail why those chances are calculated that way (that wasn't the point anyway... although I do think the title of the video is very clickbaity as usual and so who knows what was the point - more views?)...
Anyway, maybe you should check the channels of Matt Parker (Stand-up Maths) and 3Blue1Brown
i made a smaller version of this riddle by decreasing the number of participants to 4 and i made artificial intelligence to randomly pick numbers for me
with the loop strategy they succeeded 5 times out of 10
with random picking they didn't succeed in 10 trials.
it was really fascinating.
I did that also. Please see my posts. It raised a few questions for me. Would be happy if you'd weigh in.
Funny how you can solve pretty much the craziest logic riddles with AI
@@GodbornNoven .... or you could just use a die. Don't be silly.
Omg, it finally clicked for me!!! 😃 What it came down to for me was one very important realization: If you start with your own box number, you are GUARANTEED to always be on the loop that contains your slip! It's literally impossible for your slip to be inside any other loops.
Let's say your number is 66, and you first open box #66. If slip 66 WASN'T in your box, then what was? Maybe slip 13? Okayyy.... Then what's in box #13?? It can't be slip 13 because that was in box #66, so let's go check... You open box #13 and it has slip 2 inside. Okayyyyyy, then what's in box #2?? Surely it's not 13, and it's not 2, because we already found those slips in the last two boxes...
You can keep following the strategy, going box to box as the numbers on the slips lead you around, and every time you check a new box, there are only 2 outcomes: Either you find slip 66 which "completes the loop" and takes you back to box #66 (winning the game), or you find every single other number in the process, until you eventually get to the very last box to check, which WILL have slip 66 inside, because every box has a slip, there are only 100 boxes, and all 100 slips were used. No boxes are empty, and no boxes contain the same number as any other.
While following the strategy, there is no possible way for you to reach a dead end, because every number you pull is a NEW number. You COULD get stuck in a loop, but the only way for that to happen is if you find a number which leads you back to the FIRST box you opened, which will be the number we're looking for, meaning you've won! You will never find a number leading you back to any other boxes you previously opened, because you've already located those slips that point to those boxes, they are in the trail "behind" you.
Knowing that, now we're simply relying on the random chance that when the numbers were initially scrambled, no loops greater than size 50 were created. And as long as that's the case, it will be the same for all 100 players since the numbers were only scrambled once, and everyone will be able to locate their slip in 50 steps or less.
Thanks to Derek already doing the math on this for us, we know there is roughly a 30% chance this will happen. On the contrary, 70% of the time that the game is set up, we will instead have a situation in which a loop greater than 50 will exist, meaning some players whose numbers fall inside that unforseen large loop will follow the strategy and eventually run out of picks before they can follow the loop all the way back to their number.
Alas, I can sleep tonight 😊
Here's an analogy, which I think will be easier to comprehend:
Imagine you have a class of 20 students. You ask each student to write their name on a piece of paper, then fold it up and toss it in a hat. You then have all 20 students randomly choose a paper from the hat and hold onto it (no peeking!).
One at a time, you then give each student 10 guesses each to find their own name, which also includes the piece of paper in their own hands since they might've grabbed their own name by random chance.
Taking this set up, what do you think would be the wisest strategy?
If you ask Timmy to reveal his paper, he might have Tommy's name. If you then ask Tommy to reveal his paper, he could have Susan... Then if you ask Susan to reveal HER paper she could have Timmy, so now that loop is a dead end for poor Travis, who is just lost 3 of his guesses trying to find his own name. He could ask another random classmate, but that could end up with him getting stuck in another loop which doesn't contain his own name... Ie, he might ask Billy, who has his own name by chance. Or he might ask Chad, not knowing that Chad and Jeff have each other's names already....
So again, what's the best strategy?? Well how about Travis checks his OWN paper? Either it contains his own name, which makes him a winner, or it contains someone else's name, in which he can guarantee that person doesn't have THEIR OWN name.
So Travis opens his own paper and see's Timmy's name. His best option is to now ask Timmy who's name he has, because Travis know's that Timmy must have either "Travis", or someone else in the class, but not "Timmy". Asking Timmy will always lead to Travis either finding his own name, or finding another potential guess from a new student, in which he knows that person wont already be holding their own name, nor any of the names of the students he has already asked. As he approaches his 10th guess, his odds become better and better at finding his own name.
Now, he might run out of guesses before he finds his own name... BUT, as long as there are no chains (or "loops") of names which exceed 10 people before circling back around to the first, then every student in the class will be able to play the game and find their own name using this strategy, in 10 guesses or less.
Derek's math tells us that roughly 30% of the time that the students randomly choose a name from the hat, we will have a winning circumstance where no "name chains" exceed 10 people in length.
In one of the boxes is a red slip without a number.
Your excitement for figuring it out is contagious!
Yes, your explanation is far better than the one provided in the video.
You said: "a loop greater than 50 will exist, meaning some players whose numbers fall inside that unforseen large loop will follow the strategy and eventually run out of picks before they can follow the loop all the way back to their number."
No. ALL of the prisoners on that loop will fail, not just some of them.
Imagine spending hours to come up with that strategy and the first prisoner doesn't find their number
the rules are impossible by themselves.
One of the rules say: "they must leave the room exactly as they found it". Once you enter the room, the room is not the same as it once was. Since prisoners are allowed to open and close the boxes to look for their number, the room can't be exactly as they found it. Which means, the own problem is a fraud.
Another rule says:
"If all 100 prisoners find their number "during" their turn in the room, they will all be freed, but if even one fails, they will all be executed."
Its a paradox. Its impossible to 100 prisoners to find their number "during" their turn, since they are getting inside the room one after another.
@@athletico3548so with the first rule point you explained; you mean that if a prisoner knows the numbers, the math fails? But the prisoners arent allowed to share info with each other. It's still random for each individual.
Also, idont really get the second point you made, can you elaborate?
@@athletico3548 how would you rephrase the rules then? Im having a hard time understanding, i do understand the chess lore and heraclitus' river, i dont understand the second point. Maybe its because my main language is not english, but i dont see it :(
This is some qualia stuff right here
@@SublimeWeasel rephrasing it: "If each of the 100 prisoners find their number during their turn in the room, they will all be freed, but if even one fails, they will all be executed."
@@athletico3548this just seems like semantic nonsense.
Also how does leaving the room exactly as they found it not make sense? Open and close boxes simple. They are closed as before.
Seriously what are you trying to say
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.
Ah, he should have said that in the video, that is actually a good explanation
So in order to get back to the initial box picked, with your number on it, you have to find the right slip. If you find the slip you are good. So your number HAS to be in the loop that also contains the box with your number. Hence, if the longest chain is 50 or less, everyone will find their number. Damn it actually makes sense now
That's a good way of thinking about it.
@Any Body no, it isn't: every prisoner has a *unique* number, so you can't find 2 boxes that bring you to the same box
@Any Body The way the riddle is set up this shouldn't be possible. If each slip exists only once, box 23 can't have slip 54, because that slip was already in box 7.
10:32 regarding Dustin's comment, to get onto a self-closed loop from outside the loop would require the same number appearing twice (say the loop you're going into is ab...ca, and you go from d to a, then c and d contain a).
I was in shock when he flipped the whiteboard over again at 8:17. The contents were no longer the same as what he wrote earlier on that side of the board. And then I remembered that cutting is a thing. When done right, you don't notice them. Props to the editor!
Oh nice. I didn’t notice that. 🤣 Spatial memory. Haha
the cut is at 8:07
It's a three sided white board
I noticed that, it was a Brilliant (pun intended) cut :)
You might want to see a psychiatrist if something this simple causes you shock
Demonstrating, yet again, just how elegant and, frankly, satisfying mathematics can be. What got me through applied mathematics in college was the idea that there may be 100 different ways to get to a solution, but there's only one specific solution. Now, the solution may involve a set of solutions (a la differential equations), but if you're a fan of mathematics, you'll know what I mean. Enjoyed this one, Derek. Great work, as always.
I was surprised by the "what if you're on the wrong loop" question, because that part seemed the most intuitive to me.
The part I struggled with was how the likelihood of everyone winning was ~30%. The math to reach that number makes sense, but the result still seems really unintuitive to me.
It’s easier if you don’t think about the prisoners at all, just loops. If there is no loop > 50, every prisoner makes it. And there’s a lot more ways to make small loops than big loops, so any given random loop is more likely to be small than large
@@noahwelikson1100 Yeah, that's what I figured. ~30% feels way too low.
Yeah wtf when he asked that question I went "bruh" out loud
I felt the exact same way. The probability works out from graph theory and combinatorics though. You have to sum the number of ways you can make unique loops (cycles) of greater than half the number of boxes and divide by full number of permutations of the boxes
I asked about this. You could (maybe - not sure) derive it from normal distribution.. all the loops are random so it follows a random distrib meaning 68% of the time the loops will be in the 1 standard deviation but as the group needs to be right (100% of the prisoners need to find the right number) they will be right only 31% of the time (100% of them) and 68% of the time they will be in the 1 standard dev.. (meaning a part of them will lose so all of them lose)
2:45
Basically pick a random box,if the box says a number thats not yours,count the boxes till to that number u go and open it, example: u have number 6, if u opened the 5th box out of 10 boxes and the fifth box shows the number 2,go to the 2nd box and open it,if shows 8 then go to 8th,repeat all that process untill u get ur number,even luckier if u got ur number less than 50.
i've known about this puzzle, and the solution, for literally a decade (at least).
Until now, I never understood WHY it works.
Now I do. Thank you.
It's a trick, the prison is in the u.s. they are all gunna be executed anyway
@J Boss Well in the case of the prisoners, the warden will notice the box swapping
And probably execute them all
In the case of the sympathetic prison guard, the warden probably thinks "oh they're just checking the boxes"
@J Boss Part of the premise was that the prisoners must leave the room exactly as it was when they entered it.
@J Boss I think the issue is that the sympathetic officer needs to intentionally know about the >50 loop and needs to swap 2 boxes that render both halves of the loop to be less than 50 (versus just swapping 2 boxes randomly). I don't know the math to solve it but, logically, if Derek were to swap boxes 78 and 57 he would've made an even longer loop (combining the small loop to the right). Or, if he were to swap boxes 80 and 42 (or any 2 boxes that are close together on the loop) then he would create a loop of 3 but potentially leave a loop greater than 50.
Since, like the monty hall problem, this benefits from other ways of explaining, here's another way to think about how every box must form a closed loop:
for it to NOT form a closed loop, it'd have to be something like 1 -> 2 -> 3 -> 4 -> 2, where 1 never gets repeated and instead leads to a smaller loop. this, however, indicates 2 slips that point to 2, which isn't possible, since it means no slips point to 1.
Why can’t u have no slips pointing to 1
@@hishaam5429 There are 100 unique numbers and 100 unique boxes so having 2 numbers that are the same is a contradiction
Thus there cannot be 2 boxes pointing to 2
Which further implies that there must be one box pointing to the number 1
@@hishaam5429 the rule is that every prisoner has a slip somewhere. the game would be rigged if prisoner 1 had no slip
Your explanation is fantastic. Traveller!
@@hishaam5429 you could have a loop with 99 slips that don't point to 1, but then box 1 would have to contain a slip that pointed to box 1 -- a loop of size one.
I feel like the really cruel thing to do would be to allow the prisoners to look at 95-97 boxes, with the same thing. If they figure out the stragegy, it's like a >95% chance of success. If they guess randomly, it's
What is the probability of prisoner compliance and success if the sheets of paper were face up?
thats awesome! A much better example to use with people
exactly! try to convince your inmates now! the indivudual 97% seem so much more intuitive than trying to grasp even only that you'll always be on your own loop.. :D
for nerds who want to avoid using their calculator: (97/100)^100 = 4.75525% (rounded since there was a 0 after the last digit)
if they opened them randomly at 95 choices each, that would give them a 0.592% chance.
similarly, you could do this with 4 boxes and 10 friends. let them open up 3 boxes each to try to find something in one of the boxes. If the goal is to win if every one finds what was in the box, then they would have about the same odds.
What’s mad is that you can have a prisoner check 99 boxes, and STILL have only a 36% chance if you do it randomly lol
The illustrations you gave were so good!
Miltersen: "Hey, i made this riddle. Anyone want to try it?"
Everyone: "Dang, it is kinda difficult. What is the answer?"
Miltersen: "Idk go figure it out"
Haha yeah
His name bro is funny, u could have user that
"This problem is left as an exercise to the reader" is just a fancier way of saying "idk lol"
@@hahanamegobrrr6667 I've had someone say that to me before. That's how you know they are full of BS.
Love how Destin just says "Teach me", that's humbleness right there
That's what I love about Destin. He is always so humble and willing to learn from other people.
He would be a good dude to hang out with, I feel.
Btw, "humility" is the form of the word you were looking for.
he's a humble guy, just not feeling very smart that day following the answer
@@Plant_Parenthoodboth are acceptable,both refer to being modest
@@Billy.Nomates So it is! My bad.
Disregard my earlier statement.
I guess humbleness technically isn’t wrong but humility would be better in your context.
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.
So in the rubik's case, there's also a 31% chance of solving it blindfolded?
@@mikebarrientos5085 No, because you can look through the whole thing. Essentially, the 31% chance is if there is a cycle greater than half of the total number of pieces, and that is not important in the rubik's case, because there is no constraint about only looking at half the pieces.
@@lukegorman4523 ohh makes sense
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.
Wow I’ve always been scared of trying to learn blindfolded but this comment gave motivation, thank you:)
@ 10:44 - As far as the question of not coming back to your own number: One short answer is - remember that YOU (and the prisoners' group) are the one defining these "loops." Hence, by having faith in these loop definitions, you can be *certain* that, given enough chances (as an individual prisoner), you will ALWAYS find your number. The PROBLEM is, that, 69% of the time, *one* of the loops will be 51 numbers long - or longer. So, 69% of the time, because of the unfortunate "luck of the draw," the 100 prisoners are going to die, for certain. They will discover this fate with the first prisoner's number to fall on the "51+ length" loop, as he will use up all of his 50 chances before finding his number.
However, the positive flip-side, as seen on the (Z-factor?) diagram above, is that 31% of the time, ALL of the "prisoner-defined" loops are 50 numbers long, or *less.* This guarantees that, following the "prisoner-defined" loop definition system, and loops defined therein, EVERY SINGLE PRISONER will be *guaranteed* to find his number 100% of the time - in 50 chances or fewer. This is what thus also guarantees that, as a group, the prisoners will certainly succeed, 100% OF that 31% of the time! And compared to (1/2)^100, the standard odds of such a thing happening at random, that's really quite an amazing improvement! 😉👍
In thinking about the looping, I had to realize that the loop couldn't end early by the slip refering to its own box or one already visited because you reached them with the single refering slip (but you can start with the lucky loop of one by finding the right slip in the first box you open). This seems crucial to why the probability is so counter-intuitive. The set-up is highly non-random, low entropy, high information in that there is only one slip for each number, and this solution takes maximal advantage of that. Because of the single slip principle, each one is in a loop, and you can't get on the wrong loop if you start by choosing the number you are seeking. Each time you jump to a new number, that is the only way you can get there, and you will always be sent to another new, not previously reached number from that point.
When you start doing the loop strategy, the riddle goes from randomly picking things to process of elimination.
Right. If you start with Box 2 and get Slip 1, you move to Box 1, but there's no way you'll find Slip 1 in there because you already (just) found it. The shortest loop you could get at that point is a length of 2 by finding Slip 2, etc, etc.
The bit I don't get is how adding numbers to boxes or slips somehow ensures you can find your own slip.
Yes it kicks you onto a different loop strategy. But it doesn't explain how you ensure you find your targeted loop as opposed to ending up on someone else's loop.
After all the reason the loop strategy works is because of the fact there are no branching paths on your loop as it is unique and contains your own number. If you mess with the starting loop pattern yes you find a new unique loop. But your number could Very well be on some other loop. Unless somehow slip +5 strat is somehow guaranteed to find your box +5 as opposed to your original box.
I would expect it just left you on another person's loop.
Of course the correct way to ensure failure is to make all prisoners remove their slip from the containing box upon finding it. Even a loop of size two will break as soon as the first prisoner finds his slip as the second prisoner will be offered no clues about how to find his own slip.
@@glenmcgillivray4707 how could you end up on someone else's loop if the core gameplay is still here? You re-numbered all boxex but there're still hundred of them, from 1 to 100. And you still can't get the number you've already found (because you've already found it, there're no twins). You just can't create a loop where there IS box with your number ON it but WITHOUT box with your number INSIDE it. It is impossible unles there's two boxes with the same number or smth like that.
Basically, you can randomly mix box numbers without breaking the rule. The only reason why all of them have to add one specific number, because they can't mix boxes physically and have to be sure they won't make a mistake mixing numbers in their mind. Re-numbering boxes adding any constant number is solid way to do that.
I'm not sure why this break the loop created by guard, tho, can't imagine it or do math... But sounds right, I just need to draw this to see, the picture in video were too small for me.
@@inter_acies they were saying that should your warden cheat by making loops longer than 50. Say intentionally making it go to 100. You can shift the box numbers to create an entirely new sequence of loops.
This i believe. What I struggle with is how to ensure your number is within the specific loop you create in this manner.
If you open your box +5 and it contains itself. You aren't free. So what's the trick here. How do we mess with the loop of say 99 and 1 to find your reordered loop.
Here’s how I thought about the must be on a loop issue, and it might help others. When you look into your numbered box you have started a path which must end. the only way the path ends is by reaching a box you have already opened. This can happen in two ways, you find a box with the starting number or you find a number which points you back to a number you were previously on which would mean you found a number twice in your path, but finding a number twice is not possible as each number only appears once. The only way your path ends is by completing the loop and finding the box with your starting number.
This is the key: You can't enter a loop from outside the loop. It's impossible to have "tails" attached to a loop because it would mean two separate labels point to one box. (it would also imply there is a box with nothing pointing to it.) This isn't allowed per the rules of the game.
Or you are unlucky enough to be in the worse-case scenario. (1-100)
Why is that any different than stating at box 1 and ending at box 50? I’m slow cause I’m not understanding the difference. Why is moving around to boxes based on the number in a box any more special…. Now I realize it must be because all the smart people get it, but I just can’t make sense of it…opening a box and reading a number inside, then going to that box seems just as random..
@@ediartiva By the rules of the game you're not allowed to keep looking after 50 boxes, but if you ignore the rule and keep on then you will ALWAYS eventually find your number, in the worst case it would be in the very last box that's not opened. If there are no duplicates and no empty boxes there's no way you end the loop without finding your own number.
That's actually false. If you search 50 boxes without finding your number, you must leave without completing your loop.
I love the tools used for demonstration, either if they were shown on screen as a graph, its coloring, or actual objects. It helps so much to figure out whats going on
STEINER VOICE: When you don't use this strategy your odds drastic go down.
This is a great video! Very interesting and incredibly well editted
The puzzle is even more interesting if it's modified to say that the first prisoner is allowed to check all boxes and make one swap. Then telling that there exists a strategy which guarantees success sounds even more incredible.
I love it
Still we most hope that the prisoner in question swaps the longer loop instead of a smaller one
@@markmuller7962 prisoner only needs to check 50 boxes to guarantee they can always swap in a way that ensures no chain is longer than 50 after the swap. The only reason the first prisoner needs to be allowed to check all boxes is so that they themselves are guaranteed to find their own number. The puzzle can also state that all prisoners can check only 50 boxes, but the first one can do a swap, while the rest must find their number.
it is not 100% guaranteed, still needs to choose the correct loop...
@ I know how the riddle and the riddle solution works.
Thing is, if the first prisoner swaps a loop of 4 boxes he only creates 2 loops of 2 boxes while the eventual 50+ loop stays intact and it's gonna kill the prisoners.
The benevolent guard in the video either knows all the numbers inside the boxes or gets "lucky" by swapping the cards of the longest loop
@@yosefsl30 Right
the question at 10:40 is explained by that a prisoner will always start from the box of his own number assuming that the last slip of the loop will be his numbered slip as explained at 5:17 , so it is a 100% chance that the prisoner numbered slip exists in the loop, but only a 31% chance that the loop is smaller than 51. I think this is the simple explanation to this question.
Almost, it’s a 31% chance EVERY prisoners loop is 50 or less. So for all 100 of them
Thank you so much i had a hard time digesting that one. I initially thought that the explanation only justifies the existence of the loops, but does not ensure the prisoner to be in the 'correct loop'.
If the loop has all the numbers,
Why do you care that the last number is yours or not? Your number can be inside the loop.
if you randomly choose any box at the beginning the probabilities of finding your number are the same as if you choose to start with your number box.
I still dont understand why you have to find your number in the loop you pick?
You have 31% to have largest loop at 50.
You still have to choose the RIGHT LOOP.
@@minhtrinh3646 I am convinced that this is incorrect, because it assumes that the boxes will be ordered in a "loop", so in reality it is pre-ordered, that is, it is not random.
That 30% chance is only possible if someone previously ordered the boxes as a "loop". In a real case where the numbers are ordered randomly, this strategy is useless.
Ironically, this also changes what the prisoners want to see when they're looking for their number. If you're picking randomly, you want to find your number as quickly as possible. But after coming up with this strategy, you want to see chains that are decently long, but still under 51. You don't actually want to see short chains. It's good for you, personally if your number is in a short chain, but the more short chains there are, the higher the probability that one of the other, longer chains is gonna be above 51 numbers. Since it doesn't really matter how fast you find your number since all prisoners either fail or succeed together, what you want to see is a long chain, because every other prisoner in your chain is also GUARANTEED to find their number with the same strategy.
In fact, taken to its logical extreme, although the individual prisoner would probably be stressed if they're on box 49 and still haven't found their number, if they hit box 50 and find their number, they can celebrate right then and there, because a chain of 50 is a guaranteed win, because none of the other chains can be more than 50 in a set of 100.
How is your last sentence not just a 50% chance of picking the right loop of 50 that contains your number? Then multiplied by 100 prisoners..
@@mediagirl eitherway it will be the 50th box no matter where u start, cuz its a loop
There's only 1 chain of 100 numbers, its where the prisoners' number is on that chain that is how long their loop is.
@@mediagirl There's no way to start on the wrong loop, since they're picking the loop that contains their number by default. They're picking the box with their number on it, meaning the loop will always end with their number, since that's where it loops back around. The only factor is then whether or not their loop is less than 51 numbers long, because they can only open 50 boxes. If one loop is 50, then no other loop can be 51 or higher, meaning every prisoner is going to pick their loop, and they will always be able to complete their loop, since none are more than 51.
You all need to watch the video again. You are ALWAYS, 100% of the time, going to pick your own number's loop if you start on the box with your number on it, because that's what makes it a loop. You literally cannot start on the wrong loop if you pick your own number, since picking your number MEANS starting on your own loop.
The only question then is "if I'm only allowed to open 50 boxes, is my number's loop less than or equal to 50 boxes?". If you find a loop of 50, you know it is, and you know everyone else's is too, because you can't have a loop of 50, and then a loop of 51 or more, if there are only 100 boxes.
5:55
As a mathematician and who loves ridles, until this point everything makes sense,
And i had kinda same idea when i saw first at this videos this ridle but i didnt make calculations like this. But this makes sense,
I havent watched till the end but i have one big math idea.
So if u are in a loop of 10 numbers it means all of them are safe like u, and the biggest save will be if u find the loop of 49 numbers, that makes the chances impossible to fail everyone, bcz each the bigger loop smaller than 50 guarantees that other loops may be smaller.
The biggest loop X, where X < =49 is the best loop in this riddle.
I also had the question "what if you're on the wrong loop" My reasoning is the last box in the loop must contain the same number as the first opened box due to the definition of the loop. Otherwise, if the "last box" contains a different numbered slip, it just means that it is not the last box, and the loop is longer.
So there are 2 possible outcomes after opening a box: a) it contains the prisoner's number and the loop is completed or b) it does not contain the prisoners number and they must repeat the steps for the next box until the loop is closed. And the loop has to close because there are a finite 100 boxes. If there is a single loop of 100 boxes each with a unique slip, after 99 boxes/slips, the 100th slip is guaranteed to have the number of the first box.
It was nice to revisit this riddle!
This is a good explanation and helped me understand it
Because its a loop, its impossible to be on the wrong loop as long as you don't screw up picking your boxes.
I
Aye sea
@@voidmayonnaise If the random arrangment has no more than 50 loops (31% chance by the video) then first prisoners has 100% chance to get it right. I disagree with Veritasium saying it's 50%. The probably already determined when the loop is set with this trick
exactly what @KahaiMitram said, if you're not on the right loop, it's not a loop. And, by the definition of the all unique numbers being "renumbered", it has to be a loop. The only question is, is the loop shorter than or equal to 50.
(edit)
the above is still valid, but nm to anything after that. My sleep addled brain did the math wrong. The unique permutation of a loop is (n-1)!, which is the same as n!/n, which, if n=100, is 100!/100.
The easiest way for me to understand this strategy is that when choosing boxes randomly, the prisoners as a group need to be lucky 100 times to win their freedom (each person basically come in with only 50/50 chances)
While with the loop strategy, the prisoners as a group only need to be lucky ONCE. That is because if the boxes arrangement doesn't produce a loop longer than 50, then they're all GUARANTEED to win. Therefore they only need to be lucky when the boxes were shuffled, and the probability of the arrangement they need come out of the shuffle is about 31%.
The interesting thing is that if you drop the number of prisoners to 2, the probability goes to 50% if you use this strategy, as opposed to 25% by choosing randomly. If both prisoners agree to pick either their own or the other's box, then both ensure that they don't accidentally pick the same box, meaning that if the correct number is in the box they chose, they both find it, while if the wrong number is in the box, neither of them finds it.
@@ocadioan Good observation, tbh I felt this to be more counterintuitive than with 100 prisoners before I read the second sentence :)
Where are you getting this 50/50 business. Remember the chances randomly had 31 zeros to the right of the decimal. That's stretching the definition of the word lucky a bit far.
@@mperhaps It's because only having 2 prioners is a completely different scenario than having 100. Doing the strategy will remove the 2 possible ways the 2 prioners can chose their 1 box that we know will always fail, i.e. both opening 1 or both opening 2. Out of the two remaining, alternatives, there is a 50% chance since either both pick the correct box (1->1, 2->2) or both pick the wrong one (1->2, 2->1).
> Therefore they only need to be lucky when the boxes were shuffled
Not exactly. Prisoners can be the masters of own destiny, by adding an arbitrary number to every box, and therefore create a new shuffe. 12:56
The reason I love Destin so much is because of his mindset at 2:27 - Instead of being boggled and/or arguing, hes completely open to just learning the facts of what was just told to him with his simple 'Teach me' - many people could learn from Destins attitude in today's day and age; probably one of the main reasons hes in my top 3 of favorite youtube channels!
I understand they're friends and Veritasium is trying to throw Destin some viewers but I wonder if they ever flip the script. Where Destin is trying to solve one of his own puzzles and calls Veritasium so that he's the one saying "Ya I don't know the answer."
The first time a friend told me this, my reaction was _"No, I don't believe you. You're obviously wrong. It's impossible that it's over 30%. That's ridiculous. You've made a mistake."_
A few minutes later and I'm eating my words.
Destin is awesome
I watched this long ago and now it makes way more sense. Really good video