Prisoners in Hats Puzzle: two variations

While in Norway doing some maths shows I was given a tshirt and a puzzle. Both are very mathematical.
If you have not tried a "Prisoners in Hats Puzzle" before, I explain the basic version. If you have seen it before, I also give a variation which I had not come across previously. Give it a go!
MathsJam: mathsjam.com/
Math-Jam: math-jam.com/
If you want to discuss this puzzle somewhere more comfortable, it seems I have a fledgling subreddit: / mattparker
Music by Howard Carter
Design by Simon Wright
MATT PARKER: Stand-up Mathematician
Website: standupmaths.com/
Book: makeanddo4D.com/
Nerdy maths toys: mathsgear.co.uk/

[@sunpowerguru3993]

The first person says, "Three, Two, One, NOW!" On "now" all 1,000 prisoners rush the guards, disarm them, and make their escape.

[@IamGrimalkin]

I don't think calling out the number "three" would be a good idea in that setup.

[@Spellfork]

+IamGrimalkin A, B, C, NOW! Then all rush :P

[@Pacvalham]

+Joakim Rannikko The guards don't have enough information to solve for those variables.

[@Pacvalham]

+Pacvalham Just Joking

[@АлександрБагмутов]

Better this way: "First person carefully examines all numbers, finds out which two numbers are absent, adds them with the number on the next person`s hat, finds the remainder of division by three, then screeches `NOW!`, all 1,000 prisoners rush the guards, disarm them, and make their escape."

[@DrGerbils]

If the last guy is willing too sacrifice himself, 999 can be saved. The last guy adds up the numbers on all the hats in front of him. The next guy subtracts the sum of all the numbers in front of him from that number and says the difference. Each subsequent prisoner adds all the numbers in front of him and the running total of the numbers said by everyone except the first one and subtracts that total from the number said by the first guy. For example, if the last prisoner in line is wearing 57 and 258 was discarded, he will see 999 numbers that sum to 500,185. He will say 500,185 and be hauled off to be shot. The next guy will add up the numbers he sees and come up with, say, 499,236. He subtracts and determines his number must be 949.He says that number and goes free. The third prisoner from the end sees numbers totaling 499,103, adds 949 to get 500,052, subtracts that from 500,185, says 133 and goes free. Etc.

[@EtoileLion]

+DrGerbils Assuming that the revised puzzle does not limit the responses (In the white/black version, you were restricted to saying white or black. If a similar restriction is in play here, the last guy cannot say a number greater than 1001.), this is a valid solution.

[@Datenshi76]

+DrGerbils I had assumed you could only say possible hat numbers, but yeah, seems to work. Nice thinking outside the box.

[@standupmaths]

Yes, it has to be a valid hat number. Otherwise the last person could take your method and call out the world's longest hat-number guess which is every single number in front of them, in order (even separated by zeros for convenience). Sorry, I forgot to declaring that for the second version!

[@JesseCaul]

+standupmaths My strategy involved using invalid hat numbers also. I suppose I'll have to try again.

[@laci272]

+DrGerbils It can ben even easier than that:) The first guy sees all numbers - his own and the '1001' hat. So he says: 'the 1st missing number'->adds 1 zero after it+'second missing number' (ex. 345011 or 1000908 {100 + 908}). The rest now know that his hat was either 345 or 11). Victory ensures for everyone else.

[@fakjbf3129]

For the hidden video, that's a capital "i" not a lowercase "l"

[@U014B]

So it's an İ, not an ı.

[@neshmicc]

+Fakjbf You da real mvp

[@mantonyz]

+Fakjbf Thanks, This is precisely why I prefer serif fonts.

[@RobinSongRobin]

+Fakjbf could you post a direct link to the video please? It didn't work when I typed 'l' (lower case L) or 'I' (upper case i)

[@peterschulze4975]

Thanks a lot, I thought, it was already deleted

[@omerd602]

