Paper 4, Section II, E

Numbers and Sets | Part IA, 2018

For nNn \in \mathbb{N} let Qn={0,1}nQ_{n}=\{0,1\}^{n} denote the set of all 010-1 sequences of length nn. We define the distance d(x,y)d(x, y) between two elements xx and yy of QnQ_{n} to be the number of coordinates in which they differ. Show that d(x,z)d(x,y)+d(y,z)d(x, z) \leqslant d(x, y)+d(y, z) for all x,y,zQnx, y, z \in Q_{n}.

For xQnx \in Q_{n} and 1jn1 \leqslant j \leqslant n let B(x,j)={yQn:d(y,x)j}B(x, j)=\left\{y \in Q_{n}: d(y, x) \leqslant j\right\}. Show that B(x,j)=i=0j(ni)|B(x, j)|=\sum_{i=0}^{j}\left(\begin{array}{c}n \\ i\end{array}\right).

A subset CC of QnQ_{n} is called a kk-code if d(x,y)2k+1d(x, y) \geqslant 2 k+1 for all x,yCx, y \in C with xyx \neq y. Let M(n,k)M(n, k) be the maximum possible value of C|C| for a kk-code CC in QnQ_{n}. Show that

2n(i=02k(ni))1M(n,k)2n(i=0k(ni))12^{n}\left(\sum_{i=0}^{2 k}\left(\begin{array}{c} n \\ i \end{array}\right)\right)^{-1} \leqslant M(n, k) \leqslant 2^{n}\left(\sum_{i=0}^{k}\left(\begin{array}{l} n \\ i \end{array}\right)\right)^{-1}

Find M(4,1)M(4,1), carefully justifying your answer.

Typos? Please submit corrections to this page on GitHub.