100 Dwarves vs. the Evil Elf

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.