15
$\begingroup$

A team of 10 people are going to play a cooperative game. While their eyes are closed, a pit boss will place either a red or green hat on each of their heads, chosen by fair coin flip. They then all open their eyes, and will be able to see the hats on everyone's heads except their own.

The players will then simultaneously bet a number of dollars that the hat they are wearing is green. Specifically, on the pit boss's signal, the players will each call out an integer, which may be positive, negative or zero. Calling a negative number is effectively betting that your hat will be red.

The total winnings of the players is calculated by adding up the bets of people with green hats, and subtracting the bets of people with red hats. The team of players wins if and only if their total winnings are more than zero.

Before the game begins, the players may agree on a strategy, but once the hats are placed, no communication between the players is possible.

What strategy maximizes the players' chances of winning? Why can't they do better?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
15
$\begingroup$

The players can win with probability

$ 1- \frac{1}{2^{10}}$

This is optimal because:

Each player's bet has expectation $0$, and therefore, so does the sum of the bets. Therefore, it's not possible to win for every possible setting of hats, so at least of one the $2^{10}$ settings must lose.

A strategy that achieves this is:

The players imagine standing in line in a predetermined order so that each player only sees the hats of the players in front. The front player, who sees nothing, bets \$1 that their hat is green. If it is, the rest of the players see so, and bet nothing, which gives a win. If it's not, the second player bets \$2 that their own hat is green. If it is, the rest of the players know that they are net ahead \$1 and do nothing, and if not, the next player bets \$4 that their hat is green, and so on. Each player is able to simulate what will happen ahead in line, so they all know the correct to make at the same time.
In general, the player who sees $k$ players in front bets $2^k$ dollars that their hat is green only if all hats they see are red, and bets nothing otherwise. If player $k$ is the first in line with a green hat, they win $2^k$, which is enough to offset the $2^k-1$ that the players in front lose for also betting that they have green hats, and nobody behind them bets. The players only lose if everyone has red hats, losing $2^{11}-1$ dollars.

Improve this answer
$\endgroup$
1
  • $\begingroup$ similar to a Martingale? $\endgroup$
    – smci
    Nov 5, 2016 at 13:27
8
$\begingroup$

Surprisingly, the prisoners can win against

every hat sequence except one. If this is possible, then it is obviously optimal: since the average dollars won is always 0, the prisoners can't win all the time.

Here is the strategy:

If you see $n$ red hats, bet $10^{n!}!$ dollars that your hat is green. The point is that this function grows very fast, and anyone wearing green sees 1 more red hat than anyone wearing red. So, if there are any green hats whatsoever, then the total of all bets by people with green hats will be much larger than the total of all bets by people with red hats.

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ Good answer, but that seems slightly overkill. Surely $10^n$ would do? $\endgroup$
    – frodoskywalker
    Jun 5, 2015 at 19:42
  • $\begingroup$ Yes, $10^n$ would do. $\endgroup$
    – Lopsy
    Jun 5, 2015 at 20:04
  • $\begingroup$ Damn this right-handed iphone app. Sorry for the downvote. I can fix it after an edit if you do one. $\endgroup$
    – LeppyR64
    Jun 5, 2015 at 21:13
  • $\begingroup$ @LeppyR64, you have sufficient reputation to make a trivial edit yourself if you wanted to. $\endgroup$
    – James Webster
    Jun 6, 2015 at 8:15
  • 2
    $\begingroup$ @LeppyR64, a non-trivial, valid edit might be swapping "prisoner" for "player" to match the question $\endgroup$
    – James Webster
    Jun 6, 2015 at 8:16
-1
$\begingroup$

You didn't say if the players are allowed to do something between the moment they open their eyes, and the moment they have to place their bid. If, for example, they are allowed to walk around (without talking to each other or communinating in any way!), they can always win.

  • At the start, two players stand next to each other
  • The other players, one by one, chose their position like this:
    • If everybody standing in line has a green hat, stand to the right of them
    • If everybody standing in line has a red hat, stand to the left of them
    • If there are some red hats and some green hats, there must be an uninterrupted line of green hats to the left, and an uninterrupted line of red hats to the right. Chose your place between the two where the color changes.
  • At the end, if there is a red hat to your left, bet a large negative number, since your hat is red as well
  • Similarily, if there is a green hat to your right, your hat is green,so bet a large positive number
  • If there are only green hats to your left, and only red hats to your right, you don't know the color of your hat; bet a zero (if allowed to), or the smallest number you are allowed to bet. Just reread the instructions, zero is allowed.
Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ But arranging themselves in this way is communicating! Each player is, by their placement, telling the player before them what color they have. $\endgroup$
    – frodoskywalker
    Jun 5, 2015 at 23:16
  • 1
    $\begingroup$ In addition, the starting rules are broken. Start with one player, not two, so they don't accidentally start with a red hat to the right of a green hat. $\endgroup$
    – Oddthinking
    Jun 6, 2015 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.