Past exam of the mathematics course of the University of Cambridge / 2018 / ia / Paper 4 / 6E / Solution

The Hamming distance satisfies the triangle inequality coordinate by coordinate: if $x_i\ne z_i$, then $x_i\ne y_i$ or $y_i\ne z_i$. Summing these indicator inequalities proves the claim. A word at distance exactly $i$ from $x$ is obtained by choosing the $i$ coordinates to flip, so

For a $k$-code, radius-$k$ balls about codewords are disjoint, giving $|C|{\sum }_{i=0}^k\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le 2^n$. Conversely, take a maximal code of minimum distance $2k+1$. Its radius-$2k$ balls cover $Q_n$, since an uncovered word could otherwise be added, so $2^n\le |C|{\sum }_{i=0}^{2k}\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. Maximizing gives the requested coding bounds.

For $(n,k)=(4,1)$, translate a codeword to $0000$. Every other word has weight at least three, but any two distinct length-four words of weight at least three have distance at most two. Thus at most one can accompany $0000$, while $\{0000,1111\}$ works. Hence $M(4,1)=2$.