Binary labelling

Question

I learned of this question from a man in England and I find it fascinating.

You have a number of portraits which are distinguished from each other by binary labels. For example, in each portrait the person has either brown eyes or blue eyes and in each of the portraits the person is wearing a hat or not wearing a hat.

Now you want to consider a collection of portraits so that each portrait differs from each other portrait by at least four traits.
The question is if there are $n$ binary traits what is the largest number of portraits you can have so that any two portraits in the collection differ by at least four traits.

I approached this problem as follows. We work with binary numbers and we write the digits in reverse order.
So zero is 00000000000000, where here we are working with fourteen binary digits.
Now 1 = 10000000000000 and 2 = 01000000000000 and 7 = 11100000000000000 and so on.

Now let us start with 0 = 00000000000000. I wrote a computer program that looked a the numbers 1,2,3,4,.... until it found a number that differed from zero in four places. That number was 15 = 111100000000000000. Then the program went on look at 16,17,..... until it found a number that differed from 0 and 15 in at least four places. That number was 51 = 11001100000000. Continuing in this way the program found the next number is 60 = 00111100000000. Below I will write out the first few numbers.

    1    00000000000000
    2    11110000000000
    3    11001100000000
    4    00111100000000
    5    10101010000000
    6    01011010000000
    7    01100110000000
    8    10010110000000
    9    01101001000000
   10    10011001000000
   11    10100101000000
   12    01010101000000
   13    11000011000000
   14    00110011000000
   15    00001111000000
   16    11111111000000
   17    11000000110000

Here is what I found.

number of digits number	of portraits that all differ by four or more digits
4	2
5	2
6	4
7	8
8	16
9	16
10	32
11	64

From here on every time you add another digit you double the number of portraits. I have check this up to 512.

What I believe but can not prove is that this method is optimal so, for example, if you have 12 binary traits the largest number of portraits that all differ by at least 4 binary traits is 128. The other thing is that each of the binary numbers has an even number of ones.
Also, I believe but can not prove is that if there are n binary traits where n > 9 then the maximum number of portraits you can have that differ by at least 4 binary traits is 2^(n-5).

Answer 1

What you are constructing is known as a lexicographic code, or a lexcode for short. Lexcodes are pretty good, but usually not optimal. For example, it is possible to find $20$ binary vectors of length $9$ such that any two differ in at least four places, whereas you only found $16$. This following example was taken from the Sloane and MacWilliams book cited at the end, p. 57.

000 000 000
111 001 010
111 100 001
111 010 100
010 111 001
001 111 100
100 111 010
001 010 111
100 001 111
010 100 111
100 110 101
010 011 110
001 101 011
101 100 110
110 010 011
011 001 101
110 101 100
011 110 010
101 011 001
111 111 111 

In general, finding the largest code of a given length and distance is an open problem. This website by Andries E. Brouwer gives a table of the best known bounds on binary codes. The $d=4$ column is what is relevant to your question.

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978.