Instead of red and green, let us use labels \(0\) and \(1\).
The dwarfs first assign the numbers \(1\), \(2\), \(\dots\), \(7\) to
themselves.
Then each possible configuration can be represented as a sequence
\[\overrightarrow x ~=~ \left(x_1,x_2,\dots, x_7\right)\]
with \(x_i \in \{0,1\}\) for \(i=1:7\).
For sequences \(\overrightarrow x, \overrightarrow y\in\{0,1\}^7\) we define the distance \(d\left(\overrightarrow x, \overrightarrow y\right)\) between them as the total number of positions on which \(\overrightarrow x\) and \(\overrightarrow y\) differ. Formally,
\[d\left(\overrightarrow x,\overrightarrow y\right)=\sum_{i=1}^7 1_{x_i\neq y_i}.\]
We will show that there exists a set \(K\subseteq \{0,1\}^7\) with \(16\) sequences such that the distance between every two elements of \(K\) is at least \(3\). Assume for now that we constructed such set \(K\). Then the strategy of the dwarf \(i\) is the following:
- 1.
Denote by \(a_1\), \(a_2\), \(\dots\), \(a_{i-1}\), \(a_{i+1}\), \(\dots\), \(a_7\) the labels of the hats of the remaining \(6\) dwarfs.
- 2. Construct the two sequences
\begin{eqnarray*}
\overrightarrow{a_0}&=&\left(a_1, \dots, a_{i-1},0,a_{i+1},\dots, a_7\right)\mbox{ and}\\
\overrightarrow{a_1}&=&\left(a_1, \dots, a_{i-1},1,a_{i+1},\dots, a_7\right).
\end{eqnarray*}
- 3. Consider the three cases:
- Case \(0\). If \(\overrightarrow{a_0}\in K\), then shout ``\(1\).''
- Case \(1\). If \(\overrightarrow{a_1}\in K\), then shout ``\(0\).''
- Case \(2\). If \(\overrightarrow{a_0}\not\in K\) and \(\overrightarrow{a_1}\not\in K\), then stay silent.
Observe that if the configuration of hats \(\overrightarrow a\in K\),
then all the dwarfs will shout incorrectly and they will not go free.
We will now prove that if \(\overrightarrow a\not\in K\) then exactly six dwarfs are silent,
and one dwarf talks and will guess the correct color of his hat.
For each \(\overrightarrow k\in K\) the ball \(B_1\left(\overrightarrow k\right)\) with center \(\overrightarrow k\) and radius \(1\) has exactly \(8\) sequences. One of them is \(\overrightarrow k\) and the other \(7\) are not in \(K\). In addition, for different \(\overrightarrow k, \overrightarrow m\in K\) the balls \(B_1\left(\overrightarrow k\right)\) and \(B_1\left(\overrightarrow m\right)\) are disjoint. Otherwise, \(\overrightarrow k\) and \(\overrightarrow m\) would be at distance at most \(2\). We will prove that the union of all these balls is the entire set \(\{0,1\}^7\).
It suffices to prove that the sum of their cardinalities is \(2^7 = 128\),
and this follows immediately from the fact that there are \(16\) balls and each of them has \(8\) elements.
Assume now that \(\overrightarrow a\not \in K\). Then there exists exactly one element \(\overrightarrow k\in K\) such that \(\overrightarrow a\in B_1\left(\overrightarrow k\right)\). This means that the sequences \(\overrightarrow a\) and \(\overrightarrow k\) differ in exactly one coordinate, say coordinate \(i\). Then the \(i\)-th dwarf will construct two sequences. One of them will be precisely \(\overrightarrow k\), and the other will be \(\overrightarrow a\). The strategy of the dwarf is to pronounce the hat color that corresponds to the sequence \(\overrightarrow a\), thus saving the entire group of seven dwarfs.
The probability of dying is \(\frac{|K|}{128}=\frac{16}{128}=\frac18=12.5\%.\) Hence the probability that the dwarfs go free is equal to \(87.5\%\).
It remains to construct a set \(K\) with \(16\) elements that are at distance at least \(3\) from each other.
One such set is
\begin{eqnarray*}
K&=&\left\{
(0, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 1, 1, 1), \right.\\ &&
(0, 0, 1, 1, 0, 0, 1),
(1, 1, 0, 0, 0, 0, 1),\\ &&
(1, 0, 0, 1, 0, 1, 0),
(0, 1, 1, 0, 0, 1, 0),\\ &&
(1, 0, 1, 0, 1, 0, 0),
(0, 1, 0, 1, 1, 0, 0),\\ &&
(1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 0, 0, 0),\\ &&
(1, 1, 0, 0, 1, 1, 0),
(0, 0, 1, 1, 1, 1, 0),\\ &&
(0, 1, 1, 0, 1, 0, 1),
(1, 0, 0, 1, 1, 0, 1),\\ && \left.
(0, 1, 0, 1, 0, 1, 1),
(1, 0, 1, 0, 0, 1, 1)
\right\}.
\end{eqnarray*}
It is straightforward to verify that each two sequences are at distance at least \(3\).