# Binary Sequence combinatorics

• September 22nd 2013, 05:24 PM
pikachu26134
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
• September 22nd 2013, 06:48 PM
Plato
Re: Binary Sequence combinatorics
Quote:

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 $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.

• September 22nd 2013, 06:55 PM
pikachu26134
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.
• September 23rd 2013, 06:35 AM
Plato
Re: Binary Sequence combinatorics
The OP was:
Quote:

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.

Quote:

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 $2^7=128$ total strings.
So there is nothing to prove.

On the other hand, if the strings are of length $100$ the statement is false.
• September 23rd 2013, 04:00 PM
pikachu26134
Re: Binary Sequence combinatorics
The strings are of length 12 and hence there are 2^12 total strings
• September 24th 2013, 10:11 AM
emakarov
Re: Binary Sequence combinatorics
In terms of this paper (PDF), the problem asks to show that $A_2(12,4)<171$. By Corollary 1.3.1 on p. 12, $A_2(12,4)=A_2(11,3)$. In fact, Lemma 1.1 is sufficient to conclude that $A_2(12,4)\le A_2(11,3)$. Then Theorem 1.4 on p. 14 established the Hamming bound saying that $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.