Problem 10.3. Let $A$ be the set of all 4-tuples of 0 and 1. Two such 4-tuples are called neighbors if they coincide exactly at three positions. Let $M$ be a subset of $A$ with the following property: any two elements of $M$ are not neighbors and there exists an element of $M$ which is neighbor of exactly one of them. Find the minimum possible cardinality of $M$.
10.3. Consider a table with rows corresponding to the elements of $A$ and column corresponding to the elements of $M$. We write $\times$ in a cell if the element of $A$ in the respective row is adjacent to the element of $M$ in the respective column. Let $|M|=k$. It follows from the given condition that there are no two equal rows which means that $M$ has at least 16 different subsets. Since a set with $n$ elements has $2^{n}$ subset, we get $k \geq 4$.

Any row has exactly five adjacent and thus any column contains exactly five $\times$, i.e., the total number of $\times$ is $5 k$. A minimal number of $\times$ by rows is attained if one row contains no $x, k$ rows contain one $\times,\binom{k}{2}$ rows contain two $\times$, etc.

If $k=4$, then all the subsets of $M$ are 16 and hence any subset of $M$ appears exactly once as a adjacent set to some element of $A$. Then we have one row with no $\times, 4$ rows with one $\times, 6$ rows with two $\times, 4$ rows with three $\times$ and one row with four $x$. The total number of $x$ becomes $32>20$, a contradiction.

For $k=5$ one has $25 \times$. Their minimal number by rows is attained when one row contains no $\times, 5$ rows contain one $\times$ and 10 rows - two $\times$. Since $5.1+10.2=25$ the distribution of $x$ must be exactly the one described above. This means that any two elements of $M$ are simultaneously adjacent to some element of $A$.

It is easy to see that if two elements of $M$ do not coincide at at most two positions, then there is no an element of $A$ that is adjacent to them. Hence any two elements of $M$ do not coincide at one or two positions. If there are two elements which do not coincide at one position, we may assume that they are $a=0000$ и $b=1000$. The adjacent to $a$ and $b$ in $M$ are 0000 and 1000 . So the rows of $a$ and $b$ coincide, a contradiction. This shows that any two elements of $M$ are different at exactly two positions. We may assume that $0000 \in M$. Then the remaining 4 elements are among 0011, 1100, 0101, 1010,1001 and 0110. But among any of the pairs $(0011,1100),(0101,1010)$ and $(1001,0110)$ at most one element can be chosen, a contradiction.

For $k=6$ the set $M=\{0000,1111,0111,0100,1001,0101\}$ separates any two elements of $A$.

Hence the desired minimal number is 6 .