Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2005/iii/paper-33/4/a/solution
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 33 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let the distinct codewords be . No linearity assumption is needed. Sum their Hamming distances over unordered distinct pairs:Each summand is at least the minimum Hamming distance , so .
For coordinate , let be the number of codewords whose th bit is . Exactly unordered pairs differ at that coordinate. Summing coordinate contributions givessince . Combining the two bounds and dividing by gives , hence . Under , division is legitimate, proving the Plotkin boundBecause is an integer, it also satisfies the floor of the right-hand side. The binary alphabet is essential to the coordinate count; this proof applies to arbitrary binary block codes, not just linear ones.
New to topics? Read the docs here!