14
$\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? :)

Improve this question
$\endgroup$
12
  • $\begingroup$ Are they all calling out the number at the same time? $\endgroup$
    – qwertylpc
    Commented Jul 29, 2015 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
    Commented Jul 29, 2015 at 16:23
  • $\begingroup$ Does the question mean that they all have to call out the same number? $\endgroup$
    – Aggie Kidd
    Commented Jul 29, 2015 at 16:28
  • $\begingroup$ @qwertylpc " all call out one number " $\endgroup$
    – Going hamateur
    Commented Jul 29, 2015 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
    Commented Jul 29, 2015 at 16:34

6 Answers 6

Reset to default
14
$\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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Jul 29, 2015 at 18:47
9
$\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.

Improve this answer
$\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$.

Improve this answer
$\endgroup$
2
  • 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
    Commented Jul 29, 2015 at 17:28
  • $\begingroup$ @qwertylpc edited for clarification. $\endgroup$
    – f''
    Commented Jul 29, 2015 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I gotta say it is very original. $\endgroup$
    – StationaryTraveller
    Commented Jul 30, 2015 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
    Commented Jul 30, 2015 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
    Commented Jul 30, 2015 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
    Commented Mar 31, 2018 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.

Improve this answer
$\endgroup$
1
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ They can't see each other until they enter the room, and they can't see their own number. $\endgroup$
    – Jamie Barker
    Commented Jul 30, 2015 at 12:31
  • $\begingroup$ Now you're changing the puzzle ;P $\endgroup$
    – Gordon K
    Commented Jul 30, 2015 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
    Commented Jul 30, 2015 at 12:44

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