Partitioning $\{0,1\}^n$ into $n$ sets

Question

I am working on an answer to the question

Magic trick based on deep mathematics

and came across the following problem: I am trying to partition the cube $\{0,1\}^n$ into $n$ sets $P_1,\dots,P_n$ such that, for any point $x\in\{0,1\}^n$ and any $i\in\{1,\dots,n\}$, there exists a point $y\in P_i$ such that $x$ and $y$ differ in at most one term. Using my computer I know that this is possible for $n\leq 4$, impossible for $n=5$ and $6$, and possible for $n=7$ and $8$ (by brute force integer programming). For example, one solution for $n=4$ is \begin{align*} P_{1} & =xyyy\text{ or }xxxx\\ P_{2} & =xyxx\text{ or }xyyx\\ P_{3} & =xxyx\text{ or }xyxy\\ P_{4} & =xxxy\text{ or }xxyy \end{align*} where $x$ and $y$ are separate values in $\{0,1\}$. My question is: can this partition (or something like it) extend to $n=8$ in a simple way? Alternatively, are there any values of $n$ for which there is a simple and natural partition?

To clarify my notation here is an explicit list of the $P_i$'s for $n=4$:

\begin{align*} P_{1} & =0111\text{ or }1000\text{ or }0000\text{ or }1111\\ P_{2} & =0100\text{ or }1011\text{ or }0110\text{ or }1001\\ P_{3} & =0010\text{ or }1101\text{ or }0101\text{ or }1010\\ P_{4} & =0001\text{ or }1110\text{ or }0011\text{ or }1100 \end{align*}

Answer 1

You are looking for a binary code with covering radius 1, which is in general a well studied and difficult problem.

Basically you need a collection of codewords such that the union of the spheres with radius 1 around them cover the whole space.

If you took any of your collections, say $P_1$ for length 4, you could obtain what you need for length $n=8,$ by the following construction.

Take $P_i,P_j$, create the sets $U\otimes P_i$ and $P_j \otimes U$ where $U$ (the universe) is the set of all $4-$tuples. The union of these two sets will give you a covering code with radius 1. So picking $i=j=1,$ gives \begin{align*} P_{1} \otimes U & =0111xxxx\text{ or }1000xxxx\text{ or }0000xxxx\text{ or }1111xxxx\\ U\otimes P_{1} & =xxxx0111\text{ or }xxxx1000\text{ or }xxxx0000\text{ or }xxxx1111 \end{align*} where $xxxx$ means we take all possible bit patterns of length $4.$

Edit: A simpler and optimal construction is to take the codewords of the perfect Hamming code with length 7 bits and minimum distance 3. This code has 16 codewords, and covering radius 1. Add a zero bit and a 1 bit at the end of each codeword to obtain an optimal set of only 32 codewords covering $\{0,1\}^8$ with covering radius 1.

Since all binary Hamming codes with lengths $2^m-1$ are perfect, and have $2^{2^m-m-1}$ codewords, the above construction yields optimal covering codes with covering radius 1 and $2^{2^m-m}$ codewords when $n=2^m.$

It is known in general that for any length $n$ the quantity $2^n/(n+1)$ is a lower bound to the cardinality of any binary code with covering radius 1.