Escape From Evil's Room

We consider general case with $n$ people.

We first show that the people can win with probability $1 -\dfrac{1}{2^n}$ . To do this, A person simply says the number $(-1)^r.n^r$ where $r$ is the number of red hats she sees. Now, if there are $n - r$ blue hats and $r$ red hats, then $n - r$ people see $r$ red hats and $r$ people see $r - 1$ red hats. Thus, the sum of the numbers said will be

$(-1)^r\left((n - r) . n^r - r · n^{r-1}\right)=(-1)^r n^{r-1}(n^2-r(n+1))$

Since $n^2 > r(n+ 1)$ if $r < n$ the people will win as long as the hats aren’t all red, which is an event with probability $\dfrac{1}{2^n}$ .

Now, we must show that there is no strategy that does any better. Note that there are $2^n$ possible events (each person gets 1 of 2 possible hat colors) and each strategy works for some subset of them. Thus, all we must show is that there is no strategy that works in all cases. So suppose there is. For each event $E$ , let $r(E)$ denote the number of red hats, $E_i$ denote the number that the $i$ ’th person says under the winning strategy, and $S(E)$ denote the sum of the $E_i$ . Since the strategy always works, we must have $(-1)^{r(E)}S(E)$ is always positive.

Let us consider the sum $\displaystyle \sum_{E}(-1)^{r(E)}S(E)$ . Note that this can be rewritten as

$\sum_{i=1}^n\sum_{E} (-1)^E{r(E)}E_i$

Now, fix some $i$ . Let $E'$ denote the event $E$ but with the $i$ ’th person receiving the opposite hat coloring. Then $r(E) = r(E')\pm1$ and $E_i = E'_i$ since the colors that person $i$ sees are the same for $E$ and $E'$ . Thus,

$(-1)^{r(E)}E_i + (-1)^{r(E')}E'_i=0$

Since the map $E \rightarrow E'$ pairs of all events, we must have that $\displaystyle \sum_{E} (-1)^E{r(E)}E_i=0$ , and thus $\displaystyle \sum_{E}(-1)^{r(E)}S(E)=0$ .

This is a contradiction, which completes the proof.

So the answer is $\left\lfloor 10^4*P\right\rfloor=\left\lfloor 10^4\left(1-\dfrac{1}{2^{10}}\right)\right\rfloor=\boxed{9990}$ .