There should be a version of one of these where the evil mastermind says that one of the people, completely at random, is actually on his side, and he will try his hardest to break the plan and get everyone else to die (of course if you want this to make sense you have to include that the guy won't die if he calls out the wrong number / color)

[@NetAndyCz]

I have strong feeling that this riddle seems to take for granted that all the prisoners are very good mathematicians.

[@anshulbishnoi3224]

Not all just one will do. if others are smart enough to listen to him.

[@benc8386]

OK I reckon I can do it with two deaths nearly all the time even if the executions are secret, and always with two if they aren't. Haven't read the other comments (didn't want spoilers) so apologies if someone else has said the same thing already. We assume you have to call out a number in the range 1 to 1001, or it's too easy. The first prisoner looks at all the hats in front of him, and will find two numbers missing out of the range 1..1001. One of those is his own hat and the other is the one the executioner removed before putting the rest of the hats on the prisoners. He adds those two numbers together and takes the result mod 1001. He calls out that number, and dies, because it definitely isn't his hat. It doesn't matter if anyone hears the shot or not this time-- he's definitely dead. The second prisoner starts off with the same procedure-- he looks down the line and works out what the missing hats are. He will find three numbers from the range 1..1001 unaccounted-for. There are three possible combinations of pairs of those three numbers, only one pair of which will give the number the first (now deceased) prisoner called out when summed mod 1001. So he can deduce which number his own hat is. For example, suppose the first two missing numbers observed by the first prisoner are 323 and 957. He will call out (323 + 957) % 1001, which is 279. If the second prisoner's hat is 288 (for example), the scan ahead of him for missing hats yields the numbers 288, 323 and 957. He then does these sums: (288 + 323) % 1001 = 611 (288 + 957) % 1001 = 244 (323 + 957) % 1001 = 279 Remembering that 279 was the number the first guy called out, he knows that the first guy's missing numbers were 323 and 957. Therefore he knows that his own hat is 288. So he calls out 288 correctly and lives. The third prisoner can do the same thing-- once he eliminates the number correctly called by the second guy, he only has a list of three to choose from, two of which are the original two, whose sum modulo 1001 he knows, so he can also figure out his own number. Now if it weren't for the rule that you can't call out a number that's already been called, we could go all the way to the end like this and nobody else would die. Unfortunately for the guy wearing 279 though, we will eventually get to him. He knows his hat is 279 but he can't call 279 because it's already been called. So, just to reiterate, he will have three missing numbers to choose from, 323, 957 and 279. He knows his own hat is 279 but can't call it because it was the first number called, and he's now allowed to call a number that's already been called. So the best thing for him to do is to call one of the other numbers from those three. So in this example he will call out 323 or 957. Those two numbers are the numbers of the first guy's hat and of the original missing hat. So by calling one of those, he won't be depriving anybody else of the opportunity to call his own hat correctly, and therefore also of his life, the way the first guy did to him. So he calls out 323, say, and dies. The next guy hears the shot and concludes from that that what he really meant to call out was 279, since that's the only reason to die. Since he does now know the previous guy's hat, he can carry on just as before-- having eliminated 279, and everything else that's been called, he will be left with three numbers: his own hat, and the first two that sum modulo 1001 to 279. So he can figure out his own hat and so it goes on all the way to the end. So this way two people die, assuming the executions are public. Now what if the executions are not public? All we need is for a way for each guy to deduce whether his predecessor died or not. So in this example, our second dead man (the first man always dies) had hat number 279, and his list of three numbers was 323, 957 and 279. He couldn't call 279, because it had already been called (it was the first number). So he calls 323. This means the next guy's list of three missing numbers will be 279, 957, and some other number (actually his own hat number, but he doesn't know that yet). Let's say it happens to be 980. At this point he can smell a rat. He knows that 279 isn't one of the original two missing numbers because it's their sum mod 1001. So he knows that either his own hat is 279 (and his predecessor didn't die) or that his hat is 980 (and his predecessor did die). So if he does the modulo-1001 sum of the two numbers he has that aren't 279, and finds that that doesn't equal 279, then he knows he's in luck, and that his predecessor is the one that died. So he can conclude from this that the previous guy had hat 279, but couldn't call it out because it was the first number called, is now dead, and so knows to "uncall" the number he did call (323) and to act as though he had called 279. When this goes wrong is when one of the first two missing numbers for the first guy was actually 1001. In that case his sum mod 1001 is equal to the number he calls out. This creates an ambiguity that can result in 3 deaths... Maybe there's a way around this, I don't know! The rabbit hole runs deeper. I reckon this does work because I tried it in a little Python simulation that I ran a million times which always resulted in two deaths for the public execution version, and located the pathological case for the secret execution version.

[@VVonderPie]

dang

[@radweghero1868]

+ben c Great Idea so far, at least in the case with public executions. I have some issues with the secret executions case. Firstly, I don't see how the second person unable to locate 279 concludes that 279 isn't one of the original two missing numbers. Especially if their own hat were 1001 and they were to see 279, 957 and 1001. But for the sake of argument let's say the group decided beforehand to assume they are not in the pathological case. The Person says "980" and lives. For the next person the 3 missing numbers will be 279, 957 and their own hat number. In the odd case that their own hat number is 323 (and thus adding 957 gives 279 mod 1001) they will conclude that they are the unlucky person with hat number 279, by the same arguments as the person who actually had that hat. They will then gloomily choose between 957 and their own hat number and in the latter case be positively surprised by not dying. In the more likely case that their own hat number is not 323, they will conclude that the person before them had hat number 279, by the same arguments as them. In the odd case that their hat number is 300 (and adding 980 gives 279 mod 1001) they will not even notice their mistake, say "957" and die. Otherwise they will see that their predecessor also wasn't the first person to not see 279. If they could somehow deduce that they are the third person to not see the hat numbered 279 they could ensure their survival, but I don't see how they would do that.

[@benc8386]

+M3P415T0 So just to recap the way it works is everyone (after the first guy) has 3 numbers to choose from, two of which sum-mod-1001 to the first number called (279 in this case). They know the other one is their hat so call that. If 279 is one of your 3 numbers, and the other two sum-mod-1001 to 279, then it's likely your hat is 279. You can't actually call 279 so you call one of the other numbers and die secretly. Now, suppose 279 is one of your 3 numbers, but the other two _don't_ sum-mod-1001 to 279. For example, you might have 279, 957 and 980. (957 + 980) % 1001 == 936, not 279. In fact, none of the three possible pairs here sum-mod-1001 to 279. So you know something has gone wrong. The only thing that can possibly have gone wrong is that the guy before you intended to call 279 and is dead. So therefore you "uncall" what he did call, which was 323 in this example, and pretend he called 279. Your three numbers are now 980, 957 and 323. (957 + 323) % 1001 == 279, so you know that your hat is 980. You call 980 and live, and everything carries on as before. But there are a few nasty corner cases where this won't work-- I think you might have found one or two more than in my original example. But it's still not a bad strategy because it's only two deaths most of the time.

[@radweghero1868]

+ben c Yes it works most of the time, and my own ansatz didn't do any better. I actually thought of some improvements to your strategy (see below), but i fear the worst case scenario still sees 50% dead. Oh, the things one spends time on, instead of working on ones thesis xD A first fix i want to suggest is the following: Whenever your three numbers include 1001 and the number the first person declared (279 in our case), you should say the remaining number. Yes there is a small chance that something went wrong and the 279 is just there because it cannot be said twice. (In this case your own number could be 1001). But by saying the other number you pass on 279 and 1001, ensuring survival for everyone who remains in front of you. This works because again they will assume that 279 and 1001 were the original missing numbers and so find out their own hat number. The bigger problem ist that after the 980-guys turn not everything carries on as before. Sure, everybody after him gets this 3-set consisting of his hat number, some number adding up with an earlier number to 279 and 279 itself. But in the case that his hat number also adds up with an earlier number to 279 he will have two numbers with that property, leaving him with a 50/50 chance. In a worst case scenario this can happen to half the people, and there seems to be no superior strategy: The strategy of assuming that the error occured relatively recently doesn't improve this, as is illustrated by the example 1, 1001, 2, 999, 3, 998, 4, 997, 5, 996, ..., 500, 501 (with 1000 taken out of play.) The first guy calls 1001 and dies. The second guy calls 1 or 1000 and dies. The third guy can deduce what happened, call 2 and live. The 4th guys three numbers are 999, 1000, 1001 or 999, 1, 1001. He sees that 999 and the 2 from the guy before him add up. According to strategy he calls 1000 or 1 and dies. The 5th guys three numbers are 3, 999, 1001. Since 998=1001-3 wasn't called yet, but 2=1001-999 was, he calls 998 and lives. From there on every second person dies. 501/100 dead. The strategy of assuming that the error occured relatively early doesn't improve this either, as is illustrated by the example 1, 2, 3, 4, ..., 498, 499, 500, 1001, ..., 999 (with 1000 taken out of play.) Everything goes fine until the 501st guy isn't allowed to say his hat number 1001. The guy with hat number 501 will have the three-set 501, 1000, 1001 or 501, 1, 1001. According to strategy he will assume that the error occured when 500 was said. He will then call 1000 or 1 and die. The guy with hat number 502 will have the three-set 502, 201, 1001. According to strategy he will assume that the error occured when 599 was said. He will then call 501 and die. Everybody from there on will call the number of the person before them and die. 501/1000 dead.

[@benc8386]

+M3P415T0 This pathological case where half of them die sounds interesting. If the first guy's two missing numbers are 1 and 1000, then he actually wants to call out '0' but that's not allowed. So the original rule that he calls out their sum mod 1001 isn't really valid. So if we change that rule to this: he calls out the sum of the missing numbers mod 1000 and then adds 1. We also say that whenever anybody does a modulo sum after that, they do the same thing: sum mod 1000 then add 1. This way all is well, and we get 2 deaths most of the time with secret executions and 3 very occasionally, and the first guy never has to call 0. But then with your pathological sequence, using this rule, the first guy's two numbers are 1 and 1000, which means he calls out ((1 + 1000) % 1000) + 1 == 2, dies, and then the guy with hat number 2 dies, and only two people die. It becomes a pretty normal state of affairs. So I'm wondering if you can refine your pathological sequence and still give me one that kills 501 people even with this new rule.

[@lucasc342]

I have discovered a truly marvellous solution for this, which this comment is too narrow to contain.

[@stumbling]

Pierre de Fermat's comment was marked as spam and has been removed.

[@JesusClunge]

+Lucas Lin lucas lins last theorem

[@trod146]

That hasn't stopped others from writing entire essays..

[@timfulford9395]

Mr fermatt I presume

[@katherinetheawesom]

Well, the person in the back should be able to see hats with all the numbers from 1-1001 except for two (their own hat number + the missing hat number). If you're at the back of the line, for instance, you might be able to see all the numbers from 1-1001 except for #406 and #79. The best option would be for the person at the back to give a non- whole number answer, like 406.79 or 406/79, to notify everyone ahead in line that their number can't be #406 or #79. This would give 999/1000 people enough information to deduce their own number perfectly.

[@sean_haz]

+Katherine Broderick That would work except he said that the number you state has to be a valid hat number, very creative solution thouugh Although it is unlikely to work in real life as people are selfish and wouldn't say something that would lead to their death when they had a 50% chance of survival otherwise

[@Dylzhaar]

Sean Hazlett it's not really a 50/50 in this case its more 1/1001 really so perhaps the person at the back would be courteous enough to do this

[@88Nieznany88]

Nope, it is 50/50 because he can see 999 numbers. So there are 2 numbers left - one on his hat and one taken away.

[@blueeye6545]

Katherine Broderick That’s exactly what I thought, but I think we can get technical with this, so if it has to be a valid one, the top person instead gives a problem. Say he can’t see 58 or 13, he’d say “58 minus 13”. Technically it’d be a valid, but wrong number.

[@pietromilano9933]

13+45 would be more convenient

[@IoEstasCedonta]

Hey - a Redditor ("Zkink") posted a brilliant solution, and I felt I had to truck it over. Just like the black/white hat problem, only the prisoner at the rear has to be risked, and it's 50/50 for them. (I'm adapting/paraphrasing it to make it as easy to grasp as I can.) We're going to pretend the missing hat is sitting on a mannequin right behind the back person, to turn it into a question of what order (or "permutation") the 1,001 hats are in. The person at the rear can see 999 of them, meaning that there are only two possibilities for them. Now, it's a known fact that, starting with the hats lined up from 1 to 1,001, you can only get to any given permutation with either an even or an odd number of swaps of two hats - a permutation is called "even" or "odd" accordingly. Because the two permutations the person at the back are a single swap away, one is even and the other is odd. The rear prisoner assumes the permutation is even, and chooses accordingly - if it's odd, that one prisoner dies. (EDIT: Thought I should be a bit more explicit here about how the prisoners do this. First, you assume some order for the two unknown hats - it doesn't matter which. Next you start a running tally at 0. Consider the first hat, the removed one, and move it to where it "should" be - e.g., if it's hat 137, move it to place 137, the head of prisoner 136. The hat it displaces, move it to where it "should" be, and so on until you get to your starting point. If the number of steps that takes you is *even*, add 1 to the tally - otherwise leave it as it is. Do the same for each hat in turn, counting the number of steps it takes you to get back to your starting point, aborting if you ever go back before it so that you only count each hat once. Again, if the number of steps is *even*, provided you never went back before your starting point, add 1. If when you're through all the hats your tally is even, your guess was right; if odd, switch the unknown hats.) (And yes, you add 1 for each *even* cycle because cycles of odd length are even and cycles of even length are odd. It's because you're counting swaps, i.e. 2-cycles, and you can turn an n-cycle into an n+1-cycle by swapping the last element with another outside the cycle, so a 1-cycle, being trivial, is even, a 2-cycle is odd, a 3-cycle is even, etc.) Now, the second prisoner knows 999 hats they themself don't have, the 998 they can see, and the one the first prisoner named. There are two possibilities: the first prisoner named their own hat and the permutation is even, or the first prisoner named the removed hat and the permutation is odd. In the first case, the second prisoner knows the position of 999 hats and the parity, which is enough to get the last two. The second case only comes up if the first prisoner named the removed hat, meaning they were wearing the hat they thought to have been removed, meaning that the actual order is only the one swap away from the order in the first case, so the second prisoner's hat is the same either way. From then on, everyone can be sure every prisoner after the first was right, so it's as if they can see all but the first, the removed, and their own, so they're each in the same boat as the second. The only problem is getting 1,000 people to not only be able to keep hundreds of numbers in their head, but be able to work out the sign of a permutation of 1,001 elements. I should stress this is not my solution. I made some slight changes (Zkink used different terminology, and put the removed hat at the front rather than the back), but it is not mine.

[@sk8rdman]

+IoEstasCedonta Complicated, but clever, and effective. I'm willing to assume that for this thought experiment, each prisoner is capable of any amount of calculation and number processing necessary, provided that they only use and give the information allowed. Of course, for the strategy you present, each person must be able to know whether each person before them (or at least the first person) guessed correctly, or was killed.

[@IoEstasCedonta]

sk8rdman No, they wouldn't - read the description again. If the first person guessed incorrectly, everyone after will think that person to be wearing the hat that was originally removed, and either that they're wearing their actual hat and the first person's was removed or that they're wearing the first person's and their own actual hat was removed. The former case is only one swap away from the actual permutation (the guesser's for the first person's), whereas the latter is a 3-cycle away, so the former is of the opposite sign to the actual answer and the latter the same sign. Since the first person would have been correct if the permutation were even, it must be odd, meaning that the former is even and the latter is odd, so the guesser will assume the former, and get their own hat right.

[@sk8rdman]

IoEstasCedonta I think I get it now. I did some permutation analysis with smaller numbers to get a feel for how it works. Assume there are 4 people in a line and 5 hats. The removed hat is in position 0. Positions: 0 1 2 3 4 Hat order: 4 3 2 5 1 The first person sees all but his own hat, and the removed hat, so he knows there are two possible permutations. 3 4 2 5 1 even number of swaps 4 3 2 5 1 odd number of swaps Everyone agrees to assume that the hats are in an even-swap permutation, so he says four. He's wrong, but now it's the second person's turn. The second person is going to assume first person one was right, so they're also left with two possible permutations. 2 4 3 5 1 odd number of swaps 3 4 2 5 1 even number of swaps As long as he picks the even-swap permutation, he will be correct, and give enough information to the next person for them to find their correct hat number with the same strategy. It doesn't matter if the first person is right or wrong, because as long as he can tell the people in front of him a number that is NOT on their hats, and that if that number is in position 1, then the permutation is even, then everyone else can assume even permutation to find their own hat number. Of course, this also works if everyone assumes the permutation is odd, as long as everyone agrees to assume the same permutation.

[@michalbreznicky7460]

+sk8rdman Thanks a lot for the examples! They illustrate the thing nicely. Although probably a detail (and mentioned before), I think it is helpful to point out WHY everybody can assume that person #1 was right (even in case he wasn't): By assuming #1 was right, everybody is wrong about hats in positions 0 and 1 (they are swapped), but this has no implications for their survival.

[@michalbreznicky7460]

By the way, there is another variation of the solution that does not need signs of permutations but so-called inversions. I suppose it might be a bit simpler to understand. I suppose many people thought about person #1 saying the "bigger number of the two" or something like that and work from there. Simply saying the bigger number doesn't work, as person #2 can have a bigger or a lower number again. But person #1 can cleverly put information about person #2 being smaller or bigger into what he says as well. In fact he must encode this information about all pairs of numbers. An inversion in a permutation is a pair of numbers that is out of order. For example, [1 2 3 4] has zero inversions, [1 2 4 3] has one inversion (4,3), [4 3 2 1] has 6 inversions (4,3),(4,2),(4,1),(3,2),(3,1),(2,1). It is very simple to compute the number of inversions in a sequence, albeit time-consuming. So, person #1 knows that there are just 2 possible permutations: 3 4 2 5 1 has 6 inversions 4 3 2 5 1 has 7 inversions The fact that the number of inversions differs just by 1 is not a coincidence. Swapping first two elements can only add 1 inversion, or remove 1 inversion. In both cases, one of the permutations must have an even number of inversions and the other an odd number. Person #1 will assume the actual permutation is the first one, as it has an even number of inversions and say "4". Person #2 chooses from these two: 2 4 3 5 1 has 5 inversions 3 4 2 5 1 has 6 inversions Again, he picks the one with the even number and says "2". Note that for a swap, the numbers of inversions can differ by more than just 1 in general. Example: 2 1 3 4 -- 1 inversion 4 1 3 2 -- 4 inversions The difference is 3, which is still fine for our purposes, because 3 is an odd number. The difference is always an odd number because * the swap itself adds or removes one inversion for the elements you are swapping * As for the hats laying between the two being swapped, the number of inversions will change by an even number. A rough explanation: If A is the number of inversions the left hat is involved in with the hats in-between and B is the number of inversions the right hat is involved in with the hats in-between, then after the swap this will change to N-A and N-B respectively. So we get from A+B to (N-A)+(N-B). The difference is thus 2N-2A-2B, which is even.

[@TheDrB0B]

So for those who want to check the answer, the last letter is actually an capital i, not a lowercase L. Or you can click on this one: kzbin.info/www/bejne/nGmchKWwiLenf80

[@Liliou]

Thank you mate! :)

[@cartersmith9842]

TheDrB0B everyone like and reply on this comment for everyone to see!

[@senseisecurityschool9337]

He's made that link private where you can't see it. Here's another link. kzbin.info/www/bejne/aWWsmGaOap6Sp6M

[@wbfaulk]

And now it's marked private and you can't view it.

[@wyattsheffield6130]

that was some smoooooth editing with the shirt.

[@Pecola1FromScratch]

I'd save everyone except for myself by saying "9-1-1" to Siri. Not really... I would die as Siri said "Sorry, I do not understand 'Pine won son'".

[@j0h00]

Unless you are in Norway. Then you have to call 112

[@sean_haz]

+j0h00 112 is international isn't it?

[@Beat105k]

+Sean Hazlett nope, in Switzerland it's 112 too.

[@AdamBomb5794]

In Britain it's 999...

[@want-diversecontent3887]

Pecola1FromScratch How about 108

[@12tone]

So my first instinct is to approach this with the same modular arithmetic solution that smaller variations are solved with, but I'm not sure a priori if that works with the "can't repeat a number" rule. At the very least, as a bottom baseline, we know that if everyone just says a number that they can't see and haven't heard, they all have a 50-50 shot at survival, so a solution that can't do better than that is meaningless. Let's see if the modular arithmetic version works. I count up the sum, get some number X, and say X mod 1001. That could be any number, since any number could be missing, but it gives me a unique descriptor for the state in front of me. Person 2 can then look at the people ahead of them, find the X mod 1001 that describes their state, and subtract theirs from mine to find the number on their hat. Person 3 subtracts Person 2's answer from mine to find Person 2's state, then does the same thing. The question is what happens when we get to the person whose number I said. If I got mine right by chance, then everyone survives. If I got mine wrong but the number I said is the one that got removed, I'm the only one who dies. In the very likely scenario that I got mine wrong and someone has the number I said, we're both dead, but in order to avoid breaking the chain we need to find a way to communicate that down the line. Fortunately, the system does that for us: All they have to do is give a wrong answer and everyone will know they had my number and can go on calculating like that. So it looks like the mod-arithmetic one works just fine, although there's psychological questions at play because if I'm first, I'm trading a 50% chance at personal survival for a .1% chance, so who knows if I'd actually go for it once I was there. But math doesn't care about psychology. Anyway, since that saves all but two and relies on knowing when an answer is wrong, I'm guessing that's the solution you came up with. Now to try to crack the bonus challenge. Does the same basic approach work? I mean, you can do the same thing to start, it's just a question of what happens when you hit the person who can't save themself because I said their number. How do they signal that? The simplest answer seems to be to set aside a different number for them to say. But a simple rule like "say the lowest available number" would run into the problem of what to do if that's actually your number but no one's indicated a failure yet. So instead, let's use a number that everyone knows is wrong down the entire line: The last person. If I know I've got the number that the person at the start said, I look all the way down to the very end and say that number instead. Then everyone knows that I was wrong, which means I must have been stuck, which means I must have had the starting number. And that guarantees that three people will most likely die, but everyone else will definitely live. Wooh!

[@12tone]

+12tone Scanning some other comments I realized I forgot to mention that, if the state you find yourself in is 0 mod 1001, you say 1001, because 0 isn't an option and the two are equivalent mod 1001. That seems obvious, but figured I'd specify.

[@jorgesilva2428]

Not reading all that mate, sorry

[@Porglit]

BTW, that's f89SrzSRtIk with a capital "i" at the end, not a lowercase "l"...

[@dermathze700]

Thank you!

[@MrDarkplum]

It was never stated as a rule that the number chosen has to be between 1 and 1001. If the first person is willing to sacrifice themselves then everyone else can be saved easily: take the two numbers that are missing from the 999 people in front of them and add them as strings with a separation identifier like 000. e.g. numbers 231 and 933 are missing so they say 231,000,933 and then everyone after knows that their number is the number missing from 231, 933, and the numbers of the people in front.

[@AZWADER]

I commented the same answer! (Albeit in a much less compact way) Some people were just born to bend the rules 😎

[@jasongraves973]

If you were going to do this you could just read off everyone's number with a separator

[@thomaswarriner2344]

Using the solution of the black and white puzzle (which I knew the answer to), in which the back person uses what he can say to save the others. The person at the back adds up the numbers on the hats and says that (he gets it wrong but watcha gonna do?), from there, considering everyone can do maths correctly, all but one goes free. They work it out by adding up the hat that they see and subtracting that from the previous person's answer. I saved 999 people.

[@MrCreeper20k]

+Thomaswarriner In the comments he said that the answer they give has to be a valid hat number.

[@thomaswarriner2344]

?

[@YouLilalas]

+Thomaswarriner He means that you can’t say a number higher than 1001 because that could not be a hat number.

[@thomaswarriner2344]

Ah i see! Thanks!

[@fishbone0]

+YouLilalas If you do as ThomasWarriner, and just says the sum of all the numbers he can see modulo 1001 (+1 to get a valid number), you would still be able to see what your missing number is. You will probably ruin it for one of the other people, but if you are really lucky that could still be your number. So you should be guaranteed 998 saved (if my math was correct)

[@adamthornton7880]

I haven't looked at anyone else's answers yet, but my suggestion is: The first person (who can see every hat except the one that they are wearing and the one that has been removed) says the sum of the 2 hats they cannot see. If the sum is greater that 1001, and if prisoners are forced to give valid answers, they subtract 1001 from the answer. The next person can see every hat except the one they are wearing, the one worn by the person behind them, and the one that has been removed. and they know that of the 3 numbers they cannot see, only one pair of numbers sums to the number that the first person said, so their number must be the other one. Similarly, everybody further down the queue can see the hats of everyone in front of them, and has heard the numbers of the hats worn by everyone behind them except for the first person, so they can directly eliminate every number except the one worn by the first person, the one removed, and their own number, of which the first 2 can be eliminated using the method above. When the person whose number is equal to the answer given by the first prisoner is reached, they say their own number and are presumably killed for picking a number that has already been said, but they were doomed anyway. If this person is forced to choose a different number, they say the number worn by the person at the front of the queue, which lets everyone in front of them, except the very front, know what number they were. This way, the first person in the line, the last person in the line, and the person whose number is congruent with the sum of the number removed and the number worn by the person at that back of the line modulo 1001 are executed, everybody else is released.

[@pardox28]

Say you're last (1st to guess; can see all other hats) & you wear hat 501 and hat 800 is the missing one. 501+800=1301-1001(per your rule) =300. So you say "300" but now the person wearing hat 300 can't say the number of their own hat.

[@patrickroelant5171]

+Adam Thornton if the person in the back can see everyone else's then he could go for the 50/50 on the two and if he dies the next person also would have a 50/50 between their own and the dead guys but then wouldnt everyone else be set knowing the others?

[@philipnielsen2104]

+Patrick Smith no, because the third guy would have a 50/50 between his own hat and whatever unaccounted for hat hasn't been mentioned yet, and so on.

[@mrmoenty8451]

+Adam Thornton Nice solution! You can modify it to obtain the solution where everyone but two people are guaranteed to live, in the case that everyone hears who lives and who dies. Simply have the unfortunate person whose number has been said by the person in the back say one of the two numbers which they don't see before them, and which have not been said yet. One of these two numbers is the one worn by the person at the back, the other one is the one worn by no one. That way, no one else before them is doomed. Since everyone hears them being executed, everyone knows what happened, and can carry on as usual.

[@Coldheart322]

+Jon Forsythe That is kinda the point, in this puzzle some people gonna die. You are trying to limit how many. The first time I heard the original hat puzzle, they all lived if all but one of them got it right, and all died if 2 people got it wrong (or broke any of the rules). I prefer this, as it means you can remove psychology from the maths problem.

[@lvl1969]

Whatever the strategy, the first prisioner can't have more than 50% chance of survival. However, everyone else can be saved. Oh, and before commenting, please understand what parity means: en.wikipedia.org/wiki/Parity_of_a_permutation (not the best explanation, but the easiest to find) The order of the hats is a random permutation of (0,1,2,...,1000). Let's say the 0th hat is discarded, 1st given to the first prisoner and so on. Supposing everyone names their hat correctly, every prisoner on their turn will know of 999 hats and their positions. From the set of all permutations, they are left with a choice from 2 of them - one of even parity, the other odd. Algorithm follows: All the prisioners agree to guess that the (random) parity will be even (or odd, it doesn't matter as long as they agree). The first prisioner sees all the other hats and acts accordingly. For the rest of them it doesn't matter if the guess was correct or not. She told the others what she knew the order has to be for the parity to be even. The actual order of the two first elements of the hat-permutation doesn't stop the rest of the prisioners from answering according to the hypothetical even permutation. PS. To clarify: Nth prisioner knows the place of every hat except 0th and nth, and knows the missing numbers. Switching two elements always switches the parity, so they always have a choice between even and odd parity. PSS. This is also the only solution which guarrantees that everyone but the first will live. Every other such solution has to use a property that is essentially the same as parity. I might make a better explanation of that.

[@nicsheffer247]

could the guy in the back just add up all the hats in front of him and say that number, which will obviously be wrong and he will die, but then everyone in front of him can add them all up subtract the difference and say the correct number. Assuming they can remember all the numbers said behind them they should all live but the guy in the back.

[@ryanmcclure3749]

This also works if you don't know if they live or not. I think this is the best answer for both. Or at least it would be if that was allowed.

[@Annatar.]

There is a missing hat.

[@Varstahl]

+JA150EA in this scenario it makes no difference whatsoever, since the sum will be counted on the spot. From there on it's just a matter of taking that number, subtract all the ones you have in front AND in the back, and the result is your hat number.

[@Lahbreca]

+nicsheffer247 Sadly, you're not allowed to say a number bigger than 1001 - Matt forgot to say this, but it is clarified here in the comments. And I quote: "Farther You never said we couldn't guess a number bigger than 1001. But, this riddle is too easy if you're allowed to (our solutions are even better than yours!). Can you please clarify?" "standupmaths +Farzher Yes, and it has to be a valid hat number! Sorry, completely forgot that bit. Will add that to the notes."

[@ProBilogo]

I got it... prisoner 1 sees 999 numbers so there are two numbers left. he takes these two, let's consider them a and b and the number of the hat in front of him (c). He says the number between a and b which is the largest Before c(if c

[@crater7]

for the black and white problem, the first guy could guess any colour while singing a long drawn out note, higher for white, lower for black, and in the order from back to front. that saves all but one.... but not with maths...

[@madelinepoopoo]

I like it better your way anyway.

[@IceMetalPunk]

+Captain Crater Luckily, you can save all but one with maths and no one needs to have perfect pitch :P

[@Tylemaker19]

I really enjoy this solution

[@stephblackcat]

+IceMetalPunk You hardly need perfect pitch to go high or low. Nor to recognize high and low. Also as the video said math only guarantees 3. Not five.

[@AgentDRJ]

+IceMetalPunk You wouldn't need perfect pitch, just not complete tone deafness.

[@dsol222]

For the second puzzle, the person in back can see everyone in front of them and read all 999 hats. They can then call out all hats they see in groups of 4, taking one for the team. The person in front knows to listen to the first set of 4, the next listens to the next set of 4 and so on.

[@zlotnleo]

The first person says the sum of all numbers he sees in from of him. The next person subtracts the sum of all numbers they see in from of them and gets his number correctly. The following prisoner then can subtract that number from initial and then subtract the sum of all numbers in front of him to guess his number and there it goes until everyone is saved except for the first one.

[@sjoerdiscool1999]

Wow, great!!

[@Macieks300]

+zlotnleo Can only say numbers from 1 to 1001

[@gasten1236]

+Macieks300 How about doing that but with sum mod 1001? I guess maybe that way you could say some numbers twice, but the risk is very small.

[@Macieks300]

Ewout Hardeman Yeah, you're close

[@samuelunderwood5286]

Similar solution, the person in the back says the sum of the 2 numbers he doesn't see, from there, everyone in front of him can figure it out.

[@goobershnoz]

Matt Parker for 13th Doctor? Anyone?

[@ManTheRabbit]

+Garrett Tyler pls

[@trod146]

He's Australian...

[@stephenkamenar]

You never said we couldn't guess a number bigger than 1001. But, this riddle is too easy if you're allowed to (our solutions are even better than yours!). Can you please clarify?

[@standupmaths]

+Farzher Yes, and it has to be a valid hat number! Sorry, completely forgot that bit. Will add that to the notes.

[@unvergebeneid]

+standupmaths Dammit. I was guessing that this was a rule but it's so much easier if it isn't.

[@stephenkamenar]

+PowerChannel88 I would say everyone dies if you repeat a number, that breaks the rules. (but it's up to the evil mastermind standupmaths)

[@BeHAPPYM]

+Daniel Weiss What if the number you have to say , the last digits of the sum, is the number the guy in front of you has on a hat ? ... then he couldn't say it ... and it would broke the strategy ..

[@JackDrewitt]

+standupmaths does it have to be an integer?

[@ScalperSkid]

If you can see the nubers of the hats of 999 persons in front of you you must have pretty good eyes :)

[@duskfinger6799]

If the person at the backs says the sum of all the numbers in from of him he dies. But then the one in from can work out the difference between that and what he sees. Everyone else needs to keep track of what's been said, and keep working out the difference between the original sum of numbers, and what they can see, allowing all but one to survive.

[@MikkelBytoft]

+Hugo Fortescue That was the solution i came up with too. Of cause that only works if he is allowed to guess a number that is not on the list (Matt didn't say you can't do that, but i dont think you would be allowed to). Currently working on a solution that have him guess a number on the list instead.

[@830927mjki]

+Khanh Duong Phan if you can say any number then person 1 says n1*10000+n2 e.g. if the numbers are 64 and 211 then he says 640211. then people can just say the number they can't see out of whats left. same solution but simpler math. mod doesn't work as there are multiple answers. e.g mod(sum-1-2,1001) = mod(sum-501-503,1001)= 998 you could do (larger unknown - smaller unknown) instead

[@MikkelBytoft]

Not from an English speeking contry, so the therm "mod" is not something i know of, however, the way John explained it, i have allready considered and of cause not found to be a prober answer :)

[@830927mjki]

+Mikkel Bytoft mod = Modulo. mod(5,2) = 5/2 = 2 with remainder 1. with mod you keep the remainder so 1. you right, my suggestion doesn't work either.

[@830927mjki]

+Mikkel Bytoft well 2 remainder 5 but yes i have also seen it written as 17 mod 6 or 17 % 6

[@michaelhueftlein]

+standupmaths The first person in line says the addition of the two numbers that they cannot see. If it is too high they rollover and start counting from 1 again. The second person in line now knows the sum of the two people in front of them and can deduce the two values either by eliminating all other combinations of numbers adding up to that sum because of the people in front of them, or because they can see that number in front of them. If the person says a number that is not in front of them, they are the number. If the number has already been said, they can deduce that they are the other possible number. With examples: Example 1: Missing Hat #628 Prisoner 1 #314 Prisoner 2 #56 Step 1: Prisoner 1: Gives the sum of the two numbers they can't see (628 + 314 = 942). Step 2: Prisoner 2: Looks for 942. Finds it. Step 3: Prisoner 2: Looks for all the missing numbers and sees that it the missing numbers are: 628, 314, 56... Step 4: Prisoner 2: Tries to find combinations that add up to 924... 628 + 314, meaning they are 56.. Step 5: Each following prisoner: add all numbers before them, and all numbers after them and subtract that from the total of the numbers. Example 2: Missing Hat #720 Prisoner 1 #314 Prisoner 2 #56 Step 1: Prisoner 1: Gives the sum of the two numbers they can't see (720 + 314 = 1034). If the number is greater than the total number of hats roll over and start counting again. i.e, 1034 would translate to 33 (1034 - 1001) Step 2: Prisoner 2: Looks for 33. Finds it. Step 3: Prisoner 2: Looks for all the missing numbers and sees that it the missing numbers are: 720, 314, 56... Step 4: Prisoner 2: Tries to find combinations that add up to 1034 or 33... 720 + 314, meaning they are 56.. Step 5: Each following prisoner: add all numbers before them, and all numbers after them and subtract that from the total of the numbers. Example 3: Missing Hat #720 Prisoner 1 #314 Prisoner 2 #33 Step 1: Prisoner 1: Gives the sum of the two numbers they can't see (720 + 314 = 1034). If the number is greater than the total number of hats roll over and start counting again. i.e, 1034 would translate to 33 (1034 - 1001) Step 2: Prisoner 2: Prisoner 2: Looks for 33. Can't find it. Step 3:Prisoner 2: Is number 33. Example 4: Missing Hat #1001 Prisoner 1 #1000 Prisoner 2 #56 Step 1: Prisoner 1: Gives the sum of the two numbers they can't see (1000 + 1001). If the number is greater than the total number of hats roll over and start counting again. i.e. 2001 would translate to 1001 (2001 - 1001) Step 2: Prisoner 2: Looks for 1001, if they can see 1001 they know that the number has rolled over and must be a combination of numbers. If they can't see 1001, that is their number. But since they can't say a number twice they know that the two numbers missing are adding up to the 1001mod2 and therefore it must be the only other missing number.

[@goblinm13]

+Michael Hueftlein Excellent description with clear examples. Bravo! A few corrections: instead of saying "Each following prisoner: add all numbers before them, and all numbers after them and subtract that from the total of the numbers." this is equivalent to saying "Each prisoner: Keep track of the sum stated by prisoner 1. Eliminate all numbers said by previous prisoners and numbers seen in front of them as known numbers. They will have three 'missing' numbers left over. Derive which two of the missing numbers sums to the number stated by prisoner 1. Their hat is the third number." Another correction, in your example 4: missing hats 1000 and 1001 will sum to 1000; you correctly stated the equation (2001 - 1001), but used the wrong result. Your solution doesn't really address what a prisoner should do if THEIR hat is the sum. For simplicity, I am calling this prisoner the 'unlucky prisoner' because they cannot guess their own hat number despite knowing it. They will see three numbers missing, the two missing from the first prisoner, and the sum itself. This is where it is critical whether other prisoners hear the fate of whether prisoners guess correctly or not. If they do get to find out the result of each guess, the unlucky prisoner can state one of the two numbers making up the sum. Since the other prisoners hear that the guess is wrong, they will know that the number is one of the 'missing' hats and part of the sum, and will not remove it from their list. If the unlucky prisoner's guess is NOT known to be right or wrong, the unlucky prisoner will have to pick another number so that the sum isn't disrupted for future guesses. They will have to pick a number of a hat that they can see in front of them. It would make the most sense to pick the hat of the prisoner to guess last, because it will screw up all future prisoner's ability to determine their hat. Simple example with 10 prisoners, hats 1 to 11. This is assuming that prisoners DON'T hear the result of hat guesses. Prisoner 1: 2 Prisoner 2: 11 Prisoner 3: 6 Prisoner 4: 4 Prisoner 5: 9 Prisoner 6: 10 Prisoner 7: 3 Prisoner 8: 7 Prisoner 9: 8 Prisoner 10: 5 Missing hat: 1 Prisoner 1 will see that hats 1 and 2 are missing, and say "3" defined as SUM Prisoner 2 will see that hats 1, 2, and 11 are missing, notice that only 1+2 = SUM, as 2 + 11 = 2, 1 + 11 = 1 (remember, we are using mod 11), and determine that his hat is "11" Prisoner 3 will see that hats 1, 2, and 6 are missing (remember 11 has already been said), and determine his hat is "6" and continue... Prisoner 7 will see that hats 1, 2, and 3 are missing. He will determine that HIS hat is SUM, and cannot say that because it is against the rules to say "3" again. I've been calling this prisoner the "Unlucky prisoner" In the case where Prisoner 7 says "1" (and the same results happen if Prisoner 7 says "2"): Prisoner 8 will see that hats 2, 3, and 7 are missing. He will notice that no combination of these hats equals SUM, and cannot determine his hat. Prisoner 9 will see pretty much the same thing. In the case where Prisoner says "5" (which is the hat of Prisoner 10, who is the last to guess): Prisoner 8 will see that hats 1, 2, and 7 are missing, and determine his hat is hat "7"... continuing on down the line to Prisoner 10, who cannot guess his own hat since "5" was already stated.

[@NoriMori1992]

8:28 - "Let me just get this OFF -" Me: 8'D Matt: [does a trick so that you don't see him shirtless] Me: …8'c Dammit Matt, why do you have to be such a tease? XD

