The Coolest Hat Puzzle You've Probably Never Heard (SoME2)
Vložit
- čas přidán 14. 08. 2022
- #SoME2 #SummerOfMathExposition
Of all the various hat puzzles/riddles out there, this one seems to be one of the least well known, despite being, in my opinion, one of the best. Let's change that!
"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.
i think this may have been my favorite video in soME2 !!!!
thank you so much for showcasing this problem, it was an amazing watch :)
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!
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'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!
As the story goes, this is the puzzle you get when applying to Mann Co.
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!
Brilliantly explained! The frame at 7:40 captures the beauty of this problem very well, and your ensuing visuals did the explanation justice. :)
Omg, this is one of those problems that seems literally impossible but once you know the solution it seems so obvious. Amazing solution
The second you said it could be guaranteed i had modular 'parity' in mind
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.
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.
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 :)
what a wholesome ending and a wonderfully explained video! thanks for your submission!
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 :)
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!
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.
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.
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 czcams.com/video/_le31Xhk9Eg/video.html
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.
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!
Holy cow I loved that solution, very simple visuals and great explanations !
Grats on winning SoME2! This was a really cool video!
This is absolutely splendid. I love these kinds of puzzles!
I really loved this video! The emoji style was surprisingly enjoyable to watch!
Great video! The look at probabilities and the events needing to be mutually exclusive really helps lead the viewer to the answer
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!
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!
SoME2 judges were right, this video IS really good!
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
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!
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 👏
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!
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!
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
[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
What a great video and riddle; I always love how satisfying these kind of riddles are.
extra points (from me, not the jury haha) for including probability into this even though there was never a connection to it
Very well presented and edited. You deserved to win SoME2
Congrats🎉
Great video, saw a reel about this and really wanted an answer to how it worked. And you explained it really well! :)
"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.
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.
Wow, loved this video! Please keep posting!
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.
Really nice take, and congrats on your prize!!!
loved the inspiring message at the end! 🙌
amazing solution and wholesome message at the end
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.
the most entertaining type of life is to be a prisoner in a math puzzle
The video is simple yet wonderful, nice submission for SOME2. The only thing that missing is outro/intro music
Dang, was just about to be executed with my homies, but this video saved us. Thanks bro.
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.
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 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] 🙏
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 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
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!
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.
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.
Congrats for the $1,000!
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.
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
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!
Great video, I loved it, very good job :)
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.
3:42 immediately had me thinking of Zelda BotW. XD
I don't know what to say but I still want to add a comment to express how good this was
Wow very nice explanation! Well done!
Astonishing!
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
If 3blue1brown didn't explicitely say what this video is about, I'd never check it!
EDIT: OMG this is so good, thank you!
"hats" off man (XD) this video is very poggers
Congrats on the win!
this is reminiscent of check digits in error correcting codes.
"you won't know which one you have"
Me: B-but what about the guy wearing headphones
YOU WONT KNOW WHICH ONE YOU HAVE !!!
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 feel like this guy took the problem and tried to make it simpler, but just made it harder
Thats such a cool video, love the emojis!
Actually solved it without any hints, never felt this smart
LOL!!! - I was on the right way but guessed it wrong! THX what a great video!
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 :)
It's a hot Saturday afternoon. Will tackle this on Monday first thing
Very nice work!
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!
Have seen the puzzle b4 . But now I know the logic behind it
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.
> 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
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
gratz on the win!
its awesome that you show why it is possible
Fantastic!!
It's important to state whether they need to announce their type at the same time or one after another, and in the latter case whether they can hear the other announcements.
It's stated twice that they need to announce at the same time.
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.
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.