The Problem
There are many versions of this problem before, most have the prisoners standing in a straight line so that they can't see the ones behind them, but here it's different.
I was asked this twist on the question before in an interview and I don't think I fully understand if there's a trick or if the answer is just really obvious. I don't remember the exact problem statement, so I'll try my best to remember the exact phrasing.
A group of 100 prisoners is each assigned a blue/red with 50/50 chance. Each prisoner cannot see their own hat, but can see the hats of everyone else (all 99 others). Once they see the others' hats, they can bet on what color hat they have on. Each person gets $1 if they're correct, and nothing if wrong.
- How do you maximize an individual's winnings?
- How do you maximize the collective group's winnings?
- What if you can bet more than $1? How much would you bet based on what you see?
Twists:
- Does coordinating beforehand help?
My Answer/Maybe The Real Question.
I think this is a trick question. If every blue/red assignment is random (and you're sampling with replacement), you are basically asking "if I have 99 fair coin toss results, what is the probability the next toss is heads?" So there's no way to maximize either individual or group's winnings.
I'm pretty sure the question was "sampling with replacement". But what if it wasn't? If it's a finite number of hats, equal amount of red and blue let's say...
Then you just pick the color you see less of, right? Every prisoner does that as well, so no need to coordinate, maximizing individual's winnings maximizes collective winnings?
No clue how to tackle part 3 though...