[seqfan] Partitioning the n-cube into sets with mutual distance 1

Neil Sloane njasloane at gmail.com
Wed Aug 10 19:25:47 CEST 2016


Partition the 2^n vertices of the n-cube into M subsets so that the Hamming
distance between any two subsets is exactly 1. What is the max value of M?

According to this paper:

Blokhuis, A., Metsch, K., Moorhouse, G. E., Ahlswede, R., & Bezrukov, S. L.
(1993). Partitioning the n-cube into sets with mutual distance 1. Applied
mathematics letters, 6(4), 17-19
(If you look on the web, there is a copy on ResearchGate),
for n=0,1,2,3,4 the answers are M = 1,2,3,4,8

For n=4, here is a solution:
0000,1111
1000, 0111
0100,  1010
0010, 1001
0001, 1100,
0011, 1110
0110, 1101
0101, 1011

There are 169 sequences in the OEIS that match 12348, and the server is too
slow to check them all.

Can anyone find a couple more terms?



More information about the SeqFan mailing list