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.

[@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.

[@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

[@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.

[@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.

[@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!

[@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!

[@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.

[@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]

😂

[@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!

[@Amazing-Charles]

Yo veritasium made a video about this lol

[@technicroblox]

cool

[@fuseblower8128]

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

[@WrathofMath]

I tried to dance my way around the jargon 😂

[@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