Partition All $n$-bit Binaries into $n$ Parts For what values of $n$, it is possible to partition $\mathbb{Z}_2^n$ into $n$ disjoint parts, say $A_1, ..., A_n$  such that every element in $\mathbb{Z}_2^n$ is at most one-edit away from each part, i.e., the Hamming distance between $x$ and $A_k$ is at most 1 for all $x\in\mathbb{Z}_2^n$ and $k\in[n]$?
Moreover, if $n=2^m-1$ for some $m$, is it always possible to partition the space into $n+1$ parts with the same property?
Here are some observations.


*

*We can not hope for more than $n+1$ parts. If we can partition the space into $n+1$ parts. Then $n+1$ must divide $2^n$. Hence $n=2^m-1$ for some $m$. In fact, we can partition $\mathbb{Z}_2^n$ into $n+1$ parts for $n=1,3$.

*We can partition $\mathbb{Z}_2^n$ into $n$ parts for $n=2,4$, but NOT for $n=5$. This does not work for $n=5$ because one of the parts must have $\leq 6$ elements and it is not possible to have $6$ points in $\mathbb{Z}_2^n$ that 'controls' the entire space. In fact, there are at least 2 points that are 'not under control'.

 A: The answer to the second question is yes.
For $n=2^m-1$, there exists a binary Hamming code, which is a special type of a linear code. It is a linear subspace $H$ of $\mathbb{Z}_2^n$ of dimension $n-m$, such that every two elements of $H$ have Hamming distance at least three. More importantly, the $1$-neighborhoods of the elements of $H$ cover the whole cube $\mathbb{Z}_2^n$. Now the affine subspaces $H, H+e_1, \dots, H+e_n$, where $e_i$ is the vector with $i$th coordinate equal to $1$ and other coordinates zero, form a partition with required properties.
This also implies that the answer to the first question is yes if $n=2^m$.

Edit: One could also try to find some lower bounds on the size of the sets $A_i$, generalizing the second observation. Every $A_i$ has to be a binary 1-covering code of length $n$. 
See also http://www.sztaki.hu/~keri/codes/ for tables of the best bounds for small values of $n$. The lower bounds in the table for $R=1$ imply that the answer to the first question is no also for $n=6,9,10,12,14, \ldots$
