Results 1 to 3 of 3

Thread: Can the grid be filled?

  1. #1
    JWS
    JWS is offline
    Newbie
    Joined
    Feb 2015
    From
    California
    Posts
    2

    Lightbulb 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member GLaw's Avatar
    Joined
    Jul 2015
    From
    Ilford
    Posts
    217
    Thanks
    113

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    JWS
    JWS is offline
    Newbie
    Joined
    Feb 2015
    From
    California
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. 2 objects to be filled into 3 spaces
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Jul 6th 2014, 04:37 PM
  2. Sand-filled timers questions
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Nov 5th 2013, 08:45 AM
  3. Oil tank is beeing filled up
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Nov 10th 2010, 08:14 PM
  4. Room Half-Filled
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Nov 28th 2008, 04:12 PM
  5. Determinant filled with unit and inverse.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Jun 25th 2006, 07:35 AM

Search Tags


/mathhelpforum @mathhelpforum