Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 11I / b

Complete the square:If $M$ is even, an integer $N$ can equal $M/2$, giving the maximum $M^2/4$. If $M$ is odd, every integer $N$ is at least $1/2$ from $M/2$, giving the maximum $(M^2-1)/4$. Thus

At coordinate $j$, addition in ${\mathbb{F}}_2$ gives $x_j+y_j=1$ exactly when $x_j\ne y_j$. Therefore the number of ones in $x+y$ is exactly the number of coordinates in which the two words differ:

For column $j$, let $N_j$ of the $M$ codewords have a one. A pair contributes a one in that column exactly when one word is chosen from those $N_j$ words and the other from the remaining $M-N_j$. Hence column $j$ containsones among all pairwise sums. Part (i), summed over the $n$ columns, gives the upper boundThere are $\left(\genfrac{}{}{0ex}{}{M}{2}\right)$ rows, one for each unordered pair of codewords. By part (ii), every row has weight equal to that pair's distance, which is at least $d$. Therefore

Put $q=2d-n>0$. If $M$ is even, part (iii) givessoBecause $M$ is even,

If $M$ is odd, part (iii) instead givesCancelling $M-1$ yields $qM\le n=2d-q$, and thereforeSince $M$ is an integer, the same desired upper bound follows. Thus the binary Plotkin bound is