[@FrostMonolith]

That man on the back, you know? He's the real hero.

[@Benny_Blue]

Okay, I've got a strategy. (Warning: This is all in good fun, and not intended to be taken seriously at all). The person at the back says "666," in the hopes that it will summon a demon. They then make a deal with that demon to give their soul in exchange for the death of the evil mastermind. This not only saves everyone but one, but it also beats the bad guy.

[@denizcelik14]

I think the best way to solve it is with subtsracting.There are a few things you can do with 2 numbers: addition and multiplication isn't going to work cause some of the answers are above 1001 and division is obviusly the wrong choice so the next thing we got is substraction. The first person says the positive difference between the two hats he doesn't see he dies. But this sends a message to the others. There are a few problems but we can make some rules/ sacrifices. I don't think this was the way Matt was talking about but it usually works.

[@eyadmardini8904]

f89SrzSRtIk you're welcome

[@omarmassoud8811]

+eyad mardini How to open the video ?

[@chantelm9255]

+eyad mardini I typed this in (then copied and pasted what you wrote just in case), but each time I got a 404 Not Found error. :(

[@ciarfah]

***** Look at what I typed^

[@vara202]

+eyad mardini I keep getting a video not found when I type it in.

[@pgaboury]

+vara vashtul It's a capital "i" before the k, not a lowercase "L".

[@saxbend]

for the classic hats problem I am familiar with the parity based solution, but when I first came across this puzzleI came up with a very different solution that will guarantee to save all but one. The person at the back still has a 50% chance of course. Each person communicates the colour of the hat directly in front by either hesitating for a couple of seconds, or speaking as soon as it is their turn. A hesitation indicates one colour, an immediate response indicates the other, so everyone except the person at the back knows what colour hat they have.

[@exnihiloyoutube]

Say you have only 5 people and 6 hats. They are, in order, 2, 6, 1, 5, 3. Four is taken out by the prison master. The first person in line sees the hats in front and can deduce the two hats left over. She is either wearing 2, or 4. There's a 50/50 chance she'll guess accurately. She can say the lesser, 2, if she sees an odd amount of odd numbers (which there are) or he greater, if there is an odd amount of even numbers. It must be one or the other, and you're guaranteed that there can't be an equal amount of both, (because there are 999 people in front. )The next person hears the message, and ponders what their own number can be. They have three choices. They could say the previous response, which isn't very smart, because this ensures one death at least. They can say either six or four. Again, they only see odd numbers, an odd amount, so they'll say 4, and they die. Since the rest are odd, they all pass through, since they eliminate the previous numbers and the ones they see in front.

[@exnihiloyoutube]

If there were 1000 hat numbers, the game would be a snap. First person sees every number except for 921, second guy sees everything except for 921 and 632, etc. The fake hat number throws an uncertainty. This uncertainty has to be worked out with the first two guys, that's why you need at most two people wrong. But hey, maybe one of them lucks out and gets the right answer? No, sorry, because the wrong information needs to be conveyed at some point, or else person three dies, or four, or whatever. Person three needs all hats in front, which she has, the hats behind her, which she can have, and the fake hat number, given thanks to the two behind her. After the wrong hat number has been conveyed to the rest of the group, the whole thing proceeds as was stated in the beginning. Person four KNOWS the fake number, AND every other number, so he now knows his own, etc.

[@undergroundo]

+Daniel Potashov Ingeresting, but I think it breaks with this case: 5, 3, 4, 2 1. Person 1 knows that his hat is one of these: 1, 5. 2. Person 1 sees: 3, 4, 2. 3. Person 1 sees that the odd count from his point of view [3,4,2] is odd (only one odd number: 3) 4. Person 1 says his low number "1", to indicate that the odd count is odd. 5. Person 2 sees 4, 2. 6. Person 2 sees that the odd count from his point of view [4,2] is even (no odd numbers). 7. Person 2 deduces that, because his own odd count is even, and the odd count from the previous was odd, then his own number MUST be odd. 8. Person 2 knows that his hat has to be one of the hats he does not see: 1, 3, 5. 9. Person 2 can eliminate hat 1, because it was already said. 10. Person 2 has to chose between 3, 5. 11. With no further information, he makes a 50-50 call.

[@exnihiloyoutube]

+Cesar Coll if he says three, then lives, person three has no information. Now person three has to choose between 4, or 5. This is why two have to die to be certain. In a fantastic scenario, everyone could luck out and just avoid saying the fake number. Or, person two can say 5. They die, there are no more odd numbers, the last person is 2, so person three must be an even number, and person three and four both walk away.

[@vlogsnstuff3989]

Everyone can be guaranteed to be saved except the guy at the back if they use numbers as a code to relay information to the front of the line. The guy at the back could say everyone's number in order from front to back and have five 0s in between everyone's number(so the numbers don't get confused together). Everyone counts their place in line and when the guy at the back has said as many numbers as their place in line they pay attention and memorize their number and now everyone knows their number.

[@TechnocratiK]

First of all, let's assume that the hats are numbered 0-1000 instead of 1-1001. Then the first person to speak says the sum of all the hats he can see modulo 1001; call this 'x.' The second person performs the same sum (obviously, less their hat), and subtracts it from 'x' (modulo 1001) yielding their hat number, which they then say. So when it comes time for a person to say their hat number, they know the numbers of all the people before them except the first (because they've been said), and all the people after them (because they can see them), and thus 'x' less the sum of these two must be their hat number (modulo 1001). Unfortunately, some poor prisoner is stuck with hat number 'x' which he cannot say; he also needs to inform those in front of him that the number he is saying shouldn't be included in the sum. If the prisoners in front of prisoner 'x' know whether 'x' lives or dies, 'x' simply needs to say one of the two numbers he knows to not be in the line (and thus die) to inform the others. If the death of prisoner 'x' remains secret, he can use the hat number of the last (i.e. furthest away) prisoner (and thus die, taking the last prisoner with him) to inform the others, since they can all see said prisoner's hat.

[@XavierXonora]

+TechnocratiK Cold but valid. Sucks to be person number 1000

[@tkrassowski]

I was so confused by this solution for a large part of the day because I forgot you can't repeat a number. Now it all makes sense

[@tamebeverage]

The best I can come up with is saving 997 prisoners. My method would be to have the first prisoner add the two numbers he can't see, and report the value in modulo 1001. Almost every prisoner after that would have 3 numbers that have not been said and cannot be seen, and only one pair could possibly match up to result in the same number modulo 1001. For example, if the original two numbers were 87 and 954, the first prisoner would report 40, and no other number between 1 and 1001 could add to either 87 or 954 to get that result, so all other prisoners would be able to deduce their own number. The prisoner whose number matches the one that the first prisoner reported would need to say the number of the final prisoner so that the information is preserved and no other prisoners are condemned unnecessarily. He would be able to know to do this because he would notice that only 2 numbers are not accounted for, instead of the typical 3. This method is guaranteed to kill at least 2 prisoners, and will kill 3 roughly 99.9% of the time. Edit: there is actually a slim chance that, using this method, nobody dies. If the first prisoner happens to be forced to choose between 1001 and x while wearing hat number x, all prisoners survive. However, all things considered, the expected average death toll (say you somehow did this a billion times for some reason) would be just about 2.993 deaths/round.

[@craigroberts7013]

let N equal the number of hats (N = 1001 in the video). let S be equal to the sum of the two hats which the first prisoner cannot see. prisoner 1 sacrifices his guess and gives his answer as: S mod N. All other prisoners, being aware of the strategy, can narrow the possible values of their own hat to 3. Only two of the choices will obey the property given by prisoner 1's answer. The third must be the value on their own hat. A problem arises if a person knows the value on his hat, but that value was already used by prisoner 1 to give his information. The unlucky prisoner must also sacrifice his guess but he must also alert the rest of the prisoners to the true value on his hat so that they will know to exclude it from the possibilities. To do this, the unlucky prisoner gives as his answer the value on the very last prisoners hat which all other prisoners can see. When this happens he sacrifices both himself and the last prisoner in the line. The best possible scenario is that the hat with value N is the one that has been excluded. This results in every prisoner having a correct guess. The second best scenario is that the hat with value N is on the head of the first prisoner. This results in only the first prisoner being wrong. In all other scenarios three prisoners are wrong; the firist, the last and one at random.

[@PersonaRandomNumbers]

+Craig Roberts Aww, man! I thought of the modulo function and summing the remaining hats, but I forgot to take the unlucky prisoner with hat number S mod N into account.

[@craigroberts7013]

I just realized my last paragraph was wrong because the hat with number S mod N could be on the last prisoner in which case only the first and last die.

[@mattlm64]

+Craig Roberts This is simpler than my own solution which was to calculate the modulo of the sum all the known numbers and then compare it to the first person's answer. The result is exactly the same though.

[@vonbillfamily]

I read a few comments, and I didn't see this exact solution mentioned, but someone else probably has it already: First puzzle (if they can hear if the person behind them is killed): The first guy adds all of the numbers in front of him, mod 1001, then adds 1. This is a number between 1 and 1001, so it's a valid hat number. This is also most likely someone else's hat number in front of him (a problem not mentioned in some of the solutions I have read). The next guy now does the same thing, and his number will be the difference, since it will be the only number between 1 and 1001 that would have given they guy behind him the result that was said. So guy number 2 is correct. The guy in front knows what the first guy said, he knows the second guy was correct, so he can now figure out his number. The problem comes when a you get to the prisoner who is wearing the number called out by the very first guy. He can't repeat the number, so he has to say one of the two numbers he doesn't see that hasn't yet been said. He gets killed. The guys in front of him hear this and know that his hat must have been the first number stated. So they still know exactly what number everyone behind them (except the first guy) is wearing. The two guys who die at most are the first guy and the guy with the number the first guy says. Second puzzle (if they can't hear if the person behind them is killed): This is done exactly the same way, but now there could be the point when we get to the guy who knows he is wearing the hat with the number already stated by the first guy. If he treats this like the last puzzle, the guy in front of him will assume that was correct, and everyone in front of him will be wrong. So when we get to this guy, he calls out the number of the guy in the very front. Everyone (except the guy in front) will now have that signal to know that this guy was wearing the first number called out, and they can proceed. Then the guy in front will also be killed. The three guys who die are the first guy, the guy with the number the first guy says, and the last guy. I think that would work, but I could be wrong. The comments I read did help me get to this solution, I just didn't see any comments talking about what happens when we get to the guy who knows what number he has on, but he can't say it because it was said by the first guy. And sorry if this solution is stated somewhere else.

[@thoughtyness]

Let's use 5 people. 1=4 2=1 3=6 4=5 5=3 so person 5 has hat numbered 3. Person 1 adds the sum of all the hats he sees so 15. He is then killed. Person 2 adds all the numbers up so 14 he then takes 15-14 and gets 1. He lives. Person 3 sees 8 he then does 14-8 and gets 6. He lives. Person 4 sees 3 so he does 8-3 and gets 5. He lives. Person 5 says 3 as he is the last person. He lives. This way for having 1,000 prisoners only the first person dies. Now keep in mind two things 1.If person 1 lies or gets the problem wrong everyone will die. So add in a few more people who say the sum of the hats in case someone messed up. 2. Since when are prisoners smart?

[@TheMrVengeance]

+ComplexScience - It was clarified in one of the top comments that you're *only allowed to say a valid hat number*. So for the example of 5 people, you'd only be allowed to guess 1-6. So the first one can't say 15. With a 1000, it's only 1-1001.

[@feralcatgirl]

+TheMrVengeance just say the sum modulo 1001 then. no information is lost.

[@OrmTostesson]

+Syzygy314159 but then what about the person that has the number of which you said the modulo of? they can't repeat it

[@TheMrVengeance]

Syzygy314159 - Seems like a lot of mental arithmetic to add up close to 500.000 in modulo and for the next prisoner to reverse it back.

[@thoughtyness]

+TheMrVengeance There is no way to reverse a modulo. If this were true then the encryption algorithm R.S.A. (used to encrypt everything on the internet) would fail. However molding the sum of the people in front of you by the amount of people+1 is actually easier.

[@MidasSchonewille]

Since there is a finite amount of possibilities of distributing the hats and leaving one out, you could easily come up with a system that lists off every single distribution. The first person say the number corresponding to the distribution in front of him and tadaa: everyone but the first guy is saved. I guess this would involve calling a number higher than 1001, but yeah, it works

[@SKyrim190]

Do people HAVE to guess a number between 1 and 1001? Because the first person may "guess" the sum of all the numbers he is seeing, just to give out the information. People in front of him will be able to get the right answer by comparing to what they are seeing and keeping track of all the numbers being said. The first guy will deffinitly get it wrong, but this saves 999 people for sure

[@888SpinR]

+Luiz Sarchis That's what I initially thought too, but unfortunately mr evil genius himself has clarified that it has to be a valid hat number...so...

[@SKyrim190]

Oh...bummer...I will think of a better solution and post it latter them...

[@Noah-fn5jq]

+Luiz Sarchis He mentioned in another post that you have to use one of the available numbers. Although... I have seen a slight alteration of your solution that looses only 2 people.

[@Karlavaegen]

Another similar problem, here in my own story: Suddenly the evil and crazy emperor of Acountry wanted to play a game. So he decided to put most of his inhabitants in prison. To be exact, one hundred went to jail. The, if possible, even more evil prison warden was instructed to fulfill the emperors childish game. Every prisoner got their own cell (totally isolated from sounds and any other senses that humans can perceive), but there was one room left for amuzing. The emperor, as the warden, was sure that the prisoners wouldn't solve the intended problem, so they collected them at the courtyard and the warden said as instructed: -"Every second hour I will by random select one of you who I will put in the game room. I will leave you there for five minutes before I put you back in your own cell. I can select any of you, in any order, more than once, it's all by my random selection device. In this currently dark game room, the only possible interaction is a light switch that turns on and off the only light bulb in the room. If any one of you pitiful slags, while in the room, can confirm that every one of you one hundred have visited the room, we will let you go. If the daring person in question is wrong, you will all be shot in the head without mercy. If no one calls out, you will of course stay in your cells until you all rot. Even if it hurts, I will now give you all ten minutes to discuss how to save your worthless souls." The prisoners, many of them old, managed to escape the evil emperor and moved to Sweden happily ever after. What were their strategy?

[@jasonl7651]

Old comment but nice puzzle. The working strategy averages 2.5 years per escape so they won't be TOO old. The prisoners should put a chosen Person A in charge of the switch. Each other person only ever turns it on once if it's off, and Person A turns it off each time. The other prisoners ignore the light if it's on, or if they turned it on before. When Person A has counted 99 times the light was on they report and are all freed, see working below on the expected time this will take. The light will only turn on when someone who never turned it on is in the room and it's off. This starts fast but gets slow. 100/99 average cycles for the first one. But 100/1 average cycles for the last one. 100/99+100/98+100/99+...+100/1 = 517 time cycles of turning the light ON. The really slow part is Person A resetting the light each time. This averages 100 cycles, and has to happen 99 times. 517+99*100 = 10417 time cycles is the expected average. Or, 20834 hours, which is about 2.5 years assuming constant activity.

[@Karlavaegen]

@@jasonl7651 Im starting getting in love with you :) Nice!

[@Karlavaegen]

I't funny how binary problems can get so hard.. Have man more :)

[@FLOABName]

I love how morbid these are

[@philippwei3352]

In think 999 people can be saved, and the first person has a 50% chance to also be saved: Write out all numbers the first person can see in order while leaving two blanks at the beginning for the removed hat and the first persons hat. The two ways to place the first two hats give two different permutations that differ by a transposition, therefore one of the permutations is odd and one is even (see e.g. Wikipedia for what it means to say a permutation is odd or even). Say your hat number for the even permutation. Now everybody writes along all said numbers, adds all visible numbers and then has the choice between two permutations that again differ by a transposition. Therefore they can tell which even permutation the first person had in mind, and know their number.

[@CaseyBarbee]

For the 1001 hats problem: The person in the back sums all the numbers in front of him then performs the Mod operation. To do this, you divide the sum of all numbers in front of you by 1001. After dividing, you will have a remainder between 0 and 1000. Add 1 to this remainder to make it so it always gives you a valid hat number. We will call this number "X." The person in the back says X as his "guess," and will almost always die, but sacrifices must be made. The next person in line will see all numbers except for 3. Let's call these 3 numbers A, B, and C. He will know his number must be one of the 3 numbers. He will not know which is his own number, nor will he know which is the number of the person in the back, nor will he know which is omitted number, but using the information the person in the back has given him, he can figure out which of the three numbers is his own. To figure out his number, he sums all the numbers in front of him to get S, where S = hat numbers of person 2 + person 3 + person 4 + ... + person 998 + person 999 + person 1000 minus his own number If (S+A) Mod 1001 = X-1, that is his number, If (S+B) Mod 1001 = X-1, that is his number, and If (S+C) Mod 1001 = X-1 that is his number. He then says his own number You can repeat this process for each person. When it is someone's turn, they will know all the numbers in front of them, and they will also know the numbers of the person(s) behind them (since they said them). The only numbers that could possibly be their number are their own number, the number of the person in the back, and the omitted number. This is because every other number has either been said, or they can see the number in front of them. They can add all of the numbers said so far (except X) with all the numbers in front of them to get a new S. Repeating the step above to determine which of the 3 unknown numbers are their own. Most likely, someone in the line will have X as the number on their hat, but they cannot say X since it has already been said. The solutions for what you do if you can hear who is right/wrong and what you do if you cannot hear who is right/wrong vary slightly. In the case where you hear who dies and who lives: The person with number X can say the either the omitted number or the number of the person in the back. Everyone in front of them will hear that they gave an incorrect answer and can assume that their number was X. In this version, 2 people must die. The person in the back, and the person who has number X. In the case where you do not hear who dies or lives: They cannot say one of the other two possible numbers (the person in the back's number or the omitted number) because the people in front of them would not be able to properly calculate the sum S. Calculating S correctly is dependent on knowing all the numbers from person 2 to the person in the front, except your own, and the only way to know all the numbers of the people behind you is to assume that the number that they said was their own number. In the case that your number is X, you say the number of the person in the front of the line. For the remainder of the game, everyone in front of you will obviously know that the number you said was not your number, and can assume X was your number in their calculation of S instead of using the number you said. Since you must say the number of the person in front of the line. The person in the front of the line cannot say his own number and must die as well. In this version, 3 people must die: the person in the back, the person who has number X, and the person in the front. It is possible (although very rare) that X is equal to the number of the person in the back and everyone lives. If the person in the back has the number 1, and the number 1000 was omitted, this would be a case where everyone lives because the sum of the remaining numbers is 500,500 and (500,500 Mod 1001) + 1 = 1

[@ImAllInNow]

The solution I think Matt came up with: Assume that the hats are numbers 0 to 1000 for simplicity. The person in the back counts all the hats in front of them and computes that number modulo 1001 (their "Mod Number") and says that number. This will almost always be wrong, but it lets everyone in front of them (except 1) know what their hat number is by computing their Mod Number and figuring out the difference between that and the original Mod Number minus all the guesses behind them (The Mod Process). This works up until we get to the Unfortunate Bastard (UB) who does the Mod Process and results in the Mod Number itself. So they have the hat number that the first person had to guess. So they can't guess that number and are screwed. So they have to guess a different number. If everyone is notified when a wrong guess happens, then the UB can just guess one of the two numbers that hasn't been guessed and isn't in front of them (the unused number or the number of the person in the back). This lets everyone in front of UB know that UB's hat number was the Mod Number, so they can continue the Mod Process and all guess right. So in the end, all but 2 are saved, assuming the person in the back didn't miraculously guess correct. Now, If people aren't aware of who was correct and who was incorrect, then the UB can't guess a number that doesn't indicate to everyone else that he is wrong. The trick in this case is for UB to guess the number of the guy at the front of the line. This will let everyone in front of him know, again, that UB's hat number was the Mod Number and they can all guess correctly using the Mod Process except the second unfortunate bastard at the front of the line who has to guess one of the two unguessed numbers and know that it's wrong. So in this case, all but 3 are saved.

[@Wand2Fishes]

If you know if the people behind you were right or wrong then aren't you guaranteed to save everyone but one? There are 1000 numbers out of the distribution 1-1001, so the person at the back sees everyone else's and has 2 numbers to guess from, the one not included and the one he has. If he guesses wrongly, then everyone else knows what the number not included was, as well as the number he actually had so the rest can figure out what hat they have easily. If he guesses correctly, then the 50/50 guess goes to the next person and so on until someone gets it wrong (or everyone guesses correctly) and 999 people are guaranteed to be saved. Also, if you're allowed to say any number higher than 1001 then the first person can just say the sum of the everyone in front of him and everyone else is guaranteed to be saved even in the bonus version by just subtracting the sums of the rest.

[@bryceherdt2363]

+Wand2Fishes Nope. Say the 999th prisoner is wearing hat A, and the 1000th is wearing B and must guess B or C. If he wrongly guesses C and dies, the 999th prisoner has to guess A or B. Sure, they know C was the real missing number, but they don't know whether the 1000th prisoner saw A and failed to guess B, or saw B and failed to guess A.

[@Wand2Fishes]

You are right

[@pascaljacquemart5973]

+Wand2Fishes Nah. If Someone gets his number unused one gets sorted out but now next guy must guess between his real number and the number of the guy that lastly died. So it stays 50%50

[@TheSwiftFalcon]

Okay, so the first thought that came to mind is what everybody else is saying: The guy in the back sacrifices himself by saying the total sum in front of him, and everyone else can work out their hat number by subtraction. This works, but gives the guy in the back no chance of survival, and might be against a rule Matt forgot to mention. Remember, in the original puzzle, the prisoners could not say anything other than "white" or "black". I believe I have a solution which works around both problems, in which 999 people survive, and the last guy has a 0,1% chance of survival. Just to briefly return to the original puzzle, it was a fairly simple one, at least for a computer scientist (I actually got my degree at the university Matt was visiting). You are only allowed to say one of two things, and only the guy in the back is actually free to convey free information, which means 1 bit of data. This then obviously has to be a parity bit. In the original puzzle, the guy in the back has a 50% chance of survival, everyone else has 100%. Now, in this new variant, if you assume that the guy in the back could say any number, as many have done, you could in principle encode any information. You could for example provide the sum of what's in front of you. In principle, you could even teach everyone ASCII and encode a long text string. However, I'll assume that's not allowed, and you actually have to say a number between 1 and 1001. Here's what I believe is the key to the puzzle, which some seem to have forgotten: One random hat has been removed. If this was not the case, *everyone* could be saved, because you can work out the sum of all of the hats beforehand. However, you still know the approximate sum, within an error margin of 1000. The guy in the back just has to narrow this down, which he can do by *saying the sum he sees in front of him modulo 1001 plus 1*. This will give him a number between 1 and 1001, which has a 0,1% chance of being his own hat number. But for everyone else in front, they can now work out the sum of the remaining hats, and get their own hat number by subtraction.

[@TheSwiftFalcon]

Dang, I forgot about the limitation that you can't say the same number twice. That's what I get for trying to think before breakfast. I'm guessing I'd have to come up with a strategy which somehow involves the two missing hats the last guy sees. One of those will be on his head, so he can actually get a 50% chance of survival. I'll see if I have time later to device a coherent strategy.

[@janpokorny9710]

I think there is a solution where you can save everyone except the last one. The last one sum all numbers of hats which he can see and say that. The person in front of him do the same, but subtract his number from number of the person behind him. It can take a while but it should save everyone except the last. EDIT: Instead of saying the whole number he will say just his last three digits of that number - so he won't say invalid value

[@SyntekkTeam]

Yeah I thought of that one too but I wondered, what if the numbers need to be valid? if we use the sum then the first number will be well beyond 1000

[@bronars4627]

well idk if you are allowed to say a number above 1001 ... but if you are allowed to do that then an easier way to save everyone but one person would be to have the man in the back say the two numbers he cant see (this would be his number and the number taken out), just sepersted by 1 million. For example if he couldnt see 20 and 100 he would say the number 100 million and 20 (100,000,020). The second person would not see three numbers (for example 100, 20, and 345) and they would know that their number is the one that isnt 100 or 20, so their number would be 345. This could continue and in the end it would end up saving everyone except the first guy

[@SyntekkTeam]

+Matt Bronars hmm that's another interesting idea. I guess in a way the numerical version is easier than black and white since the first person could pretty much store limitless information in the digits of their number.

[@bronars4627]

+Arend Peter Castelein yeah, the key to solving the problem without cheating is finding a way to express the two numbers the first guy doesnt see into one number between 1 and 1001...

[@joelproko]

+Matt Bronars But one person in the line will have it wrong, because they don't have a hat...

[@mridul863]

This is the best i have- The first guy to answer can see all 999 numbers in front of him, and has 2 possible options for the number on his hat. Now, instead of guessing one of them he takes the average of the 2 numbers and communicate that. Round down if you get a fraction. Now, the first guy will die as well as the one in line whose number happened to be that average, because of the no-repeat rule. The second guy has 3 possible options but since he knows the average, he can use it to get the number on his hat. Same for the 3rd guy since he can exclude the number spoken by the previous guy. And this goes on. Now, since we round down during the average, there will be a situation where we have 2 possible combinations to get the same average. This guy gets a 50-50 chance to live. At maximum 3 people die.

[@dino130395]

f89SrzSRtIk You're welcome

[@yyny0]

+Dino Prašo 2 hard 4 me

[@bryceherdt2363]

I tweeted this answer, but I think I'll expand on it. First, the black/white hat puzzle answer saves all prisoners but one. Each prisoner alone has two options, and except for the back one, everyone can calibrate based on the first answer. In the black/white case, the prisoners answer as if the number of black hats is even. I was sure something similar could save 999.5 of the 1000 prisoners, on the basis of the second sentence of my previous paragraph. For instance, with two prisoners and three hats, you don't need to sacrifice two prisoners; the second prisoner can either see 1 and say 2, see 2 and say 3, or see 3 and say 1. But how to scale this up to three and four, or 1000 and 1001? Well, I'm glad I studied Galois theory in college. The prisoners must use the alternating group on one thousand one objects, A1001. Take a number of objects N in a starting order and scramble them. You will recall there are N! permutations, including the original order, that the objects can take. Somewhat obvious is that we can reach any permutation by swapping two objects at a time. But somewhat less obvious is that you can reach a permutation through either an even number of swaps or an odd number of swaps, but not both. If the number of swaps is odd, this is called an "odd permutation," and if it's even, this is an "even permutation." The prisoners need to assign the last hat to the warden and answer as if the 1001 hats form an even permutation. Now, since I don't always explain things in a natural order, you might be asking, "But what's an alternating group?" A group is a mathematical set of objects such that when any two are combined by a function, the result is also in the group. (A group also has an identity element, and an inverse for each element, and these are critical but that's slightly less important here.) The alternating group on, say, 1001 hats, is the set of even permutations of the hats, which can be combined by "composition," or permuting the hats one way and then the other way (by position). It's a group because performing an even number of swaps, followed by an even number of swaps, gives an even number of swaps. You know what? There are plenty of pages that explain this. Here's one: en.wikipedia.org/wiki/Parity_of_a_permutation So I'm going to stop here.

[@NerdyStarProductions]

I think another rule should be specified where the person is only allowed to guess a hat number between 1-1001 (dont recall hearing it be specified, but if it was, my mistake). If there is no restriction, then the person at the very back could simply say a very large number in which the digits from most to least significant are the numbers of the hats from the front to the back, with four 0s separating in between. So for example, if the first 3 hats are 17, 1000, 805, then the number he says would begin with 170,000,100,000,008,050,000. To decipher, the first person would keep listening to the number sequence until they hear 4 0s in a row, followed by a non-zero digit. Then they just ignore the last 4 0s in the number they heard, and that should be their hat. The next person then starts listening at the non-zero digit the last person would have stopped listening at, and so on until the end. It would take an absurdly long time to read out the number, but theoretically if everyone listens to the sequence carefully, everyone but the last person should know what their number is without knowing if the guess of the person behind them is correct or not. Of course, the very last person is guaranteed a death, but it also guarantees the survival of everyone else. But this is a pretty trivial solution, and I imagine it probably wasn't the intended direction of the solution for the problem.

[@Turing2]

I had a similar solution, coverting all the numbers to a 10-bit binary number and stringing them together, so that the last person says the resulting number. Of course that assumes that all 1000 are brilliant at mental arithmetic and can decode and parse a 10,000 bit binary number! :-) Your solution is probably more elegant.

[@Azord]

this is a bit late, and I might be incorrect, but I believe I have found a way to save all but one person in either case. The person at the back of the line can see every hat but two, and he also knows what the person in front of him sees. If the number on the second person's head is the higher of the two numbers that the second person will have to pick from, the first person will pick the highest number available to him. If the number on the second person's head is the lower of the two numbers that the second person will have to pick from, the first person will pick the lowest number available to him. The second person will see every number except for three, the missing hat, his hat, and the first persons hat. One of the two numbers will be chosen already, and there will be two remaining to choose. If the first person picked the highest number available to him, he will pick the highest number, and if the first person picked the lowest, he will pick the lowest. Every person ahead of the second person will know to not choose the number that both the first and second person skipped, and so will only have one number to choose from. The result of the previous person's result should not matter, so this should work for either solution.

[@direghostman]

The person at the very end says the sum of all the numbers in front of him. they will be wrong but now everyone in front knows their number by doing the same. the second to last person can check the sum he sees in front of him, subtract that from the number said behind him, he now knows his hat. only works if you can say numbers >1001, otherwise the end person couldn't encode the information example with 5 people and the number 4 removed. order - 3,2,5,1,6 end person (3) would say 14 second to last (2) would see only 12, so he knows his number is 2 next (5) would see only 7, but he needs 12, so he knows his number is 5 then (1) would see a 6, knowing that he needs to add up to 7, his number is 1 then the last person would know that they are 6

[@tifnatandmat]

+Tristan Raposo Umm... He can only say a hat number... Not a sum...

[@justinwhite2725]

And the first time anyone makes a tiny arithmetic error, everyone after that dies. While that does technically work, it assumes everyone is flawless at math.

[@justinwhite2725]

It also assumes the first guy is altruistic and would sac himself. With the coloured hats solution the first guy has a 50% chance either way, even if he helps the others. The first guy is more likely to take the 50% chance of guessing rather than giving an obviously wrong answer to help everyone else.

[@ndp8]

+Tristan Raposo If she or he is only allowed to say a hat number, you can just take the sum and use modulo H, where H is the number of hats. Then, the same arithmetic will work. In your example, that person would say "2" (14 % 6). The second to last would see only 12, which evaluates to 0 (12 % 6), so the hat must be "2". And onward... Sadly, the second person isn't allowed to say "2", since that's what the first person said... she must sacrifice herself, as that's the only way to save everyone else. This seems like it is a worst case, and matches what Matt hints at in his video. Secondly, if the first person is selfish, she has a 50% chance by examining all the other numbers... She knows she's either "3" or "4". In this strategy, she must be selfless and say "2". Perhaps there is a better way ... I'll keep thinking.

[@quinxorin]

+tifnatandmat Matt never said that a person isn't allowed to say a guaranteed-wrong number. He said the person is asked "what number hat are you wearing?" A person could absolutely say 105812514125, because that is indeed a number, it just would never be correct.

[@DerNesor]

the last guy takes the difference of the missing numbers, the second guy is either saved (or not if his hatnumber makes it so there are 2 ways to get the same difference like 5- 10-15) , in that case only the poor dude with the difference as a hat number dies alongside the first person. The other case I have not found out yet

[@stephenkamenar]

I solved the bonus question (not allowed to know if the person was right or wrong) while only killing 1 person AND only saying valid hat numbers. (okay actually it kills 2, but only because of your added rule that you can't say the same number twice) The dude in the back sees that 2 numbers are missing (his own and the unused hat). ALL THAT NEEDS TO HAPPEN IS FOR HIM TO COMMUNICATE THESE 2 NUMBERS! It seems impossible to communicate 2 numbers between 1 and 1001 when you're only able to say 1 number between 1 and 1001, but it is possible in this case. Simply add the 2 numbers together, and say the result. (if it's > 1001 just subtract 1001) But wait, if 26 and 24 were the missing numbers you'd say 50, and if 1001 and 50 were missing, you'd also say 50. There's actually 500 collisions here! No problem! Exactly 1 sum exists that uses 2 numbers that you can't see in front of you! As the 2nd dude, you simply find 2 numbers that sum to 50 that aren't in front of you, these are the 2 missing numbers! The 2nd dude now knows his own number and the rest is obvious!

[@justinwhite2725]

+Farzher It doesn't work for anyone after the 2nd guy to answer. For example if '50' is said. If 10, 40, 11, 39, 12, 38, 13, 37... are behind you there are too many possibilities. And you'd have to have an insanely good memory to cross them off your list as they get called. Like most of these answers - it works only for entities of perfect logic and perfect memory. Humans are not such entities.

[@undergroundo]

+Justin White Yes, this kind of puzzles assumes that people have perfect memories. Or, you know, they use a pen. But if they do rememebr, then Farsher's solution works out (I actually solved it the exact same way)

[@undergroundo]

+leinad55991 That's why you cycle the numbers ;) 1002 becomes 1, 1003 becomes 2, and so forth

[@justinwhite2725]

If they are given pens, then it wouldn't be so bad, but still pretty bad. We are literally talking about 1000 people and if one of those critical numbers that sum to the number given are off by 1 the whole thing falls apart for everyone else. I expect there would be some record of numbers already said so you know what numbers can't be said again.

[@undergroundo]

True. It's a good thing that these puzzles are not actually carried out in real life!

[@aesa1990]

This channel really makes it inconvenient to find the answer. I needed some self control. Thank you :)

[@jaywalker2k387]

There is an easy way to save everyone but the first guy. Simply look at all the hats in front of you. If there is an even amount of black hats, say black. If there is an odd amount of black hats, say white. The first guy is doomed to his 50/50 unfortunately, but all others are guaranteed their life. If the person behind you sees an odd number of black hats and you see an even amount, that means your hat is black. If they see an odd amount and you also see an odd amount, your hat is white. Which color you count and which color corresponds to odd and even can be whatever you want. This leaves a 50 percent chance to save everyone, and a 50 percent chance to save all but the first, and thus gives you the best odds.

[@jaywalker2k387]

Also, for the purposes of this method, zero is considered even.

[@jaywalker2k387]

and i have absolutely no idea for the second one :/

[@janpokorny9710]

+Skywalker 2000 TED - ed?

[@georg1783]

+Skywalker 2000 isn't there a random distribution off hats, because your solution works, if there are 3 black and 3 white hats, but thats not always the case?

[@justinwhite2725]

That only works if there are an even number of each hat. However he said they could all be the same colour, or all but 1 could be the same color, so that doesn't work. The way I would do the colour one (and save everyone but the first one) would be that the first guy says the colour in front. The next person would repeat that, but the will say it with a question after it if it is Not the sake as the person in front of them, and in a firm definite tone if it matches the person in front. Each other person then repeats if the person behind was firm and says the opposite if the person behind had a questioning voice. I have no idea on the 1001 hats variation - at least not one where I had to rely on everyone to be math geniuses (in which case everyone would be dead with an average sampling of the population)

[@LucasGalfaso]

For the second problem, there is a way that you always save 999 people and the last one has a 50-50 chance. Think that the hat that the first person has is position 1, the second is position 2 and so on until position 1000. Then make the assumption that the remaining hat is at position 1001, and the last person sees all but 2 hats. The last person will look at all the hats and their position and pick, within the remaining 2 hat numbers, the one that makes the parity of the permutation even. There is only one hat that makes the permutation even. From that point on, each person will pick within the 2 possible hat numbers (if you remove the ones that this person can see and the ones that were already said) the hat number that keeps the permutation even. Again, there is only one possibility. Given that there is only one possibility and the last person pick the hat number so the permutation is even, then everybody but the last person will say the correct hat number. This way, 999 people always say the right hat number and the last one has a 50-50 chance.

[@TheRMeerkerk]

+Lucas Mirelmann What if the person in the back has to choose between two even numbered hats and the one in front of him has an even numbered hat?

[@LucasGalfaso]

+TheRMeerkerk every person needs to pick the hat that keeps the parity of the permutation even (en.wikipedia.org/wiki/Parity_of_a_permutation) this is not related in any form to even or odd hat numbers.

[@TheRMeerkerk]

Lucas Mirelmann In that case you're probably right. I was thinking in a very similar way (with a bit of a workaround), except that I didn't knew anything about parities of permutations. The thing I thought of was deciding on a sequence like 1, 2, 3, ..., 1001. Then rotate 3 numbers in the sequence, until you get a sequence of hats that matches the ones you see (and heard). Then the new sequence will reveal the hat number that you should shout.

[@allaeor]

In the Chinese language the same set of syllables can mean very different things if the speaker says it with an upward or downward infliction. This principle can be used in a simple solution to the first variant of the puzzle. The first prisoner will have to valiantly take a 50/50 at life, guessing a random color, however to indicate that the prisoner in front of him has a white hat, he'll say "white" or "black" with an upward infliction, and to indicate that the hat of the prisoner in front of him is black, he'll say "white" or "black" with a downward infliction. This goes on and on down the line, and presumably the executioner won't wise up to the prisoners' binary system of communication, and everyone except the last prisoner will certainly survive. You could apply this same line of thinking to the second variation. Again, the first prisoner has a 50/50. They look at all of the hats in front of them, take a guess at one of two hats missing from the set of hats in front of them, and then somewhat complexly sing their guess in an array of high and low notes, meant to be a melodic representation, in binary, of the number of the hat in front of them. As with pretty much any of the solutions to this puzzle, if someone messes up, it could be bad news for them, or the person in front of them, but since each person is only responsible for their own life, and the life of the person in front of them, a single mistake has few consequences. This solution does require each person to know binary, and to be able to say their answer with information cleverly encrypted into their answer, but they'll have had all night to practice, and their life depends on it! I realize that this kind of takes the math element out of this puzzle which is clearly meant to have a math based solution, but I quite like solutions which require craftily encrypting information as messages to the other prisoners. In a real life instance of this unrealistic situation, coming up with a "simplistic" plan would probably yield the best outcome. Alternatively, all 1000 prisoners could just gang up on the executioner and guards, but where's the fun in that?

[@12tone]

+allaeor You could do it simpler than that. At each point, the combination of the numbers you can see and the numbers you've heard covers 999 of the 1001 possible options, so from that information alone you know there are only two possibilities for you. So I, as the person before you, can figure out exactly which two numbers you are going to be choosing from, then use my inflection to tell you whether to guess the higher or the lower one. Of course, this is clearly outside the intent of the problem, but still, a clever solution.

[@rasowa2958]

A strategy similar to white-hat/black-hat puzzle that saves every second person with 50% chance for the rest is actually very easy. From the two numbers the first person doesn't see he says number that is prior* to the number on the person in front of him. He has 50-50 to live. The next person is saved be saying this of two numbers he doesn't see that is next* to the number the previous person said. Then the strategy is repeated by another pair of prisoners. *) by prior/next I mean in ascending cyclical order, e.g. for numbers 729, 114, 850, the order is: 114->729->850->114

[@almaraNZ]

Even with the correct link with the capical i the answer video isn't accessible. Tragic.

[@OnEiNsAnEmOtHeRfUcKa]

Prisoner #1 states the combined value of all hats he can see, then dies. Prisoner #2 tallies value of remaining hats, subtracts difference, states number of own hat. Repeat this 999 more times, only one casualty. gg maniacal dictator gg

[@thecuymr]

He stated in the coments that you have to say a number between 1 and 1001

[@WhovianMinecrafter]

the first person says the total of all of the others, the rest is just subtracting what you have heard and what you see.

[@danielgordon10]

My solution as well. Saves all but one person guaranteed. I'd say that's better than 3 maybes.

[@LuciferXNero]

+WhovianMinecrafter With that method everyone would die ..

[@LuciferXNero]

+WhovianMinecrafter Let's say the first person has the number 2. He then says the sum of all the others in front of him. Then he's killed. The next person now knows that the person behind him had the number 2. But he still has no clue what his own number is. *So first of all it isn't allowed to say numbers over 1001 - so everybody dies. *Second of all using your method, the people asked what number they are will only know which number is behind them, so everyone would not be able to say their number. * Third of all you are only allowed to say 1 number, so how is it possible for each individual to say their own number AND the sum of all the people in front of them? I'm sorry to say, but that isn't a solution at all :)

[@LarryAszune]

+LuciferXNero He meant that the guy in the back says the total sum of all people and gets killed, the next person takes that sum and subtract everyone in front of him from that number. The person after that would take the sum, subtract the person's number behind him and all the people in front, and on like that.

[@echaen1707]

+LuciferXNero For your first point, that's not a rule at all. For your second and third points, the 2nd person can see all the hats in front of him, and knows the total of all the hats in front of the guy behind him. He just finds the difference between the sum of hats he can see and the number he knows remains, then says that number. The next person takes the big number the first guy said and subtracts all the hats in front of him AND all the hats which were spoken aloud. This strategy works 100% of the time and saves 999 people guaranteed even if you can't hear whether or not they were correct. The moral dilemma is that you're absolutely and totally condemning the person at the back of the line to death. No chance involved, but they save everyone else in the line. Deep stuff.

[@DraconianEmpath]

by the way, thanks for not putting the solution in the video. I hadn't heard of the prisoners in hats puzzle before and I just had a jolly hour with it rolling around in the back of my head before solving it. thanks mate!

[@Ins4n1ty_]

I either didn't get the problem right, or it is so obvious it's actually easier than the black/white one...

[@henrywicaksono8006]

Im thinking the same thing

[@logical-functionsmodel9364]

The 1st puzzle: 1= black 2= white left corresponds to the front right corresponds to the back With these rules in place, the back person says the appropriate number and a color of his/her/they choice. All save one are "guaranteed" to survive, (unless the person is trying to enact revenge, etc.)

[@888SpinR]

For the first puzzle you can encode information in black or white, obviously you can't say the number of hats you see, but you can say whether the number of black/white hats (decide beforehand) is odd or even. If the first guy sees an even number of white hats, he shouts white. 50/50 for him. The next guy either sees an even number of white hats, in which case he knows he's black, or an odd number of white hats, in which case he would know he's white. And so on.

[@DB-nr6fo]

TED? :D

[@830927mjki]

+888SpinR 1 - i see 3 white hats. BLACK 2 - i see 3 white hats - BLACK 3 - i see 2 white hats - WHITE 4 - i see 1 white hat - WHITE 5 - i see 1 white hat - BLACK 6 - WHITE this works but it relys on the people behind you not screwing up

[@888SpinR]

john kirkham That's true, but isn't it the same with all puzzles involving hypothetical people?

[@888SpinR]

David Bednarczyk Yep, I just watched it the day before he posted this video! (Coincidence, I think not!). But I managed to figure out the solution, although it took quite a while.

[@lucasbrelivet5238]

The first one sees all the numbers except his and the one that's removed so he'll definitely say one of those since he wants a chance to survive. No matter if he lives or dies, the second one is left with guessing between his number and the number that wasn't said before. And this will go on all the way down with everyone having a 50% chance of survival. If they want to use any other strategy, they would need selfless prisoners willing to say a number they know they don't have to give more information to the others. They could also give more information by following a rule like always taking the smaller one between two numbers, giving a bit more info without sacrificing themselves, but the efficiency of that would depend on the order of the numbers.

[@Witkowski_Cam]

The person at the back knows 999/1001 of the numbers aren't his, so he has a 50/50 chance of surviving. The second person will either hear the last be shot, and know that he picked the number nobody has, or if the last guy survives then he is left with the same 50/50 scenario, since he knows 998 numbers in front of him aren't his, and that the number previously called isn't. This way only one person will die.

[@adrianroed2178]

nope, the second person will know 998 numbers out of 1001 in front of him , and one more that were mentioned behind him, meaning he have the same 999/1001 chance, and this will continue all the way down the line :(

[@MagicGonads]

+MAGiK You can't hear if someone's right or wrong.

[@sjorskauderer6593]

+Magic Gonads no that was the bonus

[@castletheperson]

+MAGiK That's the solution I came up with also

[@MagicGonads]

Castle Kerr It isn't a solution though, refer to adrian roed's comment. Second person knows 998/1000, so he has a 1/2 chance of being wrong.

[@kushal]

Answer to the general question: In these problems max of people saved in worst case is n-1 Plan: The person standing last (who has to make first call) will count the number of white caps in front of him. If the count is even number, he calls white, if it is a odd number, he calls black. Let us say he calls white. When the next number counts the white caps if the count is even then he came to know that he wear black cap, otherwise white cap. Same logic goes up to 1st person. Another Answer: Let us define Black cap=0,White cap=1 Now take any sequence and set the binary representation of the caps....like 1100110110 for WWBBWWBWWB. Now when the jailor asked the last prisoner he XOR-ed all the bits before him....i.e. 1(XOR)0(XOR)0(XOR)1(XOR)1(XOR)0(XOR)1(XOR)1(XOR)0=1 He then tells the final result '1'. The next prisoner then XOR's the reverse stating from the first up to his front one. The result that he gets is the color of his cap. Similarly the prisoners in front of them do the same with the final result told by the last prisoner.

[@averageaf4321]

The answer is obvious, there is 1000 of you and one of him. Need I say more :P

[@Bobdowntheroadshow]

There's actually 1001 hats, therefore the first person in theory has a 50% chance of getting it right or wrong.

[@scatological2538]

@@Bobdowntheroadshow I think you missed the joke.

[@claw0100]

Guaranteed to save everyone but 1 person, with a 50/50 chance or them living. The last person waits a time equal to the persons hat in front before saying their number; An example using 5 people a) 2 b) 5 c) 3 d) 6 e) 1 Person e) can guess 1 or 4, 50/50 chance, before he guess this, they wait 6 seconds Person d) noticed person e wait 6 seconds so they know that their hat is number 6, they wait 3 seconds before saying '6' Person c) waits 5 seconds before saying '3' Person b) waits 2 seconds before saying '5' Person a) says 2 No number repeated, everyone is guaranteed to be saved with the exception of the first guesser.

