Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2005/iii/paper-33/4/a/solution

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 gives
since . Combining the two bounds and dividing by gives , hence . Under , division is legitimate, proving the Plotkin bound
Because 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!