12
$\begingroup$

The following is an extension of 100 Dwarves and a tiny room. The text of this puzzles spoils that one in a minor way, so go read that excellent puzzle first!


An evil elf puts $100$ dwarves in a room and gives each a shirt with a number from $0$ to $99$ (repetitions allowed). The dwarves can see everyone's number except their own, but otherwise can't communicate in any way. Their goal is to all simultaneously shout out the same number, and for this shouted number to appear on the shirt of at least one dwarf. Thus, they lose if more than one number is shouted at that instant, or if the single number shouted is not on any dwarf's shirt.

It is up to you to decide their strategy: in particular, you will give instructions to each dwarf, and the dwarf will follow your instructions exactly. However, the evil elf will also read these instructions, and assign shirts to minimize the probability of the dwarves' success.

What strategy would you give them, and what is the probability they win?

A few notes:

  • In the room there is a large screen, which all the dwarves can see, that can display whatever random number(s) your instructions require. These random number(s) are chosen after the shirts are distributed. This is to help the dwarves implement some sort of strategy involving randomness.

  • The only major difference between this puzzle and the original is that I'm asking not about whether a 100% win rate is possible, but how high you can make the win percentage.

  • For our purposes, if a dwarf has a shirt with a 29 on it, this doesn't match a shouted answer of "9" or "2".

  • I don't know the answer; I'll accept the answer with highest probability after a reasonable amount of time. I do know it is possible to do better than 1/100.

$\endgroup$
  • $\begingroup$ "communicate in any way" is non-communicative movement allowed, such as sitting down? $\endgroup$ – Jamie Barker Jul 31 '15 at 8:38
  • $\begingroup$ @JamieBarker: Not if sitting down communicates anything, like if Gimli sitting down communicates the fact that he sees a 17 on someone's shirt. $\endgroup$ – Tyler Seacrest Jul 31 '15 at 14:46
  • $\begingroup$ @TylerSeacrest Is it allowed for information to be shared by silence? For example, a strategy "If you see a 0, say 0 one minute after entering the room" where if nobody says anything at one minute, then it becomes common knowledge that there are no 0s. Of course, if some but not all say a number, then they fail. $\endgroup$ – f'' Jul 31 '15 at 15:16
  • 1
    $\begingroup$ @f'': I did not consider that issue until you brought it up. Since that seems to be up to interpretation and you have a great solution that uses that strategy, I will say that is allowed and we'll see if anyone can beat you with silence-based strategies allowed. $\endgroup$ – Tyler Seacrest Jul 31 '15 at 15:36
  • $\begingroup$ @TylerSeacrest I haven't actually used it yet, but I was asking because I might need it later. The strategy ABC as it's currently written works even if the silence is a fail. $\endgroup$ – f'' Jul 31 '15 at 15:54
9
$\begingroup$

I will describe a lower bound and an upper bound on the probability of success the dwarves can guarantee. These bounds are:

Lower bound: There is a strategy for the dwarves giving a win probability of at least $\frac{100}{199}\approx 50.25\%$.
Upper bound: I will argue that the dwarves cannot guarantee a win with probability greater than $\frac{100}{101}\approx 99.01\%$.

Lower bound: Imagine that there is a stack of 100 shirts in the corner of the room, one of each number. Then each dwarf can see a total of 199 shirts. The dwarves can use the following strategy: a random integer $n$ between 1 and 199 (inclusive) is displayed on the screen, each dwarf lists the 199 shirt numbers they can see in order from smallest to largest, and each dwarf shouts out the $n$-th number on their list.

Consider the large list of all 200 shirt numbers in the room. Each dwarf will either call out the $n$-th number on the large list or the the $(n+1)$-st, depending on where their own shirt number falls. There can be at most 99 values of $n$ for which the $n$-th entry and the $(n+1)$-st entry or the large list are different, so if the random value of $n$ selected is not one of these, then every dwarf will call out the same number, and additionally that number will appear at least twice on the large list, meaning at list one dwarf has that number on their shirt. This gives a probability of success of at least $\frac{100}{199}\approx 50.25\%$.

Upper bound: There is no strategy the dwarves can use to guarantee a probability of success greater than $\frac{100}{101}\approx 99.01\%$. This is true even if the elf is restricted to assigning shirts numbered either 0 or 1. Suppose the dwarves have chosen a strategy. For $k=0,1,\ldots,99$, let $p(k)$ be the probability that a given dwarf guesses 0, given that that dwarf sees exactly $k$ shirts labelled 0 (and therefore $99-k$ shirts labelled 1). For $k\geq 1$, if exactly $k$ shirts are labelled 0, then some dwarves see $k$ 0's and some dwarves see $k-1$ 0's, so the probability of both numbers being guessed must be at least $p(k)-p(k-1)$. If $k=0$ (all shirts are 1), then probability of failure (someone guesses 0) is at least $p(0)$. Similarly, if $k=99$ (all shirts 0), then probability of failure (someone guesses 1) is at least $1-p(99)$. By choosing $k$, the elf can choose the probability of failure to be any one of the following 101 numbers: $$ p(0),\,\,p(1)-p(0),\,\,p(2)-p(1),\,\,\ldots,\,\, p(99)-p(98),\,\,1-p(99). $$ These numbers sum to $1$, so there must be one of them that is at least $\frac{1}{101}$. This means that if the elf chooses the appropriate number of shirts to be labelled 0, the probability of failure is at least $\frac{1}{101}$, so the dwarves cannot guarantee victory with probability greater than $\frac{100}{101}$.

