The Optimal Solution to an Impossible Problem

[@WrathofMath]

Join Wrath of Math to get exclusive videos, music, and more: kzbin.info/door/yEKvaxi8mt9FMc62MHcliwjoin More math chats: kzbin.info/aero/PLztBpqftvzxXQDmPmSOwXSU9vOHgty1RO For anyone wishing I'd have explained more why a permutation must be made up of cycles, consider the alternative. If 1 maps to 1 then that is a trivial 'cycle'. Otherwise, 1 maps to something else, say a. Then a maps to b, then b to c, and so on. The claim is that eventually some number in this sequence, say x, will map back to 1, thus forming a cycle. There is hardly any other possibility. Could it go on forever without looping back? No, because we have only finitely many numbers (1-100 in our case). Could it loop back to some other number in the sequence, like b, c, or d? Rather than 1? No, because - for examples - b maps to c, so x cannot. Also, a maps to b, so x cannot map to b. But nothing (as of yet) is mapped to 1, and so indeed x may map to 1. This is why the cycles are unavoidable.

[@godfreypigott]

That formula works only if L > 50. It doesn't affect the solution, but you made it sound as though it works for ALL values of L.

[@WrathofMath]

@@godfreypigott What formula?

[@godfreypigott]

@@WrathofMath What do you mean "what formula"? There was only one formula in your video that contained an L.

[@antonyisbwos]

What formula..? Remember that the goal is to find the chances that L < half the total prisoners and if L > half the total prisoners then they will not escape the death sentence @godfreypigott (I think)

[@godfreypigott]

@@antonyisbwos Let me say it again ... *THERE WAS ONLY ONE FORMULA IN THE VIDEO THAT CONTAINED AN L.* What do you mean "what formula"? Why is everyone here so obtuse? I know what the goal was. That doesn't change the fact that at no stage in deriving the result did he say "given that L>50".

[@samgordon9756]

You are a prisoner. The challenge before you is convincing 99 other prisoners from the population of regular prisoners to listen to you. What is the probability of having 99 other prisoners who can understand and believe this proof.

[@MATOMTU]

Probably less than just picking at random

[@WrathofMath]

Depends on your relationship with the prisoners, but I would think, facing such a ludicrous situation, the crowd may be likely to follow the suggestion a well-spoken leader who sounds like he knows what he's talking about. So perhaps it would come down to your presentation.

[@davidhall7275]

Getting 99 misfits to follow your instructions? Have you ever taught children?

[@mal2ksc]

@@WrathofMath Also you could easily prove picking randomly _won't work,_ and that you have a better idea -- and if nobody else comes up with a better plan, you're probably good. You don't have to prove your idea is optimal, just better than anyone else in that group can do. It's a bit like the joke "I don't have to outrun the bear, I just have to outrun _you."_

[@spitsmuis4772]

20:20 I would have added that ln(100)-ln(50)=ln(2), making the solution more or less independent of the amount of prisoners.

[@WrathofMath]

A great comment! I would have addressed that if I intended to discuss the problem as the number of prisoners increases, but I decided to leave it as it was.

[@GameJam230]

A smart (and evil) warden would just place the numbers in the drawers so it forms one massive circular chain. Every prisoner would get halfway around and never find their number, and the warden would sit and watch with a bag of popcorn as they struggle to claw their way to victory in a game rigged against them from the start.

[@dashyz3293]

While true, the premise indicates a random scramble.

[@GameJam230]

@dashyz3293 Yeah, a smart and evil warden WOULD want you to think that 😂

[@mal2ksc]

No, that game would end quickly. First person fails, game over. You want a 51-cycle to guarantee failure, but you also want to send in the 49 prisoners _not_ in the 51-cycle first to give the prisoners false hope. If the game isn't rigged, then having the first 49 prisoners exit the room alive would be an extremely good sign. Instead you set them up with false hope only to have it all come crashing down with the first prisoner you pick from the 51-cycle.

[@GameJam230]

