Results 1 to 6 of 6

Math Help - String of consecutive digits

  1. #1
    Junior Member
    Joined
    Feb 2011
    Posts
    25

    String of consecutive digits

    Let T={0,1,2} so that T^11 represents the set of all strings of eleven digits of T.
    a)for every T=T_1T_2...T_11 show that there is a pair T_iT_i+1 of consecutive digits that is repeated using the pigenhole principle.
    b)Find a string from T of 10 digits where no repetition exists.
    c)Find with justification a postive integer N such that every string of N digits of T contains a repeated triple T_iT_i+1T_i+2.

    Answers:
    a)Since there are 9 possible pairs and 11 digits one pair will be contained at least once in the string.Is this correct?
    b)0011220102.
    c)I don't know.How should I proceed?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: String of consecutive digits

    Quote Originally Posted by StefanM View Post
    Let T={0,1,2} so that T^11 represents the set of all strings of eleven digits of T.
    a)for every T=T_1T_2...T_11
    It's not good to redefine the letter T (it was an alphabet, now it is a string).

    Quote Originally Posted by StefanM View Post
    Answers:
    a)Since there are 9 possible pairs and 11 digits one pair will be contained at least once in the string.Is this correct?
    I am not sure you give sufficient details. The important fact is not that there are 11 digits but that they form 10 pairs of consecutive digits (first + second, second + third, ..., 10th + 11th). The rest is correct.

    b)0011220102.
    This string contains "01" twice.

    c)I don't know.How should I proceed?
    Find the number of triples that can be formed from the given alphabet; let's call it n. A string of N digits must contain at least n + 1 triples. So, n + 1 consecutive digits serve as the first digit of a triple, plus you need to add two digits to form the last triple.

    By the way, such sequences are called De Bruijn sequences. In that article, a string with no repeated pairs in alphabet {0, 1, 2} is denoted B(3, 2). De Bruijn sequences are cyclic; to get a regular sequence this problem is talking about one has to take B(k, n) and add the first n - 1 characters to the end.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2011
    Posts
    25

    Re: String of consecutive digits

    Thank you for the reply.I didn't knew their name but I knew about this type of sequences from coding and ecryption.
    for b)2001022112

    and c)There are 27 different triples
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: String of consecutive digits

    for b)2001022112
    This would work.

    c)There are 27 different triples
    Yes, so the minimal length with a guaranteed repetition is ...?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2011
    Posts
    25

    Re: String of consecutive digits

    A string of n digits has n-2 triples in it ,starting on every position but the last two.
    28+2 = 30 digits, it guarantees a repeat
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: String of consecutive digits

    That's correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: November 28th 2010, 09:22 PM
  2. division number with consecutive digits
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: June 6th 2010, 04:37 PM
  3. String
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 23rd 2009, 05:04 PM
  4. a loaded string
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: February 22nd 2009, 03:49 AM
  5. Replies: 2
    Last Post: April 3rd 2007, 12:31 PM

Search Tags


/mathhelpforum @mathhelpforum