100 Dwarves and a tiny room

Question

I've got this riddle from a friend at work.

Say we have 100 dwarves. They all receive little dwarven shirts with numbers between 0-99 (With repetitions), and after that they all enter into a room. (So that they can see all the other dwarves numbers but not their own number.)

They need to decide on an algorithm before entering the room so that they all call out the same number at the same time and at least one of the dwarves will have that number on his shirt.

While in the room they they can't exchange any type of information: they can't talk or arrange in any way (Like sorting themselves out and such).

What's the algorithm? :)

Answer 1

No such algorithm exists.

• Suppose Bob sees 0's on 99 shirts. He must call out 0, since it is possible that 0 is the only represented number.

• Suppose Bob sees 0's on 98 shirts, on everyone except Alice's shirt. If Bob's shirt were 0, then Alice would see 99 zeroes, and announce 0 (by the previous bullet point). This means Bob must announce 0, else there would be a chance that Bob's and Alice's calls were different.

• Suppose Bob sees 0's on 97 shirts, where Alice isn't wearing 0. If Bob's shirt were 0, then Alice would see 98 zeroes, and announce 0 (by the previous bullet point). This means Bob must announce 0, else there would be a chance that Bob's and Alice's calls were different.

This logic continues inductively, so that if Bob sees 96, 95, or any number of zeroes, he must announce 0. Since everyone calling 0 is not a winning strategy, no strategy exists.

Answer 2

I think f'' basically has the right answer, but here's a simpler explanation of why it's not possible.

Assume there is an algorithm. Consequently there must be an output i when all the shirts have different numbers (e.g. the shirts are 0-99 and are in the same order as the dwarves ages).

So the dwarf wearing shirt i must shout i whenever he sees the other dwarves wearing their specific combination. So if we had given him a different shirt then he would still shout i.

This is a contradiction as the algorithm is assumed to output a number that is on one of the dwarves shirts. Hence no such algorithm exists.

Answer 3

As currently stated, this is impossible.

Assume that there is a working algorithm. Call the dwarves $d_0, d_1, \ldots d_{99}$. Suppose that $d_0$ sees every other dwarf wearing their own number. The algorithm says that $d_0$ must call out a number $i$.

If $i$ is 0, then the algorithm fails if $d_0$ isn't wearing 0 and all others are wearing their own number.

If $i$ isn't 0, now consider $d_i$. Suppose $d_i$ sees all the other dwarves except $d_0$ wearing their own numbers, and $d_i$ wearing some number other than $i$. $d_i$ must call a number $j$.

If $j$ isn't the same as $i$, then the algorithm fails when all except $d_0$ wear their own numbers, because $d_0$ will call $i$ while $d_i$ calls $j$.

But if $j$ is equal to $i$, then the algorithm fails when all except $d_0$ and $d_i$ are wearing their own numbers and $d_0$ isn't wearing $i$, because then nobody is wearing $i$.

Answer 4

Call out a single digit number such as "9", then anyone wearing a shirt with:

9, 19, 29, 39, 49, 59, 69, 79, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98 or 99

on their shirt, will have the number 9 on their shirt.

not 100% certain, but if the numbers are assigned randomly then there's nearly a 1 in 5 (19/100) chance that a single dwarf will have a number 9. Odds are drastically in their favour.

Answer 5

It's impossible, because if a combination is supposed to have a solution, the combination of seen numbers must all lead to the same number. If a list of these 99 seen numbers leads to $n$, then when we create a new combination by changing the other number, all the lists must lead to $n$, or there would be no solution. Finally we arrive at a point where it should still lead to $n$ even though it's no longer there! This contradiction makes it impossible for every combination to have a solution.

Edit: turns out my reasoning was the same as those of almost all the others.

Answer 6

This is easy!

Reading the question - they get their shirts BEFORE they go into the room and they are not prohibited from communicating until they enter the room. The algorithm is that they look at the first dwarf's shirt and tell him number, then they all go into the room and shout that one out.