[@MegaYhu]

My favorite solution.

[@brianroberts9270]

So if you're up and the two numbers to choose from are 789 and 788, you know the difference after that many seconds? Viable if people are really good at counting, which would get harder the more syllables you have in your number

[@elzearcontelly2651]

The first one say BLACK if there's an even number of black hats, and WHITE if there's an odd even number of black hats. Then, every prisoner can guess what hat he has when the one before said his answer.

[@moritz639]

Nice

[@sillvvasensei]

+Elzear Contelly This is my solution also. And it would give you a 50-50 shot of saving everyone because only the person in back has a 50-50 shot of being right. Everyone else is guaranteed to live as long as they can count. Back ----------------------------------------------> Front B B W B W W B W W B B W B W W B B W B Person in back counts 9 black hats in front of him, he calls White and dies B W B W W B W W B B W B W W B B W B Next person counts an even number of black hats in front of him, but knows that the person behind him counted an odd number of black hats. So he calls BLACK. W B W W B W W B B W B W W B B W B Because the number of black hats has been reduced by one, the next person knows there should be an even number of black hats and there is. So he calls WHITE. B W W B W W B B W B W W B B W B There should still be an even number of black hats, but this person counts an odd number, so he calls BLACK. W W B W W B B W B W W B B W B There should be an odd number of black hats, and there is so this person calls WHITE. W B W W B B W B W W B B W B There should be an odd number of black hats, and there is so this person calls WHITE. B W W B B W B W W B B W B There should be an odd number of black hats, and there is an even number so this person calls BLACK. etc.