$\endgroup$
  • $\begingroup$ Wow! I thought for sure f'''s solution was going to win. You've not only done better but done it with an extremely elegant solution. I wish I could give this 50 upvotes. $\endgroup$ – Tyler Seacrest Aug 3 '15 at 5:52
  • $\begingroup$ Your lower bound solution generalizes to any number of dwarves and any number of shirts. With 100 dwarves and 2 shirts, your lower bound matches your upper bound. If feel like this is evidence that your lower bound is correct, we just need to improve the upper bound in the case of more shirts. $\endgroup$ – Tyler Seacrest Aug 3 '15 at 5:54
  • $\begingroup$ Well, I guess I can stop working on my answer then. Very nice. $\endgroup$ – f'' Aug 3 '15 at 12:31
7
$\begingroup$

Without the evil elf, there are a couple sensible strategies.

Strategy A: Choose a random number from 0 to 99. Everyone shouts that number.

If the shirts were assigned at random, this would have a 1-(99/100)^100 chance of succeeding, or about 63%. Unfortunately, the elf will assign the same number to every dwarf for a 1/100 chance of winning.

Strategy B: Choose a random ordering of the numbers from 0 to 99. Every dwarf shouts the first number in the ordering that they see on at least one shirt.

This succeeds if out of all the represented numbers, the first one in the ordering occurs at least twice. Of course, the evil elf can assign all different shirts to guarantee that this fails.

But the counter-strategy for each strategy gives a 100% chance of success for the other strategy! What about this:

Strategy AB: Choose Strategy A or Strategy B with equal probability.

The best the elf can do is to assign 91 identical shirts and 9 different ones, for a 10% chance of success. We're not done yet:

Strategy C: Choose a random ordering of the numbers from 0 to 99. Every dwarf shouts the first number in the ordering that they see on at least two shirts. If they do not see any number on two shirts, they shout the first number in the ordering.

This succeeds whenever out of all the numbers on at least two shirts, the first one in the ordering occurs on at least three. If no numbers occur on at least two shirts, it is equivalent to Strategy A.

There is a mixed strategy between A, B, and C that does better than 1/10. This one is the best:

Strategy ABC: Choose Strategy A with probability 250/741, Strategy B with probability 253/741, and Strategy C with probability 238/741.

The elf has three equally good strategies here, which all have a success rate of 1601/7410 (21.6%).

Strategies A, B, and C are all special cases of a general strategy:

Strategy N: Choose a random ordering of the numbers 0 to 99. Every dwarf shouts the first number they see on at least N shirts. If they do not see such a number, their action will be specified later.

Using a mix of these strategies, I think there is a hard upper bound at 51%, but it might be possible to reach 43%.

$\endgroup$
  • $\begingroup$ I don't think this would work. Your strategy relies on making random choices and sharing those choices with all the dwarves. If you do that, the elf would also see your random choice, and you would lose. If you have each dwarf choose random numbers separately, your odds of winning are nearly zero. $\endgroup$ – user3294068 Jul 31 '15 at 14:16
  • 2
    $\begingroup$ @user3294068 from the question statement "In the room there is a large screen, which all the dwarves can see, that can display whatever random number(s) your instructions require. These random number(s) are chosen after the shirts are distributed. This is to help the dwarves implement some sort of strategy involving randomness." $\endgroup$ – f'' Jul 31 '15 at 14:36
  • $\begingroup$ How did I miss that? $\endgroup$ – user3294068 Jul 31 '15 at 15:00
3
$\begingroup$

Update: I missed the "large screen" part. This answer assumes no such screen.

A lower bound for winning is "Every dwarf choose a number at random". There is a $1000^{-1000}$ chance of all dwarves choosing the same number. The best the elf can do is assign everyone the same number, which leaves you with a total chance of winning of $1000^{-1001}$.

The best I can come up with is: Find the lowest number you see. Guess that with probability $p$. Otherwise, guess randomly from among the lower numbers.

If the lowest number shows up on two shirts, every dwarf sees the same lowest number, and you with with probability $p^{1000}$. If the lowest number shows up on only 1 shirt, then 999 dwarves see the same lowest number, and 1 dwarf sees a lowest number $n$, which is the next lowest number. In this case, you win with probability

$$P = p^{999}(1-p){1\over n}$$.

This is generally less, so we can assume the elf will choose this option.

The optimal value of $p$ does not depend on $n$: a bit of calculus yields $p = {999\over 1000}$.

The best the elf can do is assign the number 999 to 999 of the dwarves and some other number at random to the other one. This yields a probability of winning of: $P = 3.6 \times 10^{-7}$, which is about 1 in $e$ million.

I don't think you can do better. The elf can ensure that at least 1 dwarf will need to guess a number he can't see. This strategy ensures that at most 1 dwarf will have to pick a number he can't see and maximizes the odds of him picking the number everyone else should pick.

$\endgroup$
  • $\begingroup$ Interesting variation. I'd be curious what the best strategy is without the big screen in the room, in which case I certainly don't have something that beats 1/100. $\endgroup$ – Tyler Seacrest Jul 31 '15 at 15:37

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.