Demento-Santa (getting warmed up a.k.a. hot cocoa edition)

Let $G$ be the $(7,4)$ Hamming code. Here are the relevant properties: $G$ is a subspace of ${\mathbb F}_2^7$ of dimension $4$ , hence has $16$ elements, and every element of ${\mathbb F}_2^7$ is either in $G$ or can be changed to something in $G$ by changing one of its coordinates (and there is only one way to do this; $G$ is "perfect"). Each configuration of numbers on the elves' heads is an element of ${\mathbb F}_2^7$ , and each elf knows all but one of the coordinates. So from each elf's perspective, the configuration is one of two possible elements of ${\mathbb F}_2^7$ .

The strategy is as follows:

(1) If both of the possible elements are not in $G$ , don't guess.

(2) If one of the possible elements is in $G$ , guess that the configuration is NOT in $G$ .

If the configuration is not in $G$ , then exactly one elf will guess, and he will guess correctly. If the configuration is in $G$ , then all seven elves will guess wrong. The probability that the elves will win is $1-\frac{2^4}{2^7} = \frac78$ .

To see that this is the best strategy, consider that if we run the strategy with all $128$ possible configurations, the total number of correct and incorrect guesses must be equal. After all, each individual guess has a probability of exactly $1/2$ of being right. If the elves win with probability $p$ , then the winning configurations produce at least $128p$ correct guesses (since at least one elf has to guess right), and the incorrect configurations have at most $(1-p) \cdot 128 \cdot 7$ incorrect guesses (the maximum being when all the elves guess wrong). Hence $128p \le (1-p)\cdot 128 \cdot 7$ , which leads to $p \le 7/8$ .