Consider the 4 people hat game. Since 4 is not of the form 2k −1, we know there will not be any maximally eective strategy for this version of the game.
(a) What is the best possible probability of winning for this game. Using a simple argument, explain why it can’t be higher.
(b) Describe a strategy that has this probability of winning. Explain why your strategy is not maximally effective, and which part of the definition it fails to satisfy.
You might want describe your strategy geometrically by giving a labeling of the vertices of a 4-dimensional cube. In this case, the second part of the question becomes: Why doesn’t your labeling satisfy the conditions in Proposition 3. As an aside, we call a 4-dimensional cube a tesseract. Here is a representation that you might find useful.