I posed myself the problem of partitioning the integers $0\leqslant n<16$ into 4 equal parts, such that if they are expressed in 4-digit binary, any number selected can be switched to a number in any of the other 3 parts by simply flipping a $0$ into a $1$ and vice versa. For instance, this is such a partition (written as a matrix, each row being a group)
$$\pmatrix{0 & 3 & 13 & 14 \\ 1 & 6 & 8 & 15 \\ 2 & 5 & 11 & 12 \\ 4 & 7 & 9 & 10} $$ Indeed every number re-written as a 4-digit binary number gives:
$$ \pmatrix{0000 & 0011 & 1101 & \color{teal}{1110} \\ 0001 & \color{pink}{0110} & 1000 & 1111 \\ \color{teal}{0010} & 0101 & 1011 & 1100 \\ 0100 & \color{teal}{0111} & 1001 & 1010}$$ Then if we pick $6$ i.e. $0110$ in pink above, I can get to any other row by changing exactly one digit (in blue). This applies to every entry. I found other solutions as well that show more obvious patterns:
$$\pmatrix{0 & 1 & 14 & 15 \\ 2 & 3 & 12 & 13 \\ 4 & 5 & 10 & 11 \\ 6 & 7 & 8 & 9}\qquad\qquad\pmatrix{0 & 7 & 8 & 15 \\ 1 & 6 & 9 & 14 \\ 2 & 5 & 10 & 13 \\ 3 & 4 & 11 & 12} $$
My goal was to classify these, if at all possible. I noticed that each row sums to $30$, in other words $\frac{1}{4}\big(0+1+\cdots + 15\big)$, though I have not proved this is a necessary condition (it is however, not a sufficient condition). This did allow me to write a simple Python program to generate many more solutions.
An alternative way of viewing this is as a graph on $16$ vertices, representing $\{0,\dots,15\}$, where vertices are joined when it is possible to get from one to other by flipping a digit. This is a tesseract graph ($4$-regular graph on $16$ vertices). Then every partition corresponds to coloring vertices such that each vertex is joined to every other colour. Several observations can be made:
- once coloured, the graph can be partitioned into $4$ squares each with $4$ colours on them
- these graphs are bipartite, moreover in such colourings each colour will need to be appear exactly twice in each of the two disjoint sets.
- we can view the vertices as points in $\mathbb{R}^4$ where the binary representation become coordinates (i.e. $6$ is then $(0,1,1,0)$); under this lens the graph is the unit $4$-cube, neighbours of any vertex being those at a distance of $1$ (corresponding to the flipping of digits). In some sense this might be the 'heart' of what is happening here.
I've tried explicitly doing the colouring to see whether it would shed light on why the rows sum to $30$ but did not have much luck. There is always a line of symmetry (pictured below), and because if the graph is represented a certain way (as below), each point $n$ corresponds to an 'opposite' point $15-n$, this makes it clear why in the left example, every colour sums to $30$. There is symmetry on the right too but it's less clear what's happening in terms of summing things. It's possible the vertices could be rearranged such that the blue/green look like the yellow/red. Again though, I have not proved this. Anyway here are the pictures (these correspond to the first two examples above).
All this to say, is there more enlightening way of describing what is going on here? Why does every colour/group sum to $30$? I don't know whether there is a key observation I am missing that makes this all trivial, but would be interested to hear nonetheless!
Note: classifying partitions of $\{0,1,2,3\}$ (as $2\times 2$ matrices) is trivial, and through some basic analysis there is no other $m\times m$ where this can be done (other than the one discussed above): $m$ needs to be a power of $2$ otherwise there will not be enough 'material' for e.g. $m-1$ to match with, and once $m\geqslant 8$ i.e. there are too many rows for $0$ to match with.