@mal2ksc That assumes you end the game on the first failure, but it could instead be done so that none of them know the result of the game until AFTER they’ve all gone through, so they all have hope until they can’t find their number, then they’re sent into the next room where it ends all at once

[@punditgi]

Fascinating! Does the solution depend on a fixed permutation that does not change for any of the prisoners?

[@lincolnrimmer8615]

I can't prove it but I think it would not work nearly as well. The 30% is based on the largest cycle being less than it equal to 50, and if the permutation changes each time you would 'reroll' this chance every time. If the individual probabilities were made independent by each prisoner by rerolling the permutation, then (30/100)^50 is much less than (50/100)^50.

[@platinummyrr]

Yes. The strategy used here ties the prisoner success together. The best an individual can do is 50%, since they dont know where their number is, and it is randomly assigned. But by using this strategy, either they all fail or all succeed. This avoids the compounding effect of each prisoner trying randomly.

[@eirh]

Yes, if you change the permutation for each prisoner this no longer works. The strategy in the video relies on there being a pretty good chance that a random permutation has the "largest cycle size

[@WrathofMath]

Yup, good question and good replies!

[@IndyGibb]

Alas, Kevin from VSauce already taught me how to win.

[@vampire_catgirl]

Alas, Derek from Veritasium already taught me how to win.

[@psiphiorg]

@@vampire_catgirl Every math KZbinr eventually gets to this riddle. What makes it fun is each one's unique presentation of the riddle and explanation of the solution.

[@vampire_catgirl]

@@psiphiorg Very true

[@WrathofMath]

Yeah, I saw that some others had made videos on this problem; I decided not to watch them to not influence my presentation. Though perhaps I saw them several years ago or whenever they were uploaded. Regardless, hopefully my video can introduce this fun problem to some new people!

[@Intrebute]

So, I was thinking of a slight modification to the original problem. Suppose the warden is malicious and purposely picks a permutation with a cycle larger than 50. Obviously, in this new problem, this strategy always fails. What I want to know is if this new strategy would work. Before sending in the prisoners, the prisoners agree on generating a single completely random permutation and they all memorize it (call it R for random). Now, each prisoner, instead of following the permutation the warden prepared (call it M for malicious), they follow the permutation MR, would the strategy still work if they instead follow those directions on which drawer to open next?

[@ethos8863]

Everything else about this proof is incredibly believable. Loops longer than 50 being rare makes sense. There's just clearly many more permutations with loops shorter than half. In fact, I already knew of the optimal strategy off the top of my head. What isn't convincing is that the box showing the number must be part of the loop containing the number.

[@WrathofMath]

If not that loop, then which? If it's not in that loop, it can't actually be in a loop. Say I open box A, which contains number B; this directs me to box B, and so on. Will a box ever direct me to A? Well, if not, then the loop will never close and hence not be a loop. So certainly eventually a box will direct me to A, which is to say it will contain the number A.

[@ethos8863]

@@WrathofMath Ah, that makes sense and of course all loops must close because there's finitely many boxes. Thanks for the explanation

[@davidhall7275]

So a binomial is (100 L) . I figured that out when I was 12 or 13 but I didn't know what it was called. I was looking for ways to win at cards. Your explanation of this interesting problem is really good. Brings back memories.

[@qsquared8833]

1) Prisoner checks their number, if correct number, done 2) If wrong number open number of next prisoner,. 3) if right number swaps their number from their spot to the next prisoner's spot and takes thier number finishing 4) If wrong #, flips numbers of their number and next prisoner. 5) opens the number they just moved to their own number, and swaps the correct number into it's space and the resulting number to their own, then checking their own again to see if matched and they may end.

[@rogerkearns8094]

The key hiding in a chess board is a harder prisoner problem.

[@mal2ksc]

