# String of consecutive digits

• Aug 20th 2011, 11:01 AM
StefanM
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.

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?
• Aug 20th 2011, 02:48 PM
emakarov
Re: String of consecutive digits
Quote:

Originally Posted by StefanM
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
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.

Quote:

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

Quote:

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.
• Aug 20th 2011, 03:03 PM
StefanM
Re: String of consecutive digits
for b)2001022112

and c)There are 27 different triples
• Aug 20th 2011, 03:39 PM
emakarov
Re: String of consecutive digits
Quote:

for b)2001022112
This would work.

Quote:

c)There are 27 different triples
Yes, so the minimal length with a guaranteed repetition is ...?
• Aug 21st 2011, 08:57 AM
StefanM
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
• Aug 21st 2011, 09:46 AM
emakarov
Re: String of consecutive digits
That's correct.