Do you really have a rigorousproofinvolving probability ? If the players answer at random, it doesn't help since it may very well happen that all players fail, however unlikely this is.

I found a solution. The idea is simple, but it is a bit complicated to turn it into a quite rigorous proof (it is very tempting to take some things for self-evident about what strategy should be better...). I'm going to give you the main idea, and provide a complete proof afterward (because I was so proud of it! )

--------------

Here's the hint. The idea is to compare two situation: A) "N blue, N red", and B) "N+1 blue, N-1 red". In situation A), each player sees N-1 hats of one color, and N of the other colour, and their own colour is the one with N-1 hats. In situation B), N+1 players see N hats of one colour and N-1 of the other colour, and their own colour is the one with N hats (so that's thecontraryto before). (and there are N-1 other players)

A strategy is a way for each player to decide what to answer when he sees some number of red and blue hats. Suppose each player decides that, if he sees N hats of one colour, he answers this colour. Then N+1 players win in situation B, but all players lose in situation A... On the other hand, if each player decides that, if he sees N hats of one colours, he answers the other colour, then all win in situation A, but N+1 lose in situation B hence at most N-1 win.

The difficulty for a complete proof is that the strategy may a priori depend on the player...

-----

Now for the proof, fully rigorously. Assume by contradiction that there is a strategy for which at least N+1 players win in any configuration. Take a team of 2N players who apply this strategy.

Consider the first situation: Put N hats of each colour on the heads of the players. Let's say a number A of red hat players answer right (according to their strategy). That means that their strategy tells them: "If you see N-1 red hats, answer red". In the same way, a number B of blue hat players answer right. We have by assumption on the strategy.

Now (for the same players) switch the colors of the hats (between blue/red) and play again. Then A' blue hat (ex red hat) players answer right, and B' red hat (ex blue hat) players answer right, with .

We have , hence either or . In other words,there is a colour C (either red or blue) for which at least N+1 players answer C if they see N-1 hats of colour C.

Denote by C' the colour different from colour C, and consider the following experiment: put hats of colour C' on N+1 players among the latters (i.e. the ones who answer C if they see N-1 hats of colour C), and hats of colour C on the N-1 other players. What happens? The first N+1 players will see N hats of colour C', and N-1 hats of colour C. Due to the way these players were selected, they will answer C, which isnottheir own colour. Therefore, at least these N+1 players will lose. Hence at most N-1 will win. This contradicts the initial assumption.

As a conclusion, no strategy allows in any situation at least N+1 players to win. QED.

-----------------

Remark: We know now that it is not possible to make at least N+1 players win every time. But conversely, is there a strategy for which at least N players win in any situation? This should be a simpler question, but I can't find it (and, well, it's almost 1 o'clock in the morning...).

An obvious strategy would be: "Answer the colour that appears more often". This strategy will make more than N winners if there are more hats of one colour (the players with the dominant colour win). But it will completely fail if there are equally many red and blue hats... This is the same problem as above.

Any idea welcome !!