Originally Posted by

**godelproof** you proved a subset of the set of all strategies (i.e.,the strategies that don't require a coding to work out) .

Now I understand your point: indeed I assumed implicitly that the decisions of the player only depend on the number of coloured hats they see. And the strategy I gave for N winners doesn't fit into this scheme... So my proof isn't very satisfying after all...

Today i thought of another proof, which is rigorous and much simpler, but far less ingenious than yours. If you want to see it, i can post it.

Sure I'd like to! I guess it looks like the one at the end of this post...

Another thing, i'd like to know your opinion on a probabilistic proof. Its idea is very simple: 1/2 (independent) probability to put on red hat on every one. Then the expectation of numbers of players win is N for any strategy (easy to verify!). If there is a strategy that guarantees at least N+1 players always win, then the expectation should be no less than N+1, which is a contradiction. Do you think such a proof is acceptable? Well i feel very uncomfortable with it. but i can give no clear reasons to object it.

That looks clever! Let me give a try at writing a clean proof:

For $\displaystyle 1\leq i\leq 2N$, let $\displaystyle F_i$ be a function that defines a strategy for player $\displaystyle i$, i.e. $\displaystyle F_i:\{R,B\}^{2N}\to\{R,B\}$ is any function *that does not depend on the *$\displaystyle i$*-th coordinate*.

Let $\displaystyle X=(X_i)_{1\leq i\leq N}$ be a vector of independent r.v. with $\displaystyle P(X_i=R)=P(X_i=B)=1/2$. The number of winners in configuration $\displaystyle X$ is $\displaystyle W(X)=\sum_{i=1}^{2N}{\bf 1}_{(F_i(X)=X_i)}$.

Since $\displaystyle F_i(X)$ depends only on $\displaystyle (X_j)_{j\neq i}$, which is *independent *of $\displaystyle X_i$, $\displaystyle P(F_i(X)=X_i)=E[P(F_i(X)=X_i)|(X_j)_{j\neq i}]=1/2$. Therefore, the expected number of winners is $\displaystyle E[W(X)]=\sum_{i=1}^{2N} P(F_i(X)=X_i)=N$.

If the functions $\displaystyle F_1,\ldots,F_{2N}$ could be chosen in such a way that $\displaystyle W(x)\geq N+1$ for any $\displaystyle x\in\{R,B\}^{2N}$, then we would have $\displaystyle W(X)\geq N+1$ a.s. hence $\displaystyle E[W(X)]\geq N+1$, contradicting the previous paragraph.

-------

One could also write the exact same proof without random variables, which may look more convincing. We have (keeping notations):

$\displaystyle \sum_{X\in\{R,B\}^{2N}}W(X)= \sum_{i=1}^{2N} \sum_{X\in\{R,B\}^{2N}} {\bf 1}_{(F_i(X)=X_i)}$ $\displaystyle = \sum_{i=1}^{2N} \sum_{(X_j)_{j\neq i}\in\{R,B\}^{2N-1}} ({\bf 1}_{(F_i(X)=R)}+{\bf 1}_{(F_i(X)=B)})$

(the last parenthesis correspond to the summation over $\displaystyle X_i\in\{R,B\}$, which makes sense since $\displaystyle F_i(X)$ does only depend on $\displaystyle (X_j)_{j\neq i}$)

The sum of the two indicator functions is obviously 1. Therefore, we get:

$\displaystyle \sum_{X\in\{R,B\}^{2N}}W(X)=\sum_{i=1}^{2N} \sum_{(X_j)_{j\neq i}\in\{R,B\}^{2N-1}} 1= 2N 2^{2N-1}=N 2^{2N}.$

We have a sum of $\displaystyle 2^{2N}$ terms on the left-hand side, which equals $\displaystyle N 2^{2N}$, hence at least one term must be less than or equal to N: there exists a configuration $\displaystyle X$ such that $\displaystyle W(X)\leq N$. QED.