2
$\begingroup$

Given the following variant of the hat guessing game: There are n players and two colors, everybody has to guess his hat color. The aim is to find a strategy guaranteeing as many correct guesses as possible.

The optimal strategy guarantees $\lfloor{\frac{n}{2}\rfloor}$ and involves to have players paired up. If the number of players is odd, then the unpaired one always guesses he has, let us say, a blue hat. In each pair one player guesses he has a hat of the same color as the other player, while the other player guesses he has a hat of the color another than the first player.

How to prove that this strategy is optimal?

$\endgroup$
6
  • $\begingroup$ The guess are not independent though, I think the strategy is clear we the $n=2$ case: one player guesses he has a hat of the same color as the other player, while the other player guesses he has a hat of the color another than the first player. This guarantees one (and only one) player being correct and can be scaled by pairing up in the $n>2$ case. $\endgroup$
    – Mattiatore
    Jan 26, 2023 at 12:57
  • 1
    $\begingroup$ Ah, I see. Okay, you're right, this works. $\endgroup$
    – tomasz
    Jan 26, 2023 at 13:07
  • 1
    $\begingroup$ Must the guesses be made at the same instant? If not, then let one player declare the parity of the number of Black hats they see. That player may or may not get their own hat color right, but everyone else will be correct, so you can guarantee $n-1$. $\endgroup$
    – lulu
    Jan 26, 2023 at 16:00
  • $\begingroup$ Ah yes sorry, they need to decide simultaneously $\endgroup$
    – Mattiatore
    Jan 26, 2023 at 16:01
  • $\begingroup$ There doesn't seem to be any reason for the players to pair up; they simply guess randomly (or all guess blue, or whatever). This is different from the variants where, for example, the players are not all obligated to guess but get punished if no one guesses; in that case, they must come up with a strategy over who will guess what. $\endgroup$
    – Théophile
    Jan 26, 2023 at 23:21

1 Answer 1

2
$\begingroup$

No matter what strategy the players use, each player has a probability of $1/2$ of guessing their hat correctly. This is because, for each player, the $n-1$ hats they see will cause them to guess a particular color, and then their own hat will match that color with probability $1/2$. Linearity of expectation implies the expected number of correct guesses is $n/2$. Therefore, there cannot exist a strategy which guarantees getting more than $n/2$ guesses correct; if you could guarantee getting $x$ correct, the expected number correct would have to be at least $x$. This proves $\lfloor n/2\rfloor$ is optimal.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .