Results 1 to 2 of 2

Math Help - Prove a property about a bit string

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Prove a property about a bit string

    How can I prove that in a bit string, the string 01 occurs at most one more time than the string 10?

    I have tried as follows:

    Let P(n): 01 occurs at most once more than 10 in an n-bit string.

    P(1): 0, 1
    P(2): 00, 01, 10, 11
    P(3): 000, 001, 010, 011, 100, 101, 110, 111

    Assume P(j) for  1 \leq j \leq k

    Consider P(k + 1):

    Here I have to somehow show that in the 'worst case' where there already exists one 01 sequence more than 10 that regardless of where this extra bit is added, it will either create a 10 sequence, 00, 11 or 010 where the latter obviously adds both a 10 and 01 sequence to the count and allows the premise to hold true.
    How can I show this for an arbitrary k length bit string?

    What if there is a string of k bits like this: xxxxx00, which already has one 01 more than 10, and I add the extra bit as such: xxxxx00 -> xxxxx001, i.e. at the end, where the xxxxx part of the bit-string already contains one 01 more than 10. I don't think that it is possible to have this configuration, but how can I prove this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    You need a stronger induction statement. Let #(01, s) denote the number of occurrences of 01 in a string s, and similarly for #(10, s). Then you could use the following.

    \begin{array}{c|c}<br />
\mbox{If $s$ has the shape} & \mbox{then $\#(01,s)-\#(10,s)$ is}\\<br />
\hline<br />
0\dots0 & 0\\<br />
0\dots1 & 1\\<br />
1\dots0 & \llap{$-$}1\\<br />
1\dots1 & 0<br />
\end{array}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Prove by Archimedian property
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: February 28th 2011, 07:44 PM
  2. Replies: 1
    Last Post: February 20th 2011, 04:11 PM
  3. [SOLVED] Prove the composite argument property for cos(A-B)
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: July 22nd 2010, 02:40 PM
  4. PROVE LOG PROPERTY!
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 12th 2008, 10:46 PM
  5. prove inequality property
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 8th 2008, 07:07 PM

Search Tags


/mathhelpforum @mathhelpforum