Sunday, July 21, 2019

Answer to both Infinite Hats Problems from the last post

(This is a joint post with David Marcus. You'll see why later.)

In a prior I posed two infinite hat problems. Today I post the solutions. Actually this is a copy of my last post with the solutions added, so it is self contained.

A Hat Problem that you have probably seen:

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 (the answers are in a document I point to) and one meta-question:

Q1: Is there a solution where they get all but a finite number of the guesses right? (If you have read my prior post on hat puzzles, here then you can do this one.)

Q2: Is there a solution where they get all but at most (say) 18 wrong.

Answers to Q1 and Q2 are here.

How did I get into this problem? I was looking at hat problems a while back. Then I began discussing Q1 and Q2 by email (Does the term discussing have as a default that it is by email?) with David Marcus who had just read the chapter of Problems with a Point on hat puzzles. After a few emails back and fourth, he began looking on the web for answers. He found one. There is a website of hat puzzles! It was MY website papers on Hat Puzzles! It is here. And on it was a relevant paper here. We did not find any other source of the problem or its solution.

Q3: How well known is problem Q2 and the solution? I've seen Q1 around but the only source on Q2 that I know of is that paper, and now this blog post. So, please leave a comment telling me if you have seen Q2 and/or the solution someplace else, and if so where.

The responses to my last post indicated that YES the problem was out there, but the proof that you could not get all-but-18 was not well known.

I THINK that all of the proofs that you can't do all-but-18 in the comment of the last post were essentially the same as the solution I pointed to in this blog. I would be interested if there is an alternative proof.