12
$\begingroup$

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? :)

$\endgroup$
  • $\begingroup$ Are they all calling out the number at the same time? $\endgroup$ – qwertylpc Jul 29 '15 at 16:22
  • 3
    $\begingroup$ Also as the question is currently worded they can just call out the number of the person right next to them... $\endgroup$ – qwertylpc Jul 29 '15 at 16:23
  • $\begingroup$ Does the question mean that they all have to call out the same number? $\endgroup$ – Aggie Kidd Jul 29 '15 at 16:28
  • $\begingroup$ @qwertylpc " all call out one number " $\endgroup$ – Going hamateur Jul 29 '15 at 16:32
  • 1
    $\begingroup$ @Goinghamateur that is why I asked. They all call out one number which says nothing about whether it is the same number or not. Nor does it say anything about it being in unison... $\endgroup$ – qwertylpc Jul 29 '15 at 16:34
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This can be used with every other number as well, so not only must Bob say 0, he must say every number. If this wasn't tagged "logic-puzzle" I'd say the answer would be for them to just count from 0 to 99 in unison. $\endgroup$ – Rob Watts Jul 29 '15 at 18:47
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ "If $i$ is 0, then the algorithm fails if $d_0$ isn't wearing 0." That isn't necessarily true if any other $d$ is wearing is wearing 0. $\endgroup$ – qwertylpc Jul 29 '15 at 17:28
  • $\begingroup$ @qwertylpc edited for clarification. $\endgroup$ – f'' Jul 29 '15 at 23:37
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I gotta say it is very original. $\endgroup$ – StationaryTraveller Jul 30 '15 at 10:25
  • $\begingroup$ @StationaryTraveller Question simply stated they had to have that number on their shirt, not the exact number :). I'm not a mathematician by any stretch but by my calculations there's only a 0.05% chance of there being no number 9's on any shirt. Perhaps someone clevererer than I can confirm this? :P $\endgroup$ – Jamie Barker Jul 30 '15 at 10:46
  • $\begingroup$ @CodeUniquely There are 20 9's, correct, however a shirt with 99 on is still only one shirt with a number 9 on, so there are only 19 possible shirt number combinations out of 100 that display a 9 on (count the list above). And of course it's the same for every number, as I said in my answer: "single digit number such as "9"" $\endgroup$ – Jamie Barker Jul 30 '15 at 12:10
  • $\begingroup$ Well, maybe we can about double the odds with 9, as a 6 is an upside-down nine. So, we can add 17 more numbers for about a 36% chance of any dwarf having the number. $\endgroup$ – MikeP Mar 31 '18 at 1:56
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ They can't see each other until they enter the room, and they can't see their own number. $\endgroup$ – Jamie Barker Jul 30 '15 at 12:31
  • $\begingroup$ Now you're changing the puzzle ;P $\endgroup$ – Gordon K Jul 30 '15 at 12:32
  • $\begingroup$ "and after that they all enter into a room. (So that they can see all the other dwarves numbers but not their own number.)" $\endgroup$ – Jamie Barker Jul 30 '15 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.