# Thread: Binary Sequence combinatorics

1. ## Binary Sequence combinatorics

The problem simply states that:
show that there cannot be 171 binary sequences such that each differ in at least four digits.

So far I've deducted that there should be some pigeonhole principle in here (I'm assuming, at least). So far I've written down that we should take the 2^12 different sequences and subtract the ones which only differ by one and those that differ only by two and then by three. I've tried this but with little success. Could I please have some guidance on how to go about this question?
thank you

2. ## Re: Binary Sequence combinatorics

Originally Posted by pikachu26134
The problem simply states that:
show that there cannot be 171 binary sequences such that each differ in at least four digits.
So far I've deducted that there should be some pigeonhole principle in here (I'm assuming, at least). So far I've written down that we should take the 2^12 different sequences and subtract the ones which only differ by one and those that differ only by two and then by three. I've tried this but with little success. Could I please have some guidance on how to go about this question?
As far as I know the is no universal agreement of the definition of Binary Sequence.
Look at this reference. As you can see there they assume an 8-bit string.
In that case your $\displaystyle 2^{12}$ makes no sense.

So you should define the terms in this posting.

For me a Binary Sequenc is any sequence of zeros and ones.

Thus you had best tell us what you are on about, i.e. define your terms,

3. ## Re: Binary Sequence combinatorics

By Binary Sequence, I mean any sequence including only the numbers 0 and 1 (base 2). When I say that each differs in at least four digits, I mean that if we have 0000 and 1111, they differ in four digits, as do 00000 and 11110. On the other hand, 0000 and 1110 do not differ by four digits.
I apologise about the previous ambiguity.

4. ## Re: Binary Sequence combinatorics

The OP was:
Originally Posted by pikachu26134
The problem simply states that:
show that there cannot be 171 binary sequences such that each differ in at least four digits.
Originally Posted by pikachu26134
By Binary Sequence, I mean any sequence including only the numbers 0 and 1 (base 2). When I say that each differs in at least four digits, I mean that if we have 0000 and 1111, they differ in four digits, as do 00000 and 11110. On the other hand, 0000 and 1110 do not differ by four digits.
You still have not clarified what kind of bit-strings the question is about: What is the length?

For example if the strings are of length seven then there are only $\displaystyle 2^7=128$ total strings.
So there is nothing to prove.

On the other hand, if the strings are of length $\displaystyle 100$ the statement is false.

5. ## Re: Binary Sequence combinatorics

The strings are of length 12 and hence there are 2^12 total strings

6. ## Re: Binary Sequence combinatorics

In terms of this paper (PDF), the problem asks to show that $\displaystyle A_2(12,4)<171$. By Corollary 1.3.1 on p. 12, $\displaystyle A_2(12,4)=A_2(11,3)$. In fact, Lemma 1.1 is sufficient to conclude that $\displaystyle A_2(12,4)\le A_2(11,3)$. Then Theorem 1.4 on p. 14 established the Hamming bound saying that $\displaystyle A_2(11,3)\le\frac{2^{11}}{\binom{11}{0}+\binom{11} {1}}$, which happens to be just smaller than 171.

This paper is a nice introduction to error-correcting codes and is a pleasant reading, so I don't think the time spent on understanding the results above would be lost.