"The King can't do anything to ruin this startegy" *King proceeds to have them say all at once before they have any time to do mental math* Great puzzle, thanks!
Great job slowly giving hints. At the beginning of the video I felt lost as to what the winning strategy could possibly be, but by the last time you asked to pause I was able to figure out the solution myself. Despite this, I never felt like you gave away the answer!
Something that helped me clear things up, probably is more complicated than useful, but: Consider a case, the king gives everyone same hat, everyone calculates same initial sum and same remainder, but everyone thinks the final remainder (after adding their own hat) should be something different, so everybody gives an unique guess. Since every hat type was guessed, at least one, and exacty one prisoner must have said the correct type. Now the king is angry and does same thing again, but the winner gets a different hat, to see if he's cheating. The winner will give same guess as before, because from his perspective nothing changed - he won't win this time. But for everybody else the sum has changed, and the initial remainder too (there is no case where remainder stays the same, this would mean the new hat from king has same value - contradiction, or that it has same value mod 10 - again contradiction because there are only 10 values), so now everybody "shifts" their guess around the list of possible types, and again somebody must be correct (one person shifted to the correct type, the one that everyone had in the first attempt). Can the king do anything to stop this process? Maybe after enough "changes" this shifting makes nobody correct? Turns out no, this is hard to explain in a comment, but notice that at the start, not only everyone had an unique guess, but also their guess was uniquely far apart from correct answer, one of them was 0 apart (correct), somebody was 1 too far in the set of hats, somebody was 1 too far but to the other side etc... When king changes the hat of somebody (only one prisoner), it doesn't obstruct this property! because everybody's correctness shifts by (old hat value - new hat value) anyway. The 9 prisoners who saw the change adjust their answer, and the one who got his hat changed, well, just becomes wrong by that amount, so the circle isn't broken. This is kind of inductive proof that for any hat combination, the prisoners win, because at the start you can show their strategy works, and you can achieve any other combination by changing one hat after hat, and they can never lose like that.
Ooooooh this is really good. Proving it from a base case and showing how the win is invariant to any single change (and therefore any arrangement of hats) really helps drive the point home for me. The strategy is bulletproof against anything the king can do, because the prisoner's responses shift to accommodate the change. That shows the power of the strategy to adapt to the situation.
Hi why can't each prisoner decide to tell 0 1 2 3 4 5 6 7 8 9 one each person .thus whenever the king asks them to tell all prisoners will tell 10 distinct answers so one of then will be correct .
it requires a bit more modular arithmetic, but i think it's very compelling that in the final image at 12:20, you can see that, starting from prisoner 8, their guesses are exactly correct, 1 too high, 2 too high, 3 too high, all the way around to 9 too high
Nice observation. If a prisoner assumes that the total sum is X mod N, and in reality it is S mod N, then his answer will be off by exactly (S - X) mod N.
@@goingnull6028 thanks for this explanation, I think you should have put that in the video, the second I read this solution I had a click and understood the logic. All around though, an amazing video with a great riddle. Where did you hear about that riddle?
@@alonvinkler Thanks. Maybe I should have put this in the video explicitly. You never know which points will resound with people. I originally heard this problem from a coworker at Google but I'm not sure where he heard it. The analysis is my own. Also, חג שמח (almost).
Fantastic explanation of a classic math problem. The hints were a fantastic way of building up the intuitive understanding of why this works, as well as developing techniques to help with general problem solving. The visuals really supported the presentation, and the pacing was quite good to facilitate complete understanding of this problem to somebody who has never seen it before. Keep up the great work!
I'd heard of similar puzzles before but could never quite remember the answer to them, and the explanation of the solution wasn't always very convincing. But... (spoiler) ...tying this with the expression for the probability of a union and showing that it's all about removing any possible overlap was an eye opener for me. Really cool contribution!
This easily deserved to win. Came expecting a generic puzzle but eventually I realised this was a really solid video. Not only did I solve the puzzle, but I learnt important lessons about logic, problem-solving, and of course hats. Great job, congrats on $1,000
I've known this solution for a while, but I never really understood why it worked. But your explanation about removing the overlaps in the probability made it so clear!
before waching the solution, i tried solving on my own, but instead of direct modular arithematic, i instead used roots of unity. So you assign one of the 10th roots of unity to each prisoner & hat, and instead of adding numbers to get a desired remainder, we end up multiplying the values of other prisoners' hats together, and finally multiplying it with some chosen root to arrive at your assigned value. The strategy was really a shot in the dark, but i did end up writing a small program to test my results, going through each possible reality (i.e. hats on heads) and checking the answer obtained from the above algorithm . I went till N=9 before my system crashed, but it gave me enough confidence to finally move forward in the video and check the actual answer.
The path to the solution also becomes apparent when you consider expected value instead of just probability. The expected value of the number of correct prisoners must be 1, therefore for guaranteed success it must always equal exactly 1.
Yes. That's another good way of looking at it. What I really like about the probability approach is that it allows you to not even think about being correct at all - just guarantee there are no overlaps. This is of course true with the expected value as well but for me it felt a bit less obvious from that vantage point.
I finally solved it!!! I watched the beginning of this video a while back and stopped watching after hint #1. I was determined to solve it without watching further. I looked at things a different way then you did, but ultimately ended with the same result and concept. Probably my favorite riddle now, great vid!
I got it as soon as you put up the formula at 7:11!! Really cool puzzle and you explained it so well. And I especially approve of the use of emoji in equations :)
I absolutely love those equations. The biggest obstacle when one tries to understand a formula is the fact that one has to have the meaning of each symbol used in their "buffer" throughout. Using tangible pictures instead frees up suprisingly much mental capacity.
Its amazing what a common goal and set deadline can do when you witness it like this. SoME2 has let so many creators grow and so many amazing videos to be created, and this is no doubt one of them!
[spoilers below] we paused at 9:58 and the strategy came to us in a kind of burst of inspiration after staring at the numbers for a bit and were like "oh right!! modulus!!" that was such a satisfying aha moment, and this is the first time in a while we've both felt compelled to try to pause and ponder *and* actually managed to come up with an answer! thank you so much for sharing this
@@elizathegamer413 oh cool! yeah we've been watching a lot of summer of math exposition videos, there are a lot of really cool ones but this is one of our faves thus far
Loved it, huge congrats mate! Even though I could not figure it out for cases above 2, the video got me thinking deeply about the problem and the final solution is beautiful. One thing, which was not obvious to me, was the following: - Why does the prisoner who is assigned the correct mod 10 remainder for the sum (8 in your example), does always end up guessing the right number? - or stated in a different why - Why do all prisoners who are assigned incorrect mod 10 remainders for the sum (other than 8 in your example), do always end up guessing the wrong number? So I think the answer is: - each prisoner knows the partial sum (the total sum minus the last sum component, which is the number between 0-9 assigned to their own hat) - each prisoner assumes a specific, different mod 10 remainder for the total sum (and only 1 of them can correct, the other 9 must be incorrect) - for the incorrect prisoners -> their guess cannot be correct, because a correct guess would result in a sum equal to the total sum, which in turn means the same/correct remainder (contradiction) - for the correct prisoner -> the guess must be correct, because if it is incorrect, the sum would differ from the total sum. And if the sum differs, the remainder must differ/be incorrect, because the only sum component missing is between 0 and 9, the guess can only move the remainder up by min 0 or max 9, so there is no way to reach the same remainder with a different sum (contradiction)
wow that solution was really unexpected! this is probably me favourite some2 of the year :D great pace, easy to follow, you taught it really well and it was, frankly, an awesome riddle! easy sub from me, hope ya hit a 100 soon
Amazing video! You gove hints so well, guiding the viewer towards and answer without ever giving it away. I personally did not get the answer before you revealed it, but one you revealed it, it immediately clicked. You laid the foundations very well The parallela you drew to probably, and making the sets disjoint was so cool! I haven't seen anyone else draw that connection before 👏
That's a shame that you seem to be going to release a video only once per summer. The quality is amazing, you should consider creating this kind of content more regularly :)
Honestly incredibly video, and the comments reflect that, I think they were only two negative comments (which was just because they didn't listen to the problem). I especially liked how you built up to the problem, allowing and encouraging the viewer to make progress themselves before moving on. One of the best SoME2 videos I've watched so far, so really well done! :D
Please make more videos! These are really well made and throughly explained. And this is a very interesting puzzle too! After watching this I though for sure you had tons of subscribers and had been making videos for years. At first I was disappointed to learn this is only the second video on your channel. But I’m kind of excited to have discovered you so early!
I had a bit of a difficult time understanding why this strategy works, and came up with the following explanation for myself (maybe it'll helps someone else too). Never liked probabilities, for being random :), so here's probabilities-free explanation. The prisoners might as well assume the king is distributing hats non-randomly, and they need to come up with a strategy that covers *all* possible ways the king decides to distribute hats. In case of 2 prisoners, they can simply agree that one of them presumes hats are different and the other presumes hats are the same. So one of them calls the same hat as he sees on the other prisoner ("hats are same" presumption). The other calls the opposite type ("hats are different" presumption). There are no other possible ways hats can be arranged, so one of them has to be right, and so they win. In case of 10 prisoners, each one presumes a unique "mod 10" number and acts accordingly. There are no other possibilities to distributes hats, that produces "mod 10" outside of 0-9 range, so one of the prisoners will have to be right, and so they win.
The probabilistic intuition does not help explain why the strategy works. It just helps move towards the correct strategy by showing that you only need to guarantee that two prisoners cannot both be right.
I was watching 3Blue1Brown's recap video, and stopped at 4:17 to come try the challenge myself (and also leave this comment before your video inevitably reaches those hundreds of views 🤞📈 ) Despite doing quite well on other prisoner / hat puzzles, this one had me stumped ! I paused at the 2:07 bullet list, and did pretty much what you advised : Starting with only 2 prisoners & converting the types of hats to numbers. (And having the 0 & 1 made me think we might be going binary for the rest of the puzzle) 🤖 With the child version, I just thought of it as Logic Gates, and it worked the same as the 4 scenarios you described. But I had no idea how to go to 3 or more, and honestly just kept watching the video from there 😔 All in all, congratulations on the great video ! I will need a few rewatches if I am to hope to be able to present the problem to my friends & family, but you did a great job explaining everything in various ways ! 👍
Only points of constructive criticism : - Your voice & elocution are descent but future videos would benefit from a better microphone (understandbly expensive) 💸 - *My opinion only* (for extra "diversity points") : having all possible emojis to work with, and "struggling" to find 10 hats (even though everything is "head gear"), it was somewhat "bland" to see the final 5 🙋♂ all being the same (coming from a white dude). It could've worked really well with those (great) final lines of yours to have more variety, is what I'm hoping to get across. (even though those were great examples throughout the problem : No need to add unnecessary complexity with different prisoner emojis) [Also whoever might have read all of this, first of all thank you, but just in case, please don't start a flame war based _only_ on this personal opinion, or the exceptional use of emojis ; it was the theme after all] 🙏
3:00 I thought of starting with the simpler case but I went a completly different direction, I imagined a function with two inputs, the type of hat as the first input (0 or 1) and the position of the person (alsp 0 or 1, 0 being first and 1 being second). I then tried picking a fiction that would result in atleast one person being right in all 4 cases, so in the case of both people having the 0 hats, either f(0,0) = 0 (first person has the hat 0 and chooses 0) or f(0,1) = 0 (second person has the hat 0 and chooses 0) and I ended up with the function hat*position, which works for all 4 cases (but its not unique). I dont know the exact function for all the problem with 10 hats but giving the sheer number of them (20^10 maybe), theres probably atleast one that gives the desired outcome. Your solution is way more elegant tho 😅 That type of thinking of eliminating the conditional probabilities is very useful, I'll definetly try to use that in future problems!
Incredible visualisation and explanation of a complex question! By the end of the video, I felt not just that you had told me the answer, but that I understood the question, and could replicate the method in other scenarios! Amazing job, keep up the great work!
I’m so glad YT recommended this! I couldn’t believe it when I looked at your list of videos - that you’ve only made 2? I also expected a large sub count. I hope that, now you’ve made it back, you’ll start to make more content on a more frequent schedule :) Thanks for a great video!
I love a good complicated math solution, but as soon as you said the solution for 2 people I had a different solution that asks one person to "guess" theirs by telling the person to their right. Even if the king decides to go in a random order, I like to hope that person can remember long enough to guarantee everyone's release. But, as a failsafe, for every 2 more prisoners in the group, everyone is free once more.
I came up with a solution where just looking at others in a pattern can let them know the answer but now that i think about it , it is just another way of communication
I got a similar problem to this once where a classsroom of people get colored hats, and everytime a bell rings one particular color can be entirely right about which color they're wearing.
Great puzzle and great explanation and "solving tips" ! :) There is just two points I would have presented differently, maybe making it even clearer: - Instead of asking "what if the prisoners play randomly?", which is obviously a very bad strategy, I would have asked "what if the king plays randomly?", which is a very natural strategy for him, and also allows to start reasoning with probabilities (although you could as well count hat configurations leading to a win or a loose). - Instead of the argument with the inclusion/exclusion principle and the "overlap within the overlaps etc, which is a huge mess at 7.18" (which is indeed not the clearest part of the video), I would argue that with each prisoner having 10% chance of being right, the average number of prisoners being right is exactly 1. And if you have a random number which is 1 in average and want it to always be at least 1, the only possibility is that it is always exactly 1. What do you think ?
- If the king plays randomly, it doesn't lead me to think that the prisoners should play randomly. In fact, they shouldn't. I would still want to get the best strategy out of the prisoners. On the other hand, if the prisoners play randomly, there is nothing the king can do to thwart their plans other than play randomly himself and hope for the best. That forces us to analyze the full randomness strategy. - It's true that we can describe everything in terms of expected value. However, in my opinion, the probability description makes it much clearer that the prisoners only have to guarantee that not more than one is right. They don't even have to think about how to get one of themselves to be right. This was a wow factor I was trying to really hammer in the video.
Amazing video! the hints are great! and considering the problem from a probabilistic pov is brilliant! I had already solved this puzzle before I watched this video but I never thought about it that way. In other words great job!
Man I was so close. Immidiately converted to numbers, figured out solution for two and when trying to figure out for 3, realized each prisoner needed to cover 1/3 of the possible space. Had a feeling modulo would be involved in the solution but could not figure out the specifics. My problem was starting the video late at night so I was to tired to finish but would not be able to fall asleep if I didn't the solution 😢
Guess before watching: Assign a number to each hat. You use the fact that everyone knows the other 9 hats, and so can predict the total to within +-5. Everyone assumes the total is the other 9 hats + 5. You agree on an order for everyone to pick above or below somehow. Doesn’t quite work I think. Edit after watching: kind of close, didn’t think about the probability thing, that’s neat.
There's always that segment who have to be held back from trying to outsmart the problem with word games in order to avoid solving it, but at the same time still give themselves credit for their shrewdness.
What if their strategy is that first prisoner will speak out the hat type he sees at least one other person wearing, then everyone will also say the same hat type. So at least one of them will definitely get it right
Only thing that took me a while to get is that I thought the problem was set up in a way they could not see the available hat types before communicating with each other, and thus could never create asystem that paired them to numbers that everyone was guaranteed to agree on. Not even sure if there are solutions with this extra constraint,but sounss potentially fun
They must see the hat types first, as explained at 0:15 and 1:40. If they can't, there's no strategy but to guess randomly from amongst the hats that they see. Then the king can guarantee that they lose just by giving each one a different type of hat, and they wouldn't even know that the hat type on their own head exists.
I was stuck on this for a bit as well (glad I'm not the only one :)). But it doesn't really matter if they can strategize after seeing the hats or not. They can simply agree beforehand that the first hat they show us will be number 0, second one is 1, and so forth.
@@goingnull6028 It seemed in the description of the puzzle (due to the no talking after hats are shown, instead of after the blindfold was removed) that there was a deliberate attempt to prevent a common numbering system between prisoners. If the prisoners don't use the same numbering system for the hats, i don't think the presented solution would work. Was it implied that the prisoners could set a system up where they could get a common numbering system (like hats placed in a row, or revealed in order)? Or am I missing something in the solution that would work even if the numbering systems of the prisoners differed?
@@rellen22 The prisoners are first shown all ten types, then told all the rules, and then allowed to strategize until all the repeated hats arrive. This is what I tried to convey in both the loose description of the problem and the slightly more formal recap, but it seems I left plenty of room for misunderstanding. Sorry.
I think another interesting observation that comes from this solution is that the sum of n randomly picked numbers in the range [1,n] is uniformly distributed mod n. It makes sense if you think about it, but still a pretty cool result nonetheless
I am super glad you pointed this out! I realized this only after publishing the video. This puzzle is itself a proof that the sum of N numbers in 0...N-1 is evenly distributed mod N, because if not, it would imply that a prisoner could somehow get information about his own hat from looking at the other hats, which is absurd, so we have a proof by contradiction. I've never seen this kind of proof before, where some presumption implies an absurd information leak, so therefore the presumption must be false. Very interesting. Side note: Here is another way to prove that the sum of any amount of numbers in 0...N-1 is evenly distributed mod N. The sum mod N of one number is just that number, so the even distribution is trivially true. Assume that the sum mod N of k numbers is evenly distributed. For k+1 numbers, choose any k numbers, and by our assumption their sum mod N is evenly distributed. For each of those sums, add all possible values of the remaining 1 number, and observe that the sum mod N remains evenly distributed. QED
I have seen similar, slightly easier problem before. 100 prisoners will be given each either a pink or a blue hat. This time however, every single one of them will need to be right to be let go. Any mistake makes them all lose. Which strategy will give them the highest probability of winning?
I'm guessing they assign blue and pink 0 and 1 (or vice versa) and all assume overall mod 0 or overall mod 1, so the overall chance is 1/2. Nice variation.
When i choose to calculate the chance of success directly, i tend to do it by calculating the probability of success for one person. Then i take the probability the first person failed and multiply it by the probability the second person got it right. Then i add them together. Then i take the probability the first two failed and multiply it by the probability the third person succeeded. And etc This isn’t as fast as the proper method that you used. But it’s faster and simpler than the alternate methods you mentioned. And it feels like it gives a more intuitive way of thinking about it.
This is indeed a valid alternate method. When I mentioned alternate methods, I was trying to lead into the worst method, directly handling the overlaps, so that I could encourage the viewer to see that the overlaps must be non-existent for there to be a possible solution. Before that, I said that we could try any alternate methods where we add up the probabilities of disjoint scenarios, which would include yours. The specific example I gave was 1 correct, or 2 correct, or 3 correct, etc... simply because it's easy to describe and illustrate. I could have added more but decided that it wasn't really central to the point I was trying to make.
I am very proud to say that I've found a solution for the original problem after the first hint! Edit: My solution was the same as in the video, but I didn't think about probability at all. I just imagined the hats as numbers painted on their forehead, and from there it wasn't too hard to add them up
pausing to find a solution (spoilers) what if we assign each hat a number 0-N and each prisoner a number 0-N Each prisoner will pick the hat that, when summed modulo N with the other hats, produces their number. Since the prisoners cover every number, whichever sum happens to be correct will automatically make said prisoner correct.
2:28 This hint, was so helpful, and I recommend that everyone go down to two hats, then try 3. I was able then to get the solution, and it's really clever
I solved it like this, Each prisoner is assigned a unique number from 0 to 9. Each prisoner looks at the prisoner to the left. Then sees the number say x (associated with the hat). Then the prisoner says x+ his/her number . In that case also, we guarantee that there is no overlap and atleast one of them gets it correct. I think that's the best thing about this puzzle. You can think of a lot of different non-overlapping puzzles and all of them will work.
Your proposed solution does not work for more than two prisoners/hats. For two prisoners/hats, it's completely equivalent to the solution in the video. The one who is assigned 0 is effectively assuming his hat is the same as the other and the one who is assigned 1 is effectively assuming his hat is opposite the other. For three prisoners, this strategy can be broken, for example, with prisoners assigned 0, 1, 2 having hats 2, 1, 2 respectively. In general, there is nothing in this strategy that guarantees that two prisoners can't be right simultaneously, so by the principles shown in the video, there will always be scenarios where this fails for more than two prisoners/hats.
@@goingnull6028 Ok, I went back to my proof, I basically proved for 010 , and 0,1,2 and it worked. So I just assumed that by symmetry, it will work for all combinations of form ABA. But doesn't work for 212. But symmetry holds, so a different orientation of numbers will work for 212 too, but problem will be the prisoners will not have a way to track those changes. Cool. Understood my mistake. Will try to find some different method then. 👍
Cool. I know of different solutions for cases where the number of prisoners/hats is composite, but not for when it's prime. If you find an alternate strategy for three prisoners I would be really curious to know.
After hearing the riddle and noting the restrictions imposed, I couldn't help attempting a fairly math-free solution. So I tried coming up with a strategy where the individuals would decide to close their eyes or keep them open based on the number of duplicate hats they see, with predetermined answers given by those who kept their eyes open for various scenarios of observed closed/open eye ratios. But I couldn't find a way to guarantee that someone would be correct in the event of multiple sets of duplicate hats without involving something more complicated like having the individuals open their eyes a second time, or instead having them only close one eye upon first inspection. Unfortunately, while they might get away with keeping their eyes closed, I couldn't get around the fact that taking blink/wink actions based on the blink/wink actions of others would definitely be considered nonverbal communication by the king. Having finished watching the video, I realize that my attempted solution was not in the spirit of the riddle. Still I recognize that there are never too many ways to view a problem, so I figured I'd at least share my musings. That aside, I thoroughly enjoyed the genuine solution presented. I found the problem-solving methodology, along with the generalizations that followed, to be laid out in an intuitive manner. Thank you for making and sharing such elegant yet thought-provoking content!
Nice puzzle! IMHO the rules of the puzzle would have been easier to explain (and the puzzle would be essentially the same) if it was about identical tall hats having a random integer from 0 to 9 on them. Perhaps it's a bit easier as you don't need the mapping back and forth, but the math needed is the same...
The thing I always remember that allowed me to solve this is that you need to make the win condition subject to the arrangement as a whole, and I knew that there were effectively 10 chances to get it right, so in this case I was asking myself what property of the whole system is going to give me 10 cases, and once I considered that I immediately thought of the sum mod 10, from there it’s relatively easy to see that each person can determine what their hat must be under their assumption and so one must be right. Even though the win condition is opposite it’s like the puzzle where there are a bunch of numbers in boxes and to escape everyone must open the box with their number (given a certain number of tries), where you maximise the chance by making winning conditional on a property of the arrangement of the numbers.
I'm glad someone brought up the numbers in boxes riddle! That riddle is kind of the inverse of this one. In that riddle, every prisoner has a 50% chance no matter what, but their strategy is to *maximize* the overlaps so that they all win together or all lose together. That's because they have to all be correct in order to succeed.
So you have 10 guesses, as we can see the other hats we can assume everyone guesses the whole setup rather than just their own hat. Among those 10 guesses must be the correct setup. So ideally, we split all 10¹⁰ possibilities into 10 categories, and assign each prisoner one of those categories to cover, in order to maximize chances. We should also ensure that whatever the prisoner sees, there should be one and preferably only one matching example in their category. This reminded me of error correcting codes, so how about we make every prisoner ensure that the sum of all types in their guess matches the prisoner's own number by the last digit (ie mod 10). Clearly that's always possible in exactly one way for each prisoner. Now the sum of types in the correct answer must have a last digit, and there is a prisoner assigned to that digit, so that prisoner will be correct.
This might be a stupid question, but why can't you just assign each prisoner one hat type and have them each call that out no matter what they see? That way all 10 possibilities are covered and someone's guaranteed to be right.
First of all, I applaud you for asking. Someone who is shy to ask cannot learn. I think the confusion here is around different types of possibilities. There are indeed 10 different possibilities for *each individual prisoner*. However, each individual prisoner gets to express exactly one of those 10 possibilities for himself. There is no way a prisoner can ever cover all 10 possibilities of what he himself is wearing. So, for example, let's say there are just two prisoners and black/white hats. Just because one prisoner says white and one says black doesn't mean anything. They could both be right, both be wrong, or a combo. That's because prisoner 1 expressed only one of his two possibilities and prisoner 2 expressed only one of his two possibilities. To solve the puzzle, we have to break the *entire system* into N different possibilities. So for example, when there are two prisoners, we say that either the system has two of the same hat or two opposite hats. In the case of 10, we sum the hats in the system, and say that the *global sum* has 10 possibilities. Then we have each prisoner express one of the 10 possibilities for the system, not for himself. That way we leverage the 10 prisoners to cover 10 different possibilities that pertain to the system as a whole, rather than to himself as an individual. Hopefully this clears things up, but happy to try an alternative explanation if this is still confusing.
@@goingnull6028 at 0:37 there are multiple people with same hat, which makes the strategy "everybody guesses the same hat type" fail. But at the end of the video, when you start using numbers instead of hats, there's an assumption that each hat is given out only once, or that there is a permutation of 10 distinct hats. Can the final strategy work with the hat assignment from 0:37 ?
@@goingnull6028 The distinction between "local" and "global" possibilities reeallly seemed to confuse me. As soon as you pointed it out, it made so much sense. Thank you so much for this explanation! And thank you for asking that question!
Am I wrong to think that the prisoners can just agree to say one hat type they see and then just keep saying the same hat? For instance, in the two person scenario if the first person says "top hat" because he sees that on the other person, the other person can assume the hat on his head is a top hat. This also works for ten people because if the first person picks one of the prisoners and says that type of hat, every prisoner knows at least one person has that type of hat. It might be that no one has that hat type except the one the first prisoner picked, but if everyone sticks to the same answer then at least that one will get it right.
Without seeing the solution yet. Just extending on the simpler problem (of 2 people, which I figured myself using a big table). Possible spoiler: There are N prisoners, let's number them from 0 to N-1. And N hats, also numbering them from 0 to N-1. Assuming we know all the prisoner's hats, summing their values modulo N gives some number from 0 to N-1. Now, each prisoner will be targeting a certain sum, equal to his number (so e.g. prisoner 3 will target the modulo sum to be 3). But no prisoner knows all hats. So every prisoner will guess a hat such that, when the modulo sum is performed, it is equal to their prisoner number. E.g., for N=10, prisoner 3 is summing all other prisoner's numbers, gets 37, so he guesses hat number 6, so that the sum would be 3 modulo 10. And the sum has to be exactly one of these numbers, so exactly one of the prisoners will be right in what the sum is, therefore also right in their own hat.
"The King can't do anything to ruin this startegy"
*King proceeds to have them say all at once before they have any time to do mental math*
Great puzzle, thanks!
Great job slowly giving hints. At the beginning of the video I felt lost as to what the winning strategy could possibly be, but by the last time you asked to pause I was able to figure out the solution myself. Despite this, I never felt like you gave away the answer!
Almost same
Something that helped me clear things up, probably is more complicated than useful, but:
Consider a case, the king gives everyone same hat, everyone calculates same initial sum and same remainder, but everyone thinks the final remainder (after adding their own hat) should be something different, so everybody gives an unique guess. Since every hat type was guessed, at least one, and exacty one prisoner must have said the correct type.
Now the king is angry and does same thing again, but the winner gets a different hat, to see if he's cheating. The winner will give same guess as before, because from his perspective nothing changed - he won't win this time. But for everybody else the sum has changed, and the initial remainder too (there is no case where remainder stays the same, this would mean the new hat from king has same value - contradiction, or that it has same value mod 10 - again contradiction because there are only 10 values), so now everybody "shifts" their guess around the list of possible types, and again somebody must be correct (one person shifted to the correct type, the one that everyone had in the first attempt).
Can the king do anything to stop this process? Maybe after enough "changes" this shifting makes nobody correct? Turns out no, this is hard to explain in a comment, but notice that at the start, not only everyone had an unique guess, but also their guess was uniquely far apart from correct answer, one of them was 0 apart (correct), somebody was 1 too far in the set of hats, somebody was 1 too far but to the other side etc... When king changes the hat of somebody (only one prisoner), it doesn't obstruct this property! because everybody's correctness shifts by (old hat value - new hat value) anyway. The 9 prisoners who saw the change adjust their answer, and the one who got his hat changed, well, just becomes wrong by that amount, so the circle isn't broken.
This is kind of inductive proof that for any hat combination, the prisoners win, because at the start you can show their strategy works, and you can achieve any other combination by changing one hat after hat, and they can never lose like that.
Ooooooh this is really good. Proving it from a base case and showing how the win is invariant to any single change (and therefore any arrangement of hats) really helps drive the point home for me. The strategy is bulletproof against anything the king can do, because the prisoner's responses shift to accommodate the change. That shows the power of the strategy to adapt to the situation.
Hi why can't each prisoner decide to tell 0 1 2 3 4 5 6 7 8 9 one each person .thus whenever the king asks them to tell all prisoners will tell 10 distinct answers so one of then will be correct .
it requires a bit more modular arithmetic, but i think it's very compelling that in the final image at 12:20, you can see that, starting from prisoner 8, their guesses are exactly correct, 1 too high, 2 too high, 3 too high, all the way around to 9 too high
Nice observation. If a prisoner assumes that the total sum is X mod N, and in reality it is S mod N, then his answer will be off by exactly (S - X) mod N.
@@goingnull6028 thanks for this explanation, I think you should have put that in the video, the second I read this solution I had a click and understood the logic.
All around though, an amazing video with a great riddle. Where did you hear about that riddle?
@@alonvinkler Thanks. Maybe I should have put this in the video explicitly. You never know which points will resound with people.
I originally heard this problem from a coworker at Google but I'm not sure where he heard it. The analysis is my own.
Also, חג שמח (almost).
This is the best puzzle I've seen since Stand-up Maths's 'almost impossible' chessboard puzzle.
Fantastic explanation of a classic math problem. The hints were a fantastic way of building up the intuitive understanding of why this works, as well as developing techniques to help with general problem solving. The visuals really supported the presentation, and the pacing was quite good to facilitate complete understanding of this problem to somebody who has never seen it before. Keep up the great work!
I'd heard of similar puzzles before but could never quite remember the answer to them, and the explanation of the solution wasn't always very convincing. But...
(spoiler)
...tying this with the expression for the probability of a union and showing that it's all about removing any possible overlap was an eye opener for me. Really cool contribution!
i think this may have been my favorite video in soME2 !!!!
thank you so much for showcasing this problem, it was an amazing watch :)
This easily deserved to win. Came expecting a generic puzzle but eventually I realised this was a really solid video. Not only did I solve the puzzle, but I learnt important lessons about logic, problem-solving, and of course hats. Great job, congrats on $1,000
Brilliantly explained! The frame at 7:40 captures the beauty of this problem very well, and your ensuing visuals did the explanation justice. :)
I've known this solution for a while, but I never really understood why it worked. But your explanation about removing the overlaps in the probability made it so clear!
before waching the solution, i tried solving on my own, but instead of direct modular arithematic, i instead used roots of unity.
So you assign one of the 10th roots of unity to each prisoner & hat, and instead of adding numbers to get a desired remainder, we end up multiplying the values of other prisoners' hats together, and finally multiplying it with some chosen root to arrive at your assigned value.
The strategy was really a shot in the dark, but i did end up writing a small program to test my results, going through each possible reality (i.e. hats on heads) and checking the answer obtained from the above algorithm . I went till N=9 before my system crashed, but it gave me enough confidence to finally move forward in the video and check the actual answer.
Well done. Modular addition, roots of unity, or any cyclic group are all isomorphic and will work the same way for this puzzle.
As the story goes, this is the puzzle you get when applying to Mann Co.
Omg, this is one of those problems that seems literally impossible but once you know the solution it seems so obvious. Amazing solution
Loved the puzzle, loved the walkthrough, loved the Russian accent leaking through at some parts, and the moral of the story at the end.
Very well presented and edited. You deserved to win SoME2
Beautiful! Every step was quite hard to figure out but absolutly clear in hindsight. The best kind of puzzle.
The path to the solution also becomes apparent when you consider expected value instead of just probability. The expected value of the number of correct prisoners must be 1, therefore for guaranteed success it must always equal exactly 1.
Yes. That's another good way of looking at it. What I really like about the probability approach is that it allows you to not even think about being correct at all - just guarantee there are no overlaps. This is of course true with the expected value as well but for me it felt a bit less obvious from that vantage point.
This comment reminds me of this video ruclips.net/video/_le31Xhk9Eg/видео.html
I finally solved it!!!
I watched the beginning of this video a while back and stopped watching after hint #1. I was determined to solve it without watching further.
I looked at things a different way then you did, but ultimately ended with the same result and concept.
Probably my favorite riddle now, great vid!
I got it as soon as you put up the formula at 7:11!! Really cool puzzle and you explained it so well. And I especially approve of the use of emoji in equations :)
Grats on winning SoME2! This was a really cool video!
what a wholesome ending and a wonderfully explained video! thanks for your submission!
I absolutely love those equations. The biggest obstacle when one tries to understand a formula is the fact that one has to have the meaning of each symbol used in their "buffer" throughout. Using tangible pictures instead frees up suprisingly much mental capacity.
I have known this riddle for 10+ years now and I finally solved it (2 minutes into the video, so without any spoilers). Such a relief.
Its amazing what a common goal and set deadline can do when you witness it like this. SoME2 has let so many creators grow and so many amazing videos to be created, and this is no doubt one of them!
SoME2 judges were right, this video IS really good!
[spoilers below]
we paused at 9:58 and the strategy came to us in a kind of burst of inspiration after staring at the numbers for a bit and were like "oh right!! modulus!!"
that was such a satisfying aha moment, and this is the first time in a while we've both felt compelled to try to pause and ponder *and* actually managed to come up with an answer! thank you so much for sharing this
holy fuck i think i saw you guys on twitter like. a long time ago. that's so cool to randomly run into yall here!!
@@elizathegamer413 oh cool! yeah we've been watching a lot of summer of math exposition videos, there are a lot of really cool ones but this is one of our faves thus far
@@SunroseStudios thats awesome!!! im glad you're enjoying em! weve been enjoying them a lot too!!
btw we are also plural so like 🤝
@@elizathegamer413 heck yeah! we're still on twitter btw, it's linked on our channel if you wanna follow us or something lol
Loved it, huge congrats mate!
Even though I could not figure it out for cases above 2, the video got me thinking deeply about the problem and the final solution is beautiful.
One thing, which was not obvious to me, was the following:
- Why does the prisoner who is assigned the correct mod 10 remainder for the sum (8 in your example), does always end up guessing the right number?
- or stated in a different why
- Why do all prisoners who are assigned incorrect mod 10 remainders for the sum (other than 8 in your example), do always end up guessing the wrong number?
So I think the answer is:
- each prisoner knows the partial sum (the total sum minus the last sum component, which is the number between 0-9 assigned to their own hat)
- each prisoner assumes a specific, different mod 10 remainder for the total sum (and only 1 of them can correct, the other 9 must be incorrect)
- for the incorrect prisoners -> their guess cannot be correct, because a correct guess would result in a sum equal to the total sum, which in turn means the same/correct remainder (contradiction)
- for the correct prisoner -> the guess must be correct, because if it is incorrect, the sum would differ from the total sum. And if the sum differs, the remainder must differ/be incorrect, because the only sum component missing is between 0 and 9, the guess can only move the remainder up by min 0 or max 9, so there is no way to reach the same remainder with a different sum (contradiction)
Yeah. I think you got it.
Holy cow I loved that solution, very simple visuals and great explanations !
wow that solution was really unexpected! this is probably me favourite some2 of the year :D great pace, easy to follow, you taught it really well and it was, frankly, an awesome riddle! easy sub from me, hope ya hit a 100 soon
Some2 ?????
@@ashwynn4177 summer of math exposition, s.o.m.e
@@WoolyCow Thanks wooly...Thooly
Great video! The look at probabilities and the events needing to be mutually exclusive really helps lead the viewer to the answer
The second you said it could be guaranteed i had modular 'parity' in mind
Amazing video! You gove hints so well, guiding the viewer towards and answer without ever giving it away. I personally did not get the answer before you revealed it, but one you revealed it, it immediately clicked. You laid the foundations very well
The parallela you drew to probably, and making the sets disjoint was so cool! I haven't seen anyone else draw that connection before 👏
Great video, saw a reel about this and really wanted an answer to how it worked. And you explained it really well! :)
extra points (from me, not the jury haha) for including probability into this even though there was never a connection to it
That's a shame that you seem to be going to release a video only once per summer. The quality is amazing, you should consider creating this kind of content more regularly :)
Honestly incredibly video, and the comments reflect that, I think they were only two negative comments (which was just because they didn't listen to the problem). I especially liked how you built up to the problem, allowing and encouraging the viewer to make progress themselves before moving on. One of the best SoME2 videos I've watched so far, so really well done! :D
What were the two negative comments? Just curious.
Congrats🎉
This is absolutely splendid. I love these kinds of puzzles!
"The prisoners can guarantee, GUARANTEE, that they can get out."
I dunno, I they really were that smart they wouldn't be in prison
Maybe the last time the king was bored, he decided to arrest all his math professors.
I really loved this video! The emoji style was surprisingly enjoyable to watch!
This is the best piece of mathlike content I've seen in a while. Thanks for the effort, I hope you'll continue to make videos like that!
Please make more videos! These are really well made and throughly explained. And this is a very interesting puzzle too!
After watching this I though for sure you had tons of subscribers and had been making videos for years. At first I was disappointed to learn this is only the second video on your channel. But I’m kind of excited to have discovered you so early!
I had a bit of a difficult time understanding why this strategy works, and came up with the following explanation for myself (maybe it'll helps someone else too). Never liked probabilities, for being random :), so here's probabilities-free explanation.
The prisoners might as well assume the king is distributing hats non-randomly, and they need to come up with a strategy that covers *all* possible ways the king decides to distribute hats.
In case of 2 prisoners, they can simply agree that one of them presumes hats are different and the other presumes hats are the same. So one of them calls the same hat as he sees on the other prisoner ("hats are same" presumption). The other calls the opposite type ("hats are different" presumption). There are no other possible ways hats can be arranged, so one of them has to be right, and so they win.
In case of 10 prisoners, each one presumes a unique "mod 10" number and acts accordingly. There are no other possibilities to distributes hats, that produces "mod 10" outside of 0-9 range, so one of the prisoners will have to be right, and so they win.
The probabilistic intuition does not help explain why the strategy works. It just helps move towards the correct strategy by showing that you only need to guarantee that two prisoners cannot both be right.
I was watching 3Blue1Brown's recap video, and stopped at 4:17 to come try the challenge myself (and also leave this comment before your video inevitably reaches those hundreds of views 🤞📈 )
Despite doing quite well on other prisoner / hat puzzles, this one had me stumped !
I paused at the 2:07 bullet list, and did pretty much what you advised : Starting with only 2 prisoners & converting the types of hats to numbers. (And having the 0 & 1 made me think we might be going binary for the rest of the puzzle) 🤖
With the child version, I just thought of it as Logic Gates, and it worked the same as the 4 scenarios you described. But I had no idea how to go to 3 or more, and honestly just kept watching the video from there 😔
All in all, congratulations on the great video ! I will need a few rewatches if I am to hope to be able to present the problem to my friends & family, but you did a great job explaining everything in various ways ! 👍
Only points of constructive criticism :
- Your voice & elocution are descent but future videos would benefit from a better microphone (understandbly expensive) 💸
- *My opinion only* (for extra "diversity points") : having all possible emojis to work with, and "struggling" to find 10 hats (even though everything is "head gear"), it was somewhat "bland" to see the final 5 🙋♂ all being the same (coming from a white dude).
It could've worked really well with those (great) final lines of yours to have more variety, is what I'm hoping to get across. (even though those were great examples throughout the problem : No need to add unnecessary complexity with different prisoner emojis)
[Also whoever might have read all of this, first of all thank you, but just in case, please don't start a flame war based _only_ on this personal opinion, or the exceptional use of emojis ; it was the theme after all] 🙏
3:00 I thought of starting with the simpler case but I went a completly different direction, I imagined a function with two inputs, the type of hat as the first input (0 or 1) and the position of the person (alsp 0 or 1, 0 being first and 1 being second). I then tried picking a fiction that would result in atleast one person being right in all 4 cases, so in the case of both people having the 0 hats, either f(0,0) = 0 (first person has the hat 0 and chooses 0) or f(0,1) = 0 (second person has the hat 0 and chooses 0) and I ended up with the function hat*position, which works for all 4 cases (but its not unique). I dont know the exact function for all the problem with 10 hats but giving the sheer number of them (20^10 maybe), theres probably atleast one that gives the desired outcome. Your solution is way more elegant tho 😅 That type of thinking of eliminating the conditional probabilities is very useful, I'll definetly try to use that in future problems!
Incredible visualisation and explanation of a complex question! By the end of the video, I felt not just that you had told me the answer, but that I understood the question, and could replicate the method in other scenarios! Amazing job, keep up the great work!
I’m so glad YT recommended this! I couldn’t believe it when I looked at your list of videos - that you’ve only made 2? I also expected a large sub count. I hope that, now you’ve made it back, you’ll start to make more content on a more frequent schedule :) Thanks for a great video!
I don't know what to say but I still want to add a comment to express how good this was
Dang, was just about to be executed with my homies, but this video saved us. Thanks bro.
Really nice take, and congrats on your prize!!!
loved the inspiring message at the end! 🙌
The video is simple yet wonderful, nice submission for SOME2. The only thing that missing is outro/intro music
I love a good complicated math solution, but as soon as you said the solution for 2 people I had a different solution that asks one person to "guess" theirs by telling the person to their right. Even if the king decides to go in a random order, I like to hope that person can remember long enough to guarantee everyone's release. But, as a failsafe, for every 2 more prisoners in the group, everyone is free once more.
See the requirements again. The prisoners have to say their answers all at once so there is no way they can communicate.
I came up with a solution where just looking at others in a pattern can let them know the answer but now that i think about it , it is just another way of communication
I got a similar problem to this once where a classsroom of people get colored hats, and everytime a bell rings one particular color can be entirely right about which color they're wearing.
Great puzzle and great explanation and "solving tips" ! :)
There is just two points I would have presented differently, maybe making it even clearer:
- Instead of asking "what if the prisoners play randomly?", which is obviously a very bad strategy, I would have asked "what if the king plays randomly?", which is a very natural strategy for him, and also allows to start reasoning with probabilities (although you could as well count hat configurations leading to a win or a loose).
- Instead of the argument with the inclusion/exclusion principle and the "overlap within the overlaps etc, which is a huge mess at 7.18" (which is indeed not the clearest part of the video), I would argue that with each prisoner having 10% chance of being right, the average number of prisoners being right is exactly 1. And if you have a random number which is 1 in average and want it to always be at least 1, the only possibility is that it is always exactly 1.
What do you think ?
- If the king plays randomly, it doesn't lead me to think that the prisoners should play randomly. In fact, they shouldn't. I would still want to get the best strategy out of the prisoners. On the other hand, if the prisoners play randomly, there is nothing the king can do to thwart their plans other than play randomly himself and hope for the best. That forces us to analyze the full randomness strategy.
- It's true that we can describe everything in terms of expected value. However, in my opinion, the probability description makes it much clearer that the prisoners only have to guarantee that not more than one is right. They don't even have to think about how to get one of themselves to be right. This was a wow factor I was trying to really hammer in the video.
I figured this out in about 1 minute. I have to admit that I *may* be influenced by other puzzles of the same kind that I have solved before.
Amazing video! the hints are great! and considering the problem from a probabilistic pov is brilliant! I had already solved this puzzle before I watched this video but I never thought about it that way. In other words great job!
If 3blue1brown didn't explicitely say what this video is about, I'd never check it!
EDIT: OMG this is so good, thank you!
LOL!!! - I was on the right way but guessed it wrong! THX what a great video!
What a great video and riddle; I always love how satisfying these kind of riddles are.
Wow, loved this video! Please keep posting!
Congrats for the $1,000!
Man I was so close. Immidiately converted to numbers, figured out solution for two and when trying to figure out for 3, realized each prisoner needed to cover 1/3 of the possible space. Had a feeling modulo would be involved in the solution but could not figure out the specifics. My problem was starting the video late at night so I was to tired to finish but would not be able to fall asleep if I didn't the solution 😢
I feel like this guy took the problem and tried to make it simpler, but just made it harder
Guess before watching: Assign a number to each hat. You use the fact that everyone knows the other 9 hats, and so can predict the total to within +-5. Everyone assumes the total is the other 9 hats + 5. You agree on an order for everyone to pick above or below somehow. Doesn’t quite work I think.
Edit after watching: kind of close, didn’t think about the probability thing, that’s neat.
There's always that segment who have to be held back from trying to outsmart the problem with word games in order to avoid solving it, but at the same time still give themselves credit for their shrewdness.
Have seen the puzzle b4 . But now I know the logic behind it
What if their strategy is that first prisoner will speak out the hat type he sees at least one other person wearing, then everyone will also say the same hat type. So at least one of them will definitely get it right
They must all answer at once. See the conditions at the beginning of the video.
Only thing that took me a while to get is that I thought the problem was set up in a way they could not see the available hat types before communicating with each other, and thus could never create asystem that paired them to numbers that everyone was guaranteed to agree on. Not even sure if there are solutions with this extra constraint,but sounss potentially fun
They must see the hat types first, as explained at 0:15 and 1:40. If they can't, there's no strategy but to guess randomly from amongst the hats that they see. Then the king can guarantee that they lose just by giving each one a different type of hat, and they wouldn't even know that the hat type on their own head exists.
I was stuck on this for a bit as well (glad I'm not the only one :)). But it doesn't really matter if they can strategize after seeing the hats or not. They can simply agree beforehand that the first hat they show us will be number 0, second one is 1, and so forth.
@@goingnull6028 It seemed in the description of the puzzle (due to the no talking after hats are shown, instead of after the blindfold was removed) that there was a deliberate attempt to prevent a common numbering system between prisoners. If the prisoners don't use the same numbering system for the hats, i don't think the presented solution would work. Was it implied that the prisoners could set a system up where they could get a common numbering system (like hats placed in a row, or revealed in order)? Or am I missing something in the solution that would work even if the numbering systems of the prisoners differed?
@@rellen22 The prisoners are first shown all ten types, then told all the rules, and then allowed to strategize until all the repeated hats arrive. This is what I tried to convey in both the loose description of the problem and the slightly more formal recap, but it seems I left plenty of room for misunderstanding. Sorry.
I think another interesting observation that comes from this solution is that the sum of n randomly picked numbers in the range [1,n] is uniformly distributed mod n. It makes sense if you think about it, but still a pretty cool result nonetheless
I am super glad you pointed this out! I realized this only after publishing the video. This puzzle is itself a proof that the sum of N numbers in 0...N-1 is evenly distributed mod N, because if not, it would imply that a prisoner could somehow get information about his own hat from looking at the other hats, which is absurd, so we have a proof by contradiction. I've never seen this kind of proof before, where some presumption implies an absurd information leak, so therefore the presumption must be false. Very interesting.
Side note: Here is another way to prove that the sum of any amount of numbers in 0...N-1 is evenly distributed mod N.
The sum mod N of one number is just that number, so the even distribution is trivially true. Assume that the sum mod N of k numbers is evenly distributed. For k+1 numbers, choose any k numbers, and by our assumption their sum mod N is evenly distributed. For each of those sums, add all possible values of the remaining 1 number, and observe that the sum mod N remains evenly distributed. QED
"you won't know which one you have"
Me: B-but what about the guy wearing headphones
YOU WONT KNOW WHICH ONE YOU HAVE !!!
3:42 immediately had me thinking of Zelda BotW. XD
amazing solution and wholesome message at the end
I have seen similar, slightly easier problem before.
100 prisoners will be given each either a pink or a blue hat. This time however, every single one of them will need to be right to be let go. Any mistake makes them all lose. Which strategy will give them the highest probability of winning?
I'm guessing they assign blue and pink 0 and 1 (or vice versa) and all assume overall mod 0 or overall mod 1, so the overall chance is 1/2. Nice variation.
When i choose to calculate the chance of success directly, i tend to do it by calculating the probability of success for one person. Then i take the probability the first person failed and multiply it by the probability the second person got it right. Then i add them together. Then i take the probability the first two failed and multiply it by the probability the third person succeeded. And etc
This isn’t as fast as the proper method that you used. But it’s faster and simpler than the alternate methods you mentioned. And it feels like it gives a more intuitive way of thinking about it.
This is indeed a valid alternate method. When I mentioned alternate methods, I was trying to lead into the worst method, directly handling the overlaps, so that I could encourage the viewer to see that the overlaps must be non-existent for there to be a possible solution.
Before that, I said that we could try any alternate methods where we add up the probabilities of disjoint scenarios, which would include yours. The specific example I gave was 1 correct, or 2 correct, or 3 correct, etc... simply because it's easy to describe and illustrate. I could have added more but decided that it wasn't really central to the point I was trying to make.
Actually solved it without any hints, never felt this smart
I am very proud to say that I've found a solution for the original problem after the first hint!
Edit: My solution was the same as in the video, but I didn't think about probability at all. I just imagined the hats as numbers painted on their forehead, and from there it wasn't too hard to add them up
Astonishing!
"hats" off man (XD) this video is very poggers
> Be the only prisoner
> See a hat sum of 0
> Need a remainder of 1
> Guess hat 1
> Go free
> Get labeled a witch
> Get Robloxed
> MFW
It's a hot Saturday afternoon. Will tackle this on Monday first thing
pausing to find a solution
(spoilers)
what if we assign each hat a number 0-N and each prisoner a number 0-N
Each prisoner will pick the hat that, when summed modulo N with the other hats, produces their number.
Since the prisoners cover every number, whichever sum happens to be correct will automatically make said prisoner correct.
You beat the last boss in your underwear :)
@@goingnull6028 speedrun :)
2:28
This hint, was so helpful, and I recommend that everyone go down to two hats, then try 3. I was able then to get the solution, and it's really clever
But I'd never free prisoners who are this smart
Why do so many people want to help prisonners espace in these riddles? They're probably in prison for a reason! Great video though haha
I solved it like this,
Each prisoner is assigned a unique number from 0 to 9.
Each prisoner looks at the prisoner to the left. Then sees the number say x (associated with the hat).
Then the prisoner says x+ his/her number .
In that case also, we guarantee that there is no overlap and atleast one of them gets it correct.
I think that's the best thing about this puzzle. You can think of a lot of different non-overlapping puzzles and all of them will work.
Your proposed solution does not work for more than two prisoners/hats.
For two prisoners/hats, it's completely equivalent to the solution in the video. The one who is assigned 0 is effectively assuming his hat is the same as the other and the one who is assigned 1 is effectively assuming his hat is opposite the other.
For three prisoners, this strategy can be broken, for example, with prisoners assigned 0, 1, 2 having hats 2, 1, 2 respectively. In general, there is nothing in this strategy that guarantees that two prisoners can't be right simultaneously, so by the principles shown in the video, there will always be scenarios where this fails for more than two prisoners/hats.
@@goingnull6028 Ok, I went back to my proof, I basically proved for 010 , and 0,1,2 and it worked. So I just assumed that by symmetry, it will work for all combinations of form ABA. But doesn't work for 212.
But symmetry holds, so a different orientation of numbers will work for 212 too, but problem will be the prisoners will not have a way to track those changes.
Cool. Understood my mistake. Will try to find some different method then. 👍
Cool. I know of different solutions for cases where the number of prisoners/hats is composite, but not for when it's prime. If you find an alternate strategy for three prisoners I would be really curious to know.
After hearing the riddle and noting the restrictions imposed, I couldn't help attempting a fairly math-free solution. So I tried coming up with a strategy where the individuals would decide to close their eyes or keep them open based on the number of duplicate hats they see, with predetermined answers given by those who kept their eyes open for various scenarios of observed closed/open eye ratios. But I couldn't find a way to guarantee that someone would be correct in the event of multiple sets of duplicate hats without involving something more complicated like having the individuals open their eyes a second time, or instead having them only close one eye upon first inspection. Unfortunately, while they might get away with keeping their eyes closed, I couldn't get around the fact that taking blink/wink actions based on the blink/wink actions of others would definitely be considered nonverbal communication by the king.
Having finished watching the video, I realize that my attempted solution was not in the spirit of the riddle. Still I recognize that there are never too many ways to view a problem, so I figured I'd at least share my musings. That aside, I thoroughly enjoyed the genuine solution presented. I found the problem-solving methodology, along with the generalizations that followed, to be laid out in an intuitive manner. Thank you for making and sharing such elegant yet thought-provoking content!
Nice puzzle! IMHO the rules of the puzzle would have been easier to explain (and the puzzle would be essentially the same) if it was about identical tall hats having a random integer from 0 to 9 on them. Perhaps it's a bit easier as you don't need the mapping back and forth, but the math needed is the same...
Possibly. It was an artistic choice, and I'm no artist :)
The thing I always remember that allowed me to solve this is that you need to make the win condition subject to the arrangement as a whole, and I knew that there were effectively 10 chances to get it right, so in this case I was asking myself what property of the whole system is going to give me 10 cases, and once I considered that I immediately thought of the sum mod 10, from there it’s relatively easy to see that each person can determine what their hat must be under their assumption and so one must be right.
Even though the win condition is opposite it’s like the puzzle where there are a bunch of numbers in boxes and to escape everyone must open the box with their number (given a certain number of tries), where you maximise the chance by making winning conditional on a property of the arrangement of the numbers.
I'm glad someone brought up the numbers in boxes riddle! That riddle is kind of the inverse of this one. In that riddle, every prisoner has a 50% chance no matter what, but their strategy is to *maximize* the overlaps so that they all win together or all lose together. That's because they have to all be correct in order to succeed.
@@goingnull6028 That's what this reminded me of as well!
Congrats on the win!
Thanks for such an informative video! I went from "wtf" to "Wow, I actually made a soft!" in about an hour (I had to keep stopping and
So you have 10 guesses, as we can see the other hats we can assume everyone guesses the whole setup rather than just their own hat. Among those 10 guesses must be the correct setup. So ideally, we split all 10¹⁰ possibilities into 10 categories, and assign each prisoner one of those categories to cover, in order to maximize chances. We should also ensure that whatever the prisoner sees, there should be one and preferably only one matching example in their category. This reminded me of error correcting codes, so how about we make every prisoner ensure that the sum of all types in their guess matches the prisoner's own number by the last digit (ie mod 10). Clearly that's always possible in exactly one way for each prisoner. Now the sum of types in the correct answer must have a last digit, and there is a prisoner assigned to that digit, so that prisoner will be correct.
This might be a stupid question, but why can't you just assign each prisoner one hat type and have them each call that out no matter what they see? That way all 10 possibilities are covered and someone's guaranteed to be right.
First of all, I applaud you for asking. Someone who is shy to ask cannot learn. I think the confusion here is around different types of possibilities. There are indeed 10 different possibilities for *each individual prisoner*. However, each individual prisoner gets to express exactly one of those 10 possibilities for himself. There is no way a prisoner can ever cover all 10 possibilities of what he himself is wearing. So, for example, let's say there are just two prisoners and black/white hats. Just because one prisoner says white and one says black doesn't mean anything. They could both be right, both be wrong, or a combo. That's because prisoner 1 expressed only one of his two possibilities and prisoner 2 expressed only one of his two possibilities.
To solve the puzzle, we have to break the *entire system* into N different possibilities. So for example, when there are two prisoners, we say that either the system has two of the same hat or two opposite hats. In the case of 10, we sum the hats in the system, and say that the *global sum* has 10 possibilities. Then we have each prisoner express one of the 10 possibilities for the system, not for himself. That way we leverage the 10 prisoners to cover 10 different possibilities that pertain to the system as a whole, rather than to himself as an individual.
Hopefully this clears things up, but happy to try an alternative explanation if this is still confusing.
@@goingnull6028 at 0:37 there are multiple people with same hat, which makes the strategy "everybody guesses the same hat type" fail. But at the end of the video, when you start using numbers instead of hats, there's an assumption that each hat is given out only once, or that there is a permutation of 10 distinct hats. Can the final strategy work with the hat assignment from 0:37 ?
Where do you see that assumption? The numbers at the end of the video are not distinct at all.
@@goingnull6028 The distinction between "local" and "global" possibilities reeallly seemed to confuse me. As soon as you pointed it out, it made so much sense. Thank you so much for this explanation! And thank you for asking that question!
Once I got the the simpler part, I immediately learned the solution😁
Got it with no hints :) Thanks for the cool problem
Amazingly simple!
Am I wrong to think that the prisoners can just agree to say one hat type they see and then just keep saying the same hat? For instance, in the two person scenario if the first person says "top hat" because he sees that on the other person, the other person can assume the hat on his head is a top hat. This also works for ten people because if the first person picks one of the prisoners and says that type of hat, every prisoner knows at least one person has that type of hat. It might be that no one has that hat type except the one the first prisoner picked, but if everyone sticks to the same answer then at least that one will get it right.
See 0:40. The king wants to prevent information passing so he makes a rule that they must all answer at the exact same time.
Without seeing the solution yet. Just extending on the simpler problem (of 2 people, which I figured myself using a big table).
Possible spoiler:
There are N prisoners, let's number them from 0 to N-1. And N hats, also numbering them from 0 to N-1. Assuming we know all the prisoner's hats, summing their values modulo N gives some number from 0 to N-1. Now, each prisoner will be targeting a certain sum, equal to his number (so e.g. prisoner 3 will target the modulo sum to be 3). But no prisoner knows all hats. So every prisoner will guess a hat such that, when the modulo sum is performed, it is equal to their prisoner number. E.g., for N=10, prisoner 3 is summing all other prisoner's numbers, gets 37, so he guesses hat number 6, so that the sum would be 3 modulo 10. And the sum has to be exactly one of these numbers, so exactly one of the prisoners will be right in what the sum is, therefore also right in their own hat.