Two infinite hat problem and a question about what is ``well known''

Computational Complexity 2019-08-20

This is a joint post with David Marcus. You will see how he is involved in my next post. Two infinite hat problems based on one scenario. I am also curious if they are well known. 1) There are an infinite number of people, numbered 1,2,3,... There are 2 colors of hats. They can all see everyone's hat but their own. 2) The adversary is going to put hats on all the people. They will guess their own hat color at the same time. 3) The people can discuss strategy ahead of time, but must use a deterministic strategy and the adversary knows the strategy. 4) The people want to minimize how many they get wrong. 5) The adversary puts on hats to maximize how many they get wrong. I ask two questions and one meta-question: Q1: Is there a solution where they get all but a finite number of the guesses right? (I have blogged about a variant of this one a while back.) Q2: Is there a solution where they get all but at most (say) 18 wrong. (My students would say the answer has to be YES or he wouldn't ask it. They don't realize that I work on upper AND lower bounds!) Q3: How well known is problem Q1 and the solution? Q2 and the solution? I've seen Q1 and its solution around (not sure where), but the only source on Q2 that I know of is CAN'T TELL YOU IN THIS POST, WILL IN THE NEXT POST. So, please leave a comment telling me if you have seen Q1 or Q2 and solutions. And if so then where. Feel free to leave any comments you want; however, I warn readers who want to solve it themselves to not look at the comments, or at my next post.