this is a homework question from my first networking course. it was
presented without much fanfare or background material, as if the answer
should be intuitive to anyone who has rudimentary math skills. I
apparently don't.


"definitions:

string - group of consecutive 1's and 0's
string length - number of 1's and 0's in a string
n-tuplet - string of length n


example:

string - 00101100010
string length - 11
this string contains 10 overlapping 2-tuplets (i.e., 00 01 10 01 11 10
00 00 01 and 10)


questions:

how long can a string be if no 4-tuplet can appear more than once?
how about n-tuplet?"


ideas anyone?

A_StClaire_@hotmail.com wrote:
Not sure, but I'd say you have to measure first how many /different/
pairs (2-tuplets) of 0 and 1 are possible. Well, these are obviously 4:
'00' ; '11' ; '01' ; '10' which is measured as 2*2 (two different values
times two digits).

Then you have to measure how many /different/ 4-tuplets are possible
with these 4 different pairs. I'd approach the problem this way: For
easier handling, just assign the 2-tuplets their decimal value:
00b = 0d ; 11b = 3d ; 01b = 1d ; 10b = 2d

Now you have 4 different numbers, so there are 4*4 different
permutations possible (4 possible values times 4 digits). That's 16
permutations (possible ways to order the digits).

16 different permutations times 4 digits times 2 digits (remember that
each of the element was actually two binary digits) is 128 digits, so
the minimum string length which comprises all minimal possible
permutations is 128 characters long.

Please correct me if I don't make sense

Regards,
Matthias

A_StClaire_@hotmail.com wrote:
pull out your old stats book. it's back to permutations and
combinations.
HTH,
ed

Matthias Kaeppler wrote:
Even though you are making sense, I don't think you are correct. In the
explanation, they specify that a string with length 11 has 10 tupels, so
your example would have 125 tuplets. As there are only 16 unique tupels,
there are many duplicates.

The 2-tuplet example is simple. Combinatorials show us that there should be
no more than 4 tupels (as you has shown us as well). a 5-digit string
contains 4 tuplets, and as luck would have it, this string suffices:

00110

Then how much _can_ the length of a 4-tuplet string be? Well, at least no
longer than 19 (which contains 16 tuplets). But I am not sure (missing the
mathematical background as well) that you can fit _all_ 16 tuplets into a
19-digit string.

For fun, after writing most of this mail, I tried a 3-tuplets version as
well, because it should be possible to figure this out by hand as well, and
guess what? (I hope I didn't make any mistake)

0111001000

10 digits, as expected (2^n + n - 1, being 8 + 3 - 1).

I know I did the homework now, but I hope you understand the logic behind
it.

Good luck,
--
Martijn
http://www.sereneconcepts.nl

Martijn wrote:
) The 2-tuplet example is simple. Combinatorials show us that there should be
) no more than 4 tupels (as you has shown us as well). a 5-digit string
) contains 4 tuplets, and as luck would have it, this string suffices:
)
) 00110
)
) Then how much _can_ the length of a 4-tuplet string be? Well, at least no
) longer than 19 (which contains 16 tuplets). But I am not sure (missing the
) mathematical background as well) that you can fit _all_ 16 tuplets into a
) 19-digit string.

You don't need mathematical background for that, you just need to try and
find such a 19-digit string. Although I think a mathematical proof exists
that you can find such a string for any length.

) For fun, after writing most of this mail, I tried a 3-tuplets version as
) well, because it should be possible to figure this out by hand as well, and
) guess what? (I hope I didn't make any mistake)
)
) 0111001000
)
) 10 digits, as expected (2^n + n - 1, being 8 + 3 - 1).

For fun, I'll try to find one for quad-tuplets.

0000100110101111000

There, that took all of five minutes. I worked left to right, and
I chose 0, unless that would mean a duplicate entry, and I backtracked
when neither 0 or 1 was possible. I only had to backtrack a few times.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

thx for your replies, all.

Martijn wrote:


You've got 100 twice there.

But it's still better than I could come up with

-Peter


--
Pull out a splinter to reply.

Willem wrote:
Actually, I did make a mistake, it should have been:

0011101000

or

0001011100

(obviously they can be reversed)

Yeah, there is a pattern (fractal) visible that will allow you to solve
these relatively easily. Just the same way you could solve the 5-tuplet
version (note that the beginning and end are perticularly easy) and should
take you no longer than the aformentioned five minutes either.

Greets,

--
Martijn
http://www.sereneconcepts.nl

Peter Ammon wrote:
Yeah, I noticed that, 'cause 101 was missing - Ironically, that's part of my
email address

--
Martijn
http://www.sereneconcepts.nl