= 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
$$
\boxed{|B(x,j)|=\sum_{i=0}^j\binom ni.}
$$
For a $k$-code, radius-$k$ balls about codewords are disjoint, giving $|C|\sum_{i=0}^k\binom ni\leq2^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\leq|C|\sum_{i=0}^{2k}\binom ni$. 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 \b[$M(4,1)=2$].
Back to article page
