Results 1 to 6 of 6

Math Help - Binary Sequence combinatorics

  1. #1
    Junior Member
    Joined
    Jul 2011
    Posts
    53

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

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1

    Re: Binary Sequence combinatorics

    Quote Originally Posted by pikachu26134 View Post
    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.

    Thus you had best tell us what you are on about, i.e. define your terms,
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2011
    Posts
    53

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

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1

    Re: Binary Sequence combinatorics

    The OP was:
    Quote Originally Posted by pikachu26134 View Post
    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2011
    Posts
    53

    Re: Binary Sequence combinatorics

    The strings are of length 12 and hence there are 2^12 total strings
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

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

Similar Math Help Forum Discussions

  1. binary
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: October 10th 2012, 11:05 AM
  2. Binary matrix combinatorics
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 19th 2011, 08:05 PM
  3. Replies: 0
    Last Post: July 4th 2010, 12:05 PM
  4. Binary
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 20th 2009, 08:30 PM
  5. Binary
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 1st 2008, 12:28 PM

Search Tags


/mathhelpforum @mathhelpforum