# Thread: Can the grid be filled?

1. ## Can the grid be filled?

Given binary sequences of equal length, let the "distance" between them be defined as the number of bits that would need to be flipped to convert one binary sequence to another. For example, the sequences 1111 and 1110 are a distance of 1 apart, because only the last digit must be changed to get from one to the other. Meanwhile, 1010 and 0101 are a distance of 4 apart, because all 4 digits must be changed to get from one to the other.

Consider binary sequences of length 8 (example: 10101010). Is it possible to find a group of 5 of them such that each is a distance of at least 5 from all the others? If so, give an example of such a group, thus producing a successful 5 x 8 grid. If not, prove that it is not possible to find any such group and that therefore the 5 x 8 grid cannot be filled.

2. ## Re: Can the grid be filled?

We first investigate what happens between three sequences.

Choose any sequence as the first one, $S_1$. Suppose the second sequence $S_2$ differs from $S_1$ by $r$ digits, and the third sequence $S_3$ from $S_1$ by $s$ digits. Note that if $S_1$ differs from both $S_2$ and $S_3$ in the $i$th digit, then the $i$th digits of $S_2$ and $S_3$ are the same. If $r,s\geq5$ then $S_2$ and $S_3$ must have at least $2$ digits the same. So the distance between $S_2$ and $S_3$ is at most $6$, i.e. it must be $5$ or $6$.

The argument is symmetrical in all three sequences. Hence $r,s\in\{5,6\}$ also.

Suppose $|S_2-S_3|=6$. Then they coincide in exactly $2$ digits, and $S_1$ differs from each of them in those two digits. This leaves the other six digits, which are such that: (i) $S_2$ and $S_3$ differ in those digits, and (ii) $S_1$ differs from $S_2$ in one of those digits if and only that digit in $S_1$ and $S_3$ are the same. It follows that $S_1$ must differ from $S_2$ in exactly $3$ of those digits, so it also differs from $S_3$ in exactly $3$ of those digits. In this case, $r=s=5$.

Now Suppose $|S_2-S_3|=5$. If $r=6$ we can apply the previous argument again and get $s=5$. Suppose $r=5$. Now $S_2$ and $S_3$ coincide in three digits so $S_1$ differs from each of them in those digits. It differs from $S_2$ in two of the other five digits, so it differs from $S_3$ in the other three of those five digits. In this case, $s=6$.

Hence, given any three sequences, two pairs each have a distance of $5$, and the distance between the third pair is $6$. Example: $S_1=00000000,\,S_2=00011111,\,S_3=11111000$.

Now we add a fourth sequence $S_4$. WLOG we can assume $r=s=5$ and $|S_2-S_3|=6$. Suppose $S_4$ differs from $S_1$ by $t$ digits. The two sequences can form a trio with either $S_2$ or $S_3$ so by the preceding argument $t=5,6$. Suppose $t=5$. Consider the three sequences $S_1,S_2,S_4$. Then $|S_2-S_4|=6$ since the distances between the other two pairs are $5$. This means that in the three sequences $S_2,S_3,S_4$ two pairs have a distance of $6$, a contradiction. So $t=6$. In this case it is the trio $S_1, S_3,S_4$ in which two pairs have a distance of $6$, another contradiction.

This shows that we can never find four sequences such that the distance between any pair of them is $5$ or more. If we cannot find four sequences, we certainly cannot find five.

3. ## Re: Can the grid be filled?

"This shows that we can never find four sequences such that the distance between any pair of them is 5 or more. If we cannot find four sequences, we certainly cannot find five."

It's a compelling enough argument, except I've been provided with an actual example of a 4 by 8 that maintains at least 5 differences between all:

10100000
01110101
11001011
00011110
________________

Now it may still be the case that finding a 5 by 8 is impossible, but if it is, it's not because finding a 4 by 8 is impossible, because it's not.