Results 1 to 2 of 2

Math Help - Stringology problem

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    50

    Stringology problem

    hi,


    Yesterday I was asked about a problem coming from stringology. The problem was to prove something basic about strings. However, i am not a good mathematician as i ought to be so i am turning to you . The problem was:


    Let S=s_{1},s_{2},..s_{n} be a string such that s_{i}\in \sum is its i-th letter and \sum the alphabet.


    Theorem: Given S, a substring of length 1 starting at position i is either a unique or repeated.

    Proof: ???



    so the problem is that i should show that any encountered letter is repeated somewhere else in the string or it occurs only once. However i don't know where to start. Also i am not quite sure if this is well-defined at all. At first i thought this looks like the case where i can prove that every number element of natural numbers is either odd or even but there is no such regularity as with natural numbers. so i am wondering is there a way to prove this or not. what necessary additional information is required to prove this statement? Does anyone know about any similar cases ?

    thnx
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Stringology problem

    I may not understand properly what "unique" and "repeated" means here, but there are two cases: either s_i occurs in the rest of the string, in which case it is repeated, or it does not, in which case it is unique. I think this is obvious.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum