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.
So here's one (partially). Spoiler below I guess
ReplyDeleteLet h_i be the color of the i^{th} persons hat. Before the game starts the N people come up with a random string r_1, r_2, \ldots, r_N and all memorize it. Then they agree to the following protocol: For person i, if \exists j > i s.t. r_j == h_j, pass. O.w. shout out r_i and terminate the protocol.
The protocol always succeeds if the first person passes. If the the first person doesn't pass, then all the keys in front at different which is suppa unlucky (1/2^{n-1}), in which guess player one has to guess (1/2 err prob). Thus the protocol succeeds w.p 1-1/2^n. No idea how to show a matching lower bound though, except that, you know, nothings ever double exponential.
I think you have an answer to a slighly different problem.
ReplyDeleteMy problem was: NO adversary, hats put on at random. For that problem
you can get it except in ONE case, so prob of sucess is like yours,
but you can to it deterministically with an algorithm for close to yours.
Yours does that well when there IS an adversary but the players are allowed randomization. Great!
"We want to maximize the probability that (1) someone does not say PASS, and (2) ALL who do not say PASS are correct."
ReplyDeleteCorrect in terms of what? What is the goal? Are they trying to guess their own hat color or someone else's?
"Hats are going to be put on the heads RANDOMLY- prob of RED or BLUE is 1/2."
Does this mean that there are exactly as many red as blue hats in the hat reservoir, or does it mean that as we place a hat on someone's head, we flip a coin to decide whether to color it red or blue?
I love a good puzzle. But this one is way underspecified.
I want a deterministic strategy (so no coin flips, no random string)
ReplyDeleteto minimize the prob of failure. There is no adversary--- so effectively
I want to minize the number of sequences of R's and B's where
either everyone passes OR someone who gives a guess gets it wrong.
what you have is very close to that.
The key diff between the problem you solved and the one I intended to ask:
I intended to have the hats put on randomly, but players det
So my prob of failure is based on the random sequence of hats.
You solved the problem where their is an adversary but the players get to use randomization. So your prob of failure is based on the players coin flips and is not depending on the randomness of the hats, which is why you can have an adversary.
I will modify the post, though oddly enough, my NOT specifiying that it was deterministic led to your solution and a great new problem and solution.
ahh yeah, you're right. When I read the problem, I mentally pigeonholed myself into a solution where first I picked some random bits - any string \in \{0,1\}^n will work then right? And the one failure string is when it just so happens that flips coincide with it
ReplyDeleteThese are fun, here's a stab at 3 (spoilers below, again)
3) Like in problem 1, it seems hopeless since you don't get any information from the world except what everyone else is wearing. The wording of the question is a tip off that maybe you can't do that great which begs the question, can you do anything?
Here's a protocol that gives you something: After the hats go on, each player shouts out the most common color they see (breaking ties arbitrarily). Claim: The number of correct guesses is 1/c (in expectation).
Pf idea: Let N_i be the number of agents with hat color i and c be the number of colors. By our assumption (and pigeonhole), \exist N_i > N/c, and every agent will guess color i. N_i of them will be right giving the claim.
Remark: Actually this is not quite right. If, for example, exactly half the group gets red and the other half gets blue, then everyone will guess the opposite color that they see and no one will get it right. The dirty fix is to have each agent guess proportional to what they see, which a little fiddling I think that rule gives 1/c correct in expectation (where the randomness is each agents decision rule)
Lowerbound: If the adversary picks the hat colors at random, ensuring that N-i = N_j \for i,j it seems intuitive that this is the best you can do. No idea how to prove it
I didn't specify that I wanted a deterministic protocol in the question (is deterministic or randomized the default? I had thought det). So I'll do it now- try to do as best you can with a deterministic protocol.
ReplyDelete