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

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