[@carljaibearbear2568]

Ted-Ed? I watched that one too!

[@lucaspardo5016]

Ted-Ed

[@Pablo4949]

As you were talking about the mathsjam website, I was thinking there are probably not too many Americans would either know about "maths" or would remember it when typing a url later. Good work with the math-jam link! No mathsjams in my area, sadly. Sidenote, I'm American and I prefer maths, for what that is worth.

[@jimmypge]

+Pablo blood traitor

[@BunniBuu]

The "unlisted" video comes up as "this video is unavailable" :(

[@BrotherAlpha]

+Bunni-chan f89SrzSRtIk The second to last letter is a capital I, not a lower case l. Bad font choice.

[@juchemz]

+Bunni-chan Its a capital i, not an L

[@Jivvi]

+juchem69z that still doesn't work.

[@otakuribo]

+BrotherAlpha I happen to think it's a nice Gothic sans-serif font, very readable; just not the most unambiguous font for displaying code like a URL. :/ We're translating computer language to human language back to computer language, and that little bit gets lost in translation. #shrug

[@adambaker2190]

+Bunni-chan I think you got lower case L confused with capital i.

[@Your2ndPlanB]

I've heard of another really cool variation: Instead of n prisoners, the mastermind has this time (through cloning or something) managed to imprison COUNTABLY INFINITE prisoners. He tells them that he will do the same thing to them as in the basic version (i.e., put them in a line (that's infinitely long), facing one direction, and asking them the colour of their hat, which can be either black or white). The prisoners, however, are not normal people: They can see infinitely far (so they can see the hats of everyone in front of them), they can hear infinitely far back (so they can hear what the people behind them are saying), and finally: They can apply the axiom of choice. How many prisoners can be saved? How many if there are countably infinite possible colours of hats?

[@undergroundo]

Only TWO have to die, EVEN of no one can hear the outcome of the guesses. SPOLIER ALERT: (Note: I do it with 1000 hats instead of 1001 for clarity) Prisioner 1 can see every sinlge hat except for two; the one he is wearing and the unused one. Let's call these, "The Primordial Pair". He knows that his hat must be one of those two options, but beeing the great sport that he is, he sacrifices himself, and instead of taking a 50% chance of living, and calling out a number from the Primordial Pair, he calls instead the SUM of theese two. "WAIT!"--I hear yuo say--"What if the sum goes boyond 1000?". For which I would answer, "Fair point". But the solution is simple; you "loop" it by substracting 1000. So, if the numbers are 300 and 400, the sum is 700. But, if the numbers are 900 and 200, the answer is 100 (900 + 200 = 1100; 1100 - 1000 = 100. Let's call this number "The Primordial Sum". Now, P2 started the game with similar information, except that he had three possible options. However, he can figure out the numbers on the Primordial Pair, because out of three different numbers, only 2 would be able to add up to the Primordial Sum. Even though, a Primordial Sum of 100 could mean that the numbers add up to either 100 or 1100, there will be only 2 numbers out of the 3 options that can add up to any of those totals. Thus he can eliminate those two options, and call out confidently the remaining one. P3, started with four options, but when P2 said his number, he eliminated it from his list of options, leaving him with the exact same options that P2 started with, so he follows the same reasoning. Eventually, there will be some unlucky bastard whose number happens to match the Primordial Sum, which was already used at the very begining of the game. Since he can't say his number again he simply says one of the numbers in the Primordial Pair. He is, therefor, the second person to die. All of the rest can follow the same rules and live.

[@justinwhite2725]

+Cesar Coll Assumes all humans have eidetic memory and can mentally 'cross off' all the combinations that make the primordial sum. Perfect memory is not a parameter given in the riddle, but a random set of 1000 prisoners.

[@mrphlip]

+Cesar Coll That's very similar to what I came up with, but it breaks down when you consider the people in _front_ of the person who can't guess their own hat number, because it's what the first prisoner guessed. For the sake of argument, say that P1 says "123" (and dies), and then P300 is wearing hat 123. P2 through P299 deduce their hats as you describe, then it's P300's turn, and they realise their hat is 123 and they're not allowed to guess it. So, they guess one of your two primordial hats, and die. Now, if P301 knows that P300 died, they know that this could only be because P300's hat said 123 and they were forced to improvise. So they can still reconstruct the same knowledge of everyone's hat but their own, and work from there. But if P301 doesn't know that P300 died, then they're in trouble. Because now they have this list of 3 possibilities for their hat, but instead of being the primordial pair and their own hat number, instead it's _half_ of the primordial pair, their own hat number, and 123. They can no longer tell their hat number apart from the half of the primordial pair that's left.

[@Gussi-92]

+Justin White If he does it with 1000 hats and 1000 people having eidetic memories, then not even one of them dies, since each person sees 999 numbers (999-n numbers in front of them + n numbers already crossed off by the people behind them), so they have the missing number.

[@olivierjeannin6925]

+Cesar Coll Nice suggestion, but... If I try to reformulate your suggestion : -We have 999 prisoners P1, P2, P3, ... , P999 (P1 being the first to speak) - one hat has been removed, with the number we can name A -P1 sees all 998 other prisoners, and their numbers, so he sacrifices, and say loudly the sum of the primordial pair (or 1+2+3+...+999 (=999*1000/2) minus the sum of all numbers he sees on hats), modulo 1000 (let's call S that number). Let's name B the number on P1's hat (S=A+B). -At this point, the so-called "unlucky bastard" prisoner is determined (the one with S on his hat), let's call him Pu (he is at the position u in the line) -For the following prisoner Pi (i between 2 and u-1), they will see 999-i hats in front, and ear i - 2 (himself and P1) good guesses, so among the 1000 possibilities, only 1000-(999-i)-(i-2)=3 remains (A, B and Pi's number). Among this 3 numbers, the two forming the Primordial pair can be identified (their sum is S), so Pi can loudly say the leaving one, being sure it is the right one -Then come prisoner Pu, wearing hat no S. Same as previously, he will identify 3 numbers, the Primordial pair and his number (A, B and S). Then he sees the problem : he is the chosen one, the unlucky bastard, as he can't say "S". So he says A, or B, no matter what, he's dead from the beginning... BUT - For the following prisoners Pi, i between U+1 and 999, they will also identify 3 numbers, but it will not any more be A, B and Pi's number, as Pu said A or B. The 3 numbers are A or B (the one that Pu didn't say), Pi's number, and S. Pi understand Pu is behind, not in front of him, but how can Pi guess his number ??? He has to choose between two numbers (he knows S can't be his number), but he as no clue...

[@Pantoolermore]

+Cesar Coll if the numbers are 49 and 51 he also has to call out 100 so its not very consistent

[@hamsandwich8181]

With the original everyone but the person at the back can know their colour, if for example before they guess they tap their foot once for black or twice for white to signify the colour of the person in front of them.

[@KaktitsMartins]

Whose bright idea was to make the letter "l" the same as, well, letter "I". /Facepalm

[@quacking.duck.3243]

The capital letter I (i) is actually shorter than the lowercase l (L) :P but yeah it's annoying when you're copying links.

[@KaktitsMartins]

+Duck Hah, but in the link, in the video, the picture version, the "i" as long as it can be, so it is even more confusing :D

[@AlfrescosEmporium]

As far as I am aware based in what was said, the rules were you are not allowed to say a number already been said. therefore implying that other forms of communication are not invalid in which case you could save everyone expect the first person. you could something such as if the person in front has 851 on their hat, you tap them 8 times on the left and once in the right for a break in value, then 5 on the left and 1 in the right and then 1 on the left to imply 851. This would be viable because they had time to plan this form of communication between them before lining up and getting hats.

[@Luredreier]

Yikes, I've tried all sort of variants of "f80SrzSRtIk" and I still can't get the video... :-/

[@JROwensPhotos]

+Luredreier f89, not f90, but I'm guessing that's just a typo in the comment, not your URL attempts; more likely, second to last character is uppercase 'i', not lowercase 'L'.

[@Luredreier]

+Randy Owens I didn't write 90, I wrote 80, but yeah, I didn't notice that letter... Thanks. =)

[@Evildaddy911]

The first guesser can look down the line, taking note of whichever 2 hats he does not see. He can deliver that information to everybody else in the format of "X * 1000 + Y". The 2nd guesser can eliminate those 2 options, leaving the 3rd possibility to be certain. That goes down the line, sacrificing 1 to save the other 999.

[@Empire526]

4:08 This video is private. Go home.

[@PsyKosh]

I can save all but two even in the case where the prisoners don't know if the answers they heard are correct or not: The prisoner in the back bitwise xors together all the numbers they can see. Then the next prisoner xors that with their xor of all the prisoners ahead of them to get the value of their own hat. This proceeds with each prisoner xoring together all the values they hear said behind them with all the values they see ahead of them. The two prisoners that might not survive are the first prisoner and a prisoner who has a hat that happens to match what the initial xor value stated by the first prisoner was. This solution is essentially a solution for the black and white hats version being run in "parallel" for the number of bits in the numbers, as if instead of a single hat with a number, each prisoner got many black and white hats in a particular order. And was wearing all of them simultaneously. In a stack. You know what I mean.

[@JooJingleTHISISLEGIT]

Person in back: Clap out the person's hat number in binary directly in front of you. Everyone else: Say your number then clap the person's in front of you out. Only the person in the very back dies.

[@EddoWagt]

Probably not everyone knows binary

[@roderik1990]

+Joo Jingle The warden is displeased at your blatant attempt at breaking the rules by passing along information. Everyone will be executed.

[@JooJingleTHISISLEGIT]

You could use urine, right? So everyone drinks tons of water, presses up against the person in front of them, and pees in binary what the number is on the hat... xD Actually maybe not...

[@Theraot]

+Joo Jingle Just draw the number of the one in front of you in the back of their hand

[@JooJingleTHISISLEGIT]

***** No cause' the warden would notice that.

[@bobrik14]

greetings from Mathsjam in trondheim! It was awesome meeting up with you and enjoying some really challenging mathematics!

[@Noah-fn5jq]

I think I can save all except (possibly) 3 in the numbered - not-knowing-if-the-previous-person-died variation. The first person sums the "missing" numbers (his own and the removed one), call it x. Then he calculates (x mod 1001) + 1 this will give him a number between 1 and 1001... so he can say it. Note that this will be neither of the missing numbers... so (s)he will die. Everyone else will know the original two numbers though by finding which of the 3 in question (truly missing, the first person's, and their own) fit the original calculation. Therefore they can pick their own every time. There will be one other person to die (person with the answer of the original calculation) and they just need to say the last person's number.... so they will die and the last person will as well. :( Please check my math. Edit: Apologies to all the people that made a clone post of... I posted this before reading too far into the comments.

[@ImAllInNow]

+noah schaefferkoetter yep, this is what I came up with too.

[@goininXIV]

+noah schaefferkoetter I might well be wrong, but since the two original missing numbers are known, couldn't the person who's number was said as the clue say one of the two original missing numbers (they themselves haven't been said yet, only their sum), thus saving all but two people?.

[@Noah-fn5jq]

goininXIV I almost got caught in this trap too... the problem is that the original two numbers are only known BECAUSE they haven't been said. Once they are said then it is a guessing game for everyone else. For the sake of argument, think of the last person: If we use your approach then the hint might be 6 and the two "missing numbers" might be 1 and 2. Then the 2nd person to die (unknown) could have said either 5 or 4. Since we don't know this we don't know which missing number completes the hint. Hope this makes sense.

[@qc1okay]

+noah schaefferkoetter I just now posted a full solution, very similar to yours, bettering the solution claimed at the end of the video.

[@Noah-fn5jq]

qc1okay Thanks for the shout out in your post... I did respond with a concern.

[@Jumpyluff]

That's a capital i in the URL btw.

[@starwarsjk99]

Wait can you say a number that is not a hat number? I wasn't sure about that rule. Here is one possibility if you are allowed to say a number that is not a hat number. I am not sure if this rule is there but if you are allowed to then here is a solution that saves everyone except the last man: The last man has 1000 people in front of him along with 999 hats. 2 hats are not in front of him. He takes those two numbers. Everyone generates a list of the first 1000 prime numbers. If the 2 missing hat numbers were a and b, the ath and bth prime numbers are selected. These primes are multiplied to get a unique co-prime number from these two primes. He screams this number out. He is executed since this number is probably not a hat number. (Noble sacrifice). Everyone factorises this number to generate the two hats that are not in the list. They are left with the list of all possible hat numbers. The second last prisoner works out which hat is missing from the list, which is his own hat. Then the next prisoner removes this number from the list, therefore working out his hat number. etc.

[@Beat105k]

+jk991234 Or the last guy just screams the sum of all the hats in front of him, so the second prisoner just subtracts the sum of all the hats in front of him from this answer and knows his hat number, the third guy subtracts the (sum of all the hats in front of him + the last number called) and so on. Seems simpler to me. But unfortunatly you're only allowed to call out any integer from 1-1001.

[@netserivry5561]

here's how the strategy goes: The first person knows that his hat is one of the 2 numbers he doesn't see on any of the hats in front of them, and they guess which one it is. If they get it wrong, the person right in front of them knows he has 2 possible numbers, one of which is his own and the other is the first person's number. They pick one, and so on. If the first person got it right, however, the 2nd person's possibilities are either his own number or the unused number. in this case, too, he just picks one randomly. this way, each of them gets a 50% chance to live. Also, you could get around the rule that says that you can't say a number that have already been used by simply having each odd one say the number before that of the person in front of them, so that technically they won't use the same number, but that can get confusing after a while.

[@vividvoidgirl2760]

I'm pretty sure I've managed a 50% chance between total deaths of 0 or 1. The first prisoner works out which two numbers are missing, picks one of them at random (giving them 50% chance of death) and repeats it as many times as the number on the next prisoner's hat. The next prisoner then knows their number and says it as many times as the next prisoner's number, and so on. If you really wanted to force no repetitions at all, you train everyone to have pitch perfect voice and hearing. If you agree on a value for the pitch of zero, you can then define jumps in pitch as numbers and simply call out your number in the correct pitch for the next persons number. Pitch perfect too hard? Simply make saying your number last for as many seconds (or portions thereof) as the next person's number. I kinda feel like I broke it =(

[@frisosmit8920]

yeah, you broke it

[@frisosmit8920]

I like you

[@louiswouters71]

+Himinow But the first part of your comment is completely correct. You can definitely save 999 and maybe the last one as well with pure logic. It has al got to do with the 14-15 puzzle and permutations.

[@Gewooneengamers]

today i am going to the Mathematical Olympiad of the nl. i am one of the last 1002. your vids surely helped me get to understand maths puzzels etc thanks

[@Nimblewright1992]

What number is your hat?

[@Gewooneengamers]

+Nimble hat?

[@LillianWinterAnimations]

I think I have a solution with the colored hats that can CERTAINLY save all prisoners but the prisoner in the back of the line (who has a 50/50 chance) Let's take prisoner n. Prisoner n declares the color of their own hat, and communicates the color of that hat in front of them by saying it loudly, or softly. If prisoner n+1 has a white hat, prisoner n will say the color of their own hat loudly. If prisoner n+1 has a black hat, prisoner n will say the color of their own hat softly. Prisoner 1 will not be told what hat they have, becasue there is NO prisoner behind them to communicate it to them, HOWEVER all others will be able to survive with certainty.

[@LillianWinterAnimations]

***** That's fair. In the traditional logic sense I'd be using the every-other approach.

[@shaikhmullah-ud-din1964]

N has no idea what his hat's color is. Failed logic ab initio.

[@marcinkozlowski]

You've got N hats (and N-1 people). The last person says the sum of all numbers in front of him modulo N + 1 (and is promptly executed, as it's not his number). Every person thereafter needs to solve: find x between 1 and N such that the sum of all numbers I see and all the numbers said before, but for the first person plus x modulo N + 1 is what the first person said - which has a single solution.

[@MrID36]

I like to think outside the box and have devised a much easier solution than Matt's. The prisoner at the back doesn't know his/her own color so he/she says any color, but they say it using either a high or low pitched voice to signify that the person in front has either a white or black hat. The next person then repeats this process calling out their own hat color in either high-pitched or low-pitched voice.

[@XavierXonora]

+MrID36 Matt knows the proper solution lol. Yours is OK but extremely suspicious. The solution is this. If you see an even number of black hats, you say black. If you see an odd number, you say white. The person in front of you can extrapolate that answer and guess their hat. So if the number is odd for the first guy and still odd for the second, that must mean their hat is white, but if it's even, their hat must be black.

[@curtismoore4347]

+Anthony Paull The coding of odd and even is only performed by the first person. Everyone else just says the color of their hat.

[@XavierXonora]

Curtis Moore Yeah that's what I said isn't it?

[@MaxWattage]

I'm not a professional mathematician, but I think I have a solution (with no cheating!) which would save everybody but one most of the time, but there is some risk involved. The first person can see all the numbers in front of him, except two. These are his own hat's number and the missing hat's number. His task is to somehow convey both those numbers to the second guy in the queue, but only by only saying one number between 1 and 1001. The first guy can do this because both he and the second guy can see an extra shared source of information, namely the long sequence of hats in front of both of them and can use that to help encode the information in his answer. Lets say the two unknown hat numbers to convey are the set {X, Y}. The first guy adds one to each of those hat numbers to give the set {(X+1), (Y+1)}. The hats with numbers (X+1) and (Y+1) will be present somewhere in the queue ahead of him. The first guy then looks down the row of people ahead of him and finds the two people with those hat numbers and notes their positions in the queue. These can be denoted as queue positions Px and Py. He then says the difference between these queue positions as his answer, i.e. |Px-Py|. The first guy is then sacrificed (to save the rest), as the number |Px-Py| is not (generally) his own hat number. The second guy in the line now has the problem that he has three unknown numbers, his hat's number, the first guy's hat number, and the missing hat's number. These are the set of hat numbers {X, Y, Z}. (in no particular order) He does however know that those 3 numbers aren't any of the 997 numbers in front of him, so he knows what the three numbers are, but not which one of {X, Y, Z} is his own hat's number. He also knows the clue number |Px-Py| given to him by the (deceased) first guy, and that the first guy's set of unknowns {X,Y} is a subset of his set of unknowns {X,Y,Z}. Based on this |Px-Py| information, he looks at all the pairs of people ahead of him in the queue who are spaced |Px-Py| people apart in the queue, and notes their hat numbers. He then subtracts 1 from each of the hat numbers in each pair to give 'n' candidate solutions {Xn,Yn}. If one of those candidate solution for {X,Y} is found to be a subset of {X,Y,Z}, then the second guy then knows {X,Y,Z}, and hence Z, which is his own hat number. He can then call out his own hat number and be saved. The third guy in the line can now do the same calculation as the second guy, but he now knows the second guy's hat number so can exclude the second guy's number from his calculation. Thus the third guy's chance of survival is also high, and so on. It is assumed that people much further down the queue can remember all the previous hat numbers that have been shouted out and their order, so they can still do the calculation even if the people in positions Px and Py were behind them in the queue and have already left.