I always wonder what you're supposed to do in the following situation: the prisoners aren't numbered 1 to 100 but rather a number that was handed out by the order in which they arrived -- and some people have left the prison (by serving their term, or by dying) so there are numbers missing, and prisoner #1 is long gone. I suppose everyone could put their heads together and make their own list that ties every prisoner number to a number from 1 to 100, and when they open a drawer and find #83627 they have to look that up on their list to translate it back to a number from 1-100 to continue the cycle (unless they pick their own number of course). This would be mathematically equivalent, but in reality it would open up a whole lot more opportunities to screw up. Of course if I were the evil prison warden, I'd leave the rules exploitable... but I'd cheat and make sure the "random" arrangement in the drawers always contains a 51-cycle, and send in prisoners _not_ in the 51-cycle first, so that they can get almost halfway into a run before they fail. It's so much spicier when they think it's going to work, right up until it doesn't.

[@zinc_magnesium]

Me pulling out my abstract algebra textbook trying to explain cycle notation to my cell mate

[@WrathofMath]

😂

[@SilentSword22]

quick note just for correctness, the naive strategy is actually just a little bit better than 50% i believe. It should actually be 51%... this is calculated by finding the combined probability of failure (product of (1-1/(100-n)) with n = 0 and n < 50) and then using the prob of failure to find the prob of success.

[@MarieAnne.]

I believe it is indeed 1/2 The total number of ways to choose 50 boxes from 100 is (100 choose 50) = 100! / (50! * 50!) The number of ways to choose 50 boxes that contain your number is (1 choose 1) * (99 choose 49) = 99! / (49! * 50!) So probability of randomly choosing 50 boxes that contain your number = [99! / (49! * 50!)] / [100! / (50! * 50!)] = (99! * 50! * 50!) / (49! * 50! * 100!) = 50/100 = 1/2

[@jorgechavesfilho]

Great!

[@georgecarr9561]

But, even if there was an existing cycle of more than 50, would they really be guaranteed dead? Couldn't the prisoners, at vanishingly low odds mind you, happen to choose close to their number in the cycle? He'll technically they could each walk out and choose 1 drawer only right?

[@JavedAlam-ce4mu]

No, this isn't possible, because every prisoner chooses their own room number as the starting draw, there are no odds involved. This is because due to the fact that they each choose their room number as the first draw, each prisoner therefore has a unique sequence of draws that they will open, and this means that by definition there will always be one prisoner who will open the full cycle length of draws before finding their number. There aren't any odds involved, this is guaranteed to happen.

[@WrathofMath]

No, because there is no 'happen to choose' in the strategy. Prisoner A will open drawer A, and by definition the cycle will not be complete until he finds his number, and thus he will have to traverse the entire cycle, as will every prisoner along the cycle. Good question!

[@JavedAlam-ce4mu]

@@WrathofMath Woops, I didn't understand it properly. Thanks for the clarification! Seems obvious now when I draw it out.

[@cyanide7833]

This is a great explanation, i just don't see how u wud prove that this is the optimal solution and no other strategy cud get more than 31%

[@Amazing-Charles]

Yo veritasium made a video about this lol

[@fuseblower8128]

I didn't hear the term "bijection" even once. I'm so disappointed! 😉

[@WrathofMath]

I tried to dance my way around the jargon 😂

[@technicroblox]

cool

[@iblameomdeep]

Veritasium already taught this

[@WrathofMath]

oh, i guess nobody should ever speak of it again then

[@mementomori7160]

@@WrathofMath Tbh, my first thought was the same, but wtf, if someone big made a vid about something then suddenly no one else can? You did it your own way, and that's what matters. You did a good job!

[@lincolnrimmer8615]

10:54 "The prisoners would definitely die." This is wrong, the stated problem has them guess 50 times, so any competent prisoners would open every drawer and win. I get that it's meant to be half the number of boxes, but it was never expressly stated. The whole point of mathematics as football logic is not too leave ambiguity like this. I've seen this same oversight in every video on the topic that I've watched and it always annoys me.

[@lincolnrimmer8615]

Let's see what sort of dislike ratio I get on this ;)

[@godfreypigott]

@@lincolnrimmer8615 When was the last time you saw a dislike count on a comment?

[@WrathofMath]

I state explicitly, when beginning the discussion on permutations of 1-8, that the prisoners may open 4 drawers, half the total. This point of 'half' the total is repeated several other times in the video. 6:06