# Numbered hats, Warden and Maths

You are one of 4 prisoners. Tomorrow will be a deciding day: the warden has told you and your cellmates that you can all go free, or all be executed, depending on how you answer tomorrow's challenge. He was kind enough to let you and your cellmates plan ahead a strategy. Tomorrow's challenge goes as follows:

Each of you will be given a hat with a number. You will see your cellmates' hat numbers, but not your own. Each cellmate's hat will have a unique number (no duplicates). You don't know how small or big the numbers might be, but they will be integer numbers greater than 0. You will not be allowed to communicate when the hats are put in place.

You will be given a sheet of paper in which you can write a number, and only a number - no punctuation or letters allowed. The warden will rewrite the number in his own handwriting, and remove zeroes to the left.

Then, he will collect those numbers, scramble them and redistribute, such that no prisoner gets their own written number back. You may all go free if, and only if, you and your cellmates guess your own hat's number.

Can you figure out a strategy which guarantees that each prisoner can guess their own hat's number?

Note: I don't have an answer in mind. I'll keep trying to figure out this puzzle alongside.

• Wasn't there a Khan Academy video like ths? – North Feb 23 '18 at 14:56
• This is the video: youtube.com/watch?v=N5vJSNXPEwA – North Feb 23 '18 at 14:57
• Can we pass notes while the warden is distracted by rewriting all the numbers? ;) – Trevor Powell Feb 24 '18 at 1:29
• I personally wouldn't risk being executed earlier by not being too careful :P – HugoBDesigner Feb 24 '18 at 3:46

Sure, it's perfectly doable.

Encode all the other numbers you see in binary and separate them by the number 2. Once you get someone else's paper, find the number you didn't see: that is your hat. (You can also identify whose paper it is, too!)

• Remember that the warden might remove zeroes to the left, but this strategy can still be salvaged ;) – HugoBDesigner Feb 23 '18 at 13:05
• @HugoBDesigner All positive binary numbers start with 1, so that shouldn't be a problem. – Deusovi Feb 23 '18 at 13:06
• Right, oversight on my end. That is a great strategy, I might accept it in 24 hours. Nice job getting it so quickly! – HugoBDesigner Feb 23 '18 at 13:08
• Binary again?!! Can't you just use Octals and use 8 or 9 as separator? – ibrahim mahrir Feb 23 '18 at 16:05
• @ibrahimmahrir Sure, why not? I was originally going to say "use base 9, and use 9 as a separator". But binary is more well-known, I think (and it shows how much freedom you have in this question). – Deusovi Feb 23 '18 at 16:08

When you receive a paper, you can see the three hats of your three friends and their numbers $a,b,c$ ; let's say they are $3$, $4$ and $8$.
Then the number you write down on the paper is $p_a*p_b*p_c$, where $p_n$ is the $n$-th prime number ($2,3,5,7,11$...). In our example, $p_3=5, p_4=7, p_8=19$, so you write $5*7*19=665$.
Everyone proceeds in the same way. When you receive a paper with a number $N$, (say, $N=1045$), $N$ will have exactly three prime dividers (here, $5$, $11$ and $19$), leading you to three possible hat-numbers (here, $3$, $5$ and $8$). Two of those numbers you have seen by yourself, the third one is yours.
In our example, your hat shows number $5$.

Everybody walks out free and happy.

Multiplying prime numbers is a classical way of conveying multiple pieces of information through a single integer.

• I go crazy with the spoilers tag too, hahah. Great strategy, by the way! – HugoBDesigner Feb 23 '18 at 13:17
• @Evargalo, if you want to make multi-line spoiler, add <br> to tell SE to make a line jump ;) e.g: >! line one <br> line two – Flying_whale Feb 23 '18 at 13:17
• @Flying_whale Thx, that's what I just figured by checking how HugoBDesigner had corrected my answer. I hope I won't forget it before next time ! – Evargalo Feb 23 '18 at 13:20
• @Evargalo: Do you mean "prime" rather than "primary"? – Chris Feb 23 '18 at 15:23
• @Chris oh yeah, bad translation. It sounded weird when I wrote it. And sure everybody is a mathematician, why would we be in jail in the first place otherwise? – Evargalo Feb 23 '18 at 18:39

You're all making this much more complicated than it needs to be. :)

1. Count the maximum number of digits among the numbers you can see.
2. Starting with the largest number you can see, concatenate the numbers together, padding with 0s at the start of each number if it has fewer digits, so that you write the same total amount of digits for each number.

At this point, it's trivial to extract the original numbers again, simply by dividing the number into n equal lengths, where n is the number of hats you can see. (In the case of the puzzle as stated, 3, but this same process works for any number of hats)

Let's take an example:

Assume that there are four prisoners (including yourself), and you can see hats numbered 17, 400, and 17,400,145. You need to figure out what your own hat's number is.

The number on the slip of paper handed to you says 174,001,450,000,040,000,000,145.

First, you count the digits: That's 24 digits in total. Divide by three and you know that each individual number is going to be eight digits long. So taking the digits in sets of eight, you get back 17400145, 00000400, and 00000145. You can see hat number 17,400,145 and hat number 400, but you can't see a hat number 145, so you trivially know that that 145 must be your own hat's number.

• I think 32 in the example should be 24. This is probably just a typo, not a logic error, as the rest of the explanation makes sense for 24 but not 32. – Blckknght Feb 24 '18 at 3:06
• @jpmc26 That is why I specified "Starting with the largest number you can see"; it ensures that the first number needs no leading zeroes. (I probably should have called out that reasoning explicitly) – Trevor Powell Feb 24 '18 at 9:00
• @Blckknght Gah, you're right! I fail at counting, apparently! I've fixed the stated count of digits in the example; the method still works. :) – Trevor Powell Feb 24 '18 at 9:02
• Sorry. I think my brain must've cut off a little while ago. – jpmc26 Feb 24 '18 at 9:05

No maths required. Just write any message you want in Morse code, using 1 = dot, 2 = dash, 3 = space. An appropriate message might be something like, "Alice's number is 36473, Bob's number is 758254, Carol's number is 537242, oh and by the way the food here is terrible".

This uses much less math than other options:

Concatenate the observed numbers, then concatenate the numbers again but change the first digit of each number being concatenated (modifying the last digit also works).

Even if the numbers chosen were ambiguous when concatenated, such as repeating sequences or numbers of different length, you would write them in a given order: $ABC$, then again, modifying the first digit of each: $ABCabc$.

Example:

You see 12 121212 and 12121212. You write: 12121212121212124242121242121212. Whoever reads it divides it in half (this example doesn't require carrying, but if it did that fact would be obvious) 1212121212121212 and 4242121242121212 and sees where the 4's were added to correctly parse the first part: 12 121212 12121212, they see two of these numbers and know they are the third.

Another example: if you saw the numbers 3, 33 and 333, you would write down:
333333553533
Or something similar. Once splitting, the first half gives you the raw answer concatenated:
333333
Whereas the second half gives you the places to split it, based on where differences happen:
5 - 53 - 533

This way, you can always tell the three numbers apart. Once receiving someone else's number, you can easily work out your number by excluding the numbers you can already see.

• I'm not sure I follow, mind giving an example? – HugoBDesigner Feb 23 '18 at 19:28
• Actually, I think your answer could be simplified further to a single, simple strategy. Should I write my own answer on it or edit yours? – HugoBDesigner Feb 23 '18 at 20:07
• How do you know whether a number is "tricky"? You don't know what's on your own hat when writing the note, so it can be tricky without you knowing. – Deusovi Feb 23 '18 at 20:13
• @HugoBDesigner feel free to edit. @ Deusovi I think it can't be tricky unless there are 3 numbers of the same form, so everyone should to be able to see two before writing. – user19641 Feb 23 '18 at 20:30
• Sorry if this seems like a radical change, I just couldn't help but notice that your answer could be vastly simplified so that a single method could be used, regardless of whether numbers were "tricky" or not :P – HugoBDesigner Feb 23 '18 at 20:43

At your planning meeting,

assign each of the four prisoners a number. The four prisoners's numbers are $9$, $8$, $7$, and $6$.

Now on hat day:

convert each hat number that you can see to binary ($0$'s and $1$'s), prepend the binary string with the corresponding prisoner's number ($9$, $8$, $7$, or $6$), and then put them all together (concatenate).

Example:

Suppose you're prisoner $9$, and you see the following hats on the following prisoners: Prisoner $8$ wears hat $41$, Prisoner $7$ wears hat $74$, and Prisoner $6$ wears hat $11$.

Now:

Convert the hat numbers to binary: Prisoner $8$ wears hat $10101$, Prisoner $7$ wears hat $1001010$, and Prisoner $6$ wears hat $1011$.

Write down the number

$8101017100101061011$

When you get a number from someone else,

Look for the part that starts with your number $9$, and convert the binary string that follows back to decimal.

If you'd like to do a little less writing,

You could all agree to use base $6$ instead. Or even base $9$, and number the prisoners as $9$, $99$, $999$, and $9999$.

No math required.

Make this plan in advance, so everyone can do the same:

1: Write down all the numbers you see, one after another.
2: Encode the number of digits in each number as a string of ones and, say, sixes, and prepend it to the number string from step 1. Use the 1 to denote the first digit of a number.

For example, if the numbers you see are 42, 666 and 9000, write

161661666426669000

To guess your number,

1: Split the number string in half
2: Match the first half to the second half
3: Split the second half on the left side of each one in the first half
4: Match the numbers on hats to the list given by step 3. (you have probably already forgotten them, since the warden is going to use some really hard-to-remember numbers.), and

The one number you cannot see on another hat is your own number.

Right the numbers that you see using trailing 0s as separators. the 4 numbers can then be decoded (since 0 is not a valid number) and your number is the number you did not see (since your guaranteed to not receive your own message).

Example numbers:

4 15 16 10

Encoding where you are 4:

15016010 or 15010016 etc.

• This plan fails in the face of numbers with lots of internal zeros. For instance, if you see your fellow prisoners with numbers 1010101 (4 ones), 101010101 (5 ones) and 10101010101 (6 ones), and you get given a paper with 10101010101010101010101 (12 ones) written on it, you have no idea whether your number is 1, 101, or 10101 (since all you can do is count the ones, and 12 = 5+4+3 = 6+4+2 = 6+5+1). – Blckknght Feb 24 '18 at 2:51

This answer assumes that you can remember all of the numbers that you have seen and the person who has this number.

Number each person in base 10, with leading zeroes so that each person has the same number of digits for their number (for instance, if there are 245 people, then person number 11 would have the number "011").

Write the sum of all the other numbers concatenated with the person number.

This will allow you to determine your own number.

How:

i) Assume there are more than 100, but less than 1000 people. Then you have 3 digits for the person number. Assume you are person a (where a is this 3 digit number)

ii) You add up all of the numbers that you see and get the answer X.

iii) You write this on the paper concatenated with your number. Since you are number a, this is Xa.

iv) You receive a paper back, and use the last three digits, which we will call b to determine whose paper it is, and the remaining digits to know the sum, which we will call Y. So the full number was Yb.

v) Assume that we remember what number was on b's head. Call this number m.

vi) Subtract m from X, the original sum that you calculated and wrote down. This gives the sum of all hats except your own hat and the hat of the person whose sheet you have, b.

vii) The difference between Y, the sum of all hats except person b, and (X-m), the sum of all hats except yours and person b's, is the number on your hat. This would be Y - (X-m).

This should work with any numbers as the numbers all had to be greater than 0, so the sum must be greater than 0.

• If a person's number is "110", but prisoners A and B have hats "12345110110" and "11012345", wouldn't it be impossible to parse the numbers on the hats? Or do I understand your answer wrongly? – HugoBDesigner Feb 23 '18 at 20:45
• The person number is always three digits after the sum, (A+B+[your number])xyz with x,y,z each a digit in all cases. With your example numbers (taking your number arbitrarily as 12345110) the prisoner writes (12345110110+11012345+12345110) = 12368467565, then appends their personal number 110 => 1236867565110. You read this and see the ending 110 and know not to bother with the number on person 110's hat, subtract A and B from 12368467565 to get back to your number. – user19641 Feb 23 '18 at 22:11
• If a person's number is "110", then there are at least 110 prisoners. Let us assume that there are less than 1000. Let us further assume that the other prisoners, besides prisoners A and B, have a total sum of 1,000,000,000 on their hats. We will assume that prisoner B is number "099." Then, prisoner A would write the number 1011012345110 where the first 10 digits, 1,011,012,345,110 = 1,000,000,000 + 11,012,345 and the last three digits are prisoner A's number, "110." – OpiesDad Feb 23 '18 at 22:12
• Prisoner B would write the number 13345110110099 where the first 11 digits, 13,345,110,110 = 1,000,000,000 + 12,345,110,110 and the last three digits are prisoner B's number, 099. You then take 13,345,110,110 - (1,011,012,345,110 - 11,012,345) = 12,345,110,110 which is the number on your hat. – OpiesDad Feb 23 '18 at 22:16
• I think this answer could be simplified by solving for the question as given (four prisoners) and then once you have given that argument with examples then explain how to solve it for the general case. When the "how" starts with an assumption (there are more than 100 prisoners) whixh contradicts the facts given (ere are 4 prisoners) it doesnt make for a good explanation. That javing been said the technique seems to be good... – Chris Feb 24 '18 at 18:10