Numbered hats, Warden and Maths

Question

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.}

Answer 1

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!)

Answer 2

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.

Answer 3

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.

Answer 4

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".

Answer 5

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.

Answer 6

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$.

Answer 7

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.

Answer 8

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.

Answer 9

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.