Hat problems are fun and often require clever solutions. I have posted about one type of hat problem here.
In this post I ask three. For two of them I have a point to make which I will make when I post the answer later in the week. Feel free to post your thoughts and answers, BUT be warned that if you don't want to know the answer then don't look at the comments.
1) N people stand in a line and are numbered 1,2,3,..,n. If i < j then person i can see person j's hat color.
Hats are going to be put on the heads RANDOMLY- prob of RED or BLUE is 1/2. (so no adversary)
The people, in order 1,2,3,..., n either say RED or BLUE or PASS.
We want to maximize the probability that (1) someone does not say PASS, and (2) ALL who do not say PASS are correct.
They can meet ahead of time to discuss strategy but after the hats are on ALL they can say
is RED, BLUE, PASS and only when they are supposed to.
(Also try with 3 colors, 4 colors, etc.)
(ADDED LATER- some comments I got inspire a clarification and a new problem.
Clarify: NO adversary. The players are deterministic. So the prob of failure is based on the randomness of the hats. So you want to minimize the number of seq of R and B where the players mess up.
Another problem: Their IS an adversary but the players are allowed to flip coins. Now the prob of failure is based on the players coin flips.
2) omega people in a line are numbered 1,2,3,... If < j then person i can see person j's hat color.
An ADVERSARY is going to put hats on peoples heads RED or BLUE.
The people in order 1,2,3,... either say RED or BLUE
They can meet ahead of time and discuss strategy as in problem 1. The Adversary KNOWS the strategy
a) Prove or Disprove: there is a protocol such that they always get all but a finite number of hats right
b) Prove or Disprove: there is a protocol such that they always get all but at most ONE right.
3) N people in a circle (so they see each others hats).
An Adversary is going to put hats on peoples heads- there are c hat colors.
The people AT THE SAME TIME shout out a hat color.
Give a protocol that maximizes how many get it right (in the worst case). Show there is no better protocol.