Results 1 to 4 of 4

Math Help - Prove there exists two strings

  1. #1
    Newbie
    Joined
    Jun 2012
    From
    -
    Posts
    11

    Prove there exists two strings

    Let s1, s2, ..., s101 be 101 bit strings of length at most 9. Prove that there exist two strings, si and sj, where i not equal to j, that contain the same number of 0s and the same number of 1s. (eg: strings 001001 and 101000 contain the same number of 0s and the same number of 1s)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Prove there exists two strings

    I think it's enough to take 56 strings. Use pigeonhole principle where pigeons are strings and holes are ordered pairs (m, n) such that m + n ≤ 9.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2012
    From
    -
    Posts
    11

    Re: Prove there exists two strings

    could you explain more on this?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Prove there exists two strings

    Below, the variables m, n and k range over nonnegative integers. So, the set of holes is H = {(m, n) | m + n ≤ 9}. Each string is mapped into a hole from H: if s is a string, m is the number of 0's in s and n is the number of 1's in s, then m + n ≤ 9 and s is mapped into (m, n). If we prove that the number of strings is strictly greater than the number of holes, then there must be at least two strings in one hole, which is what the problem asks to prove.

    Note that H = H0 ∪ H1 ∪ ... ∪ H9 where ∪ denotes the union of sets and Hk = {(m, n) | m + n = k} for each 0 ≤ k ≤ 9. Also, all Hk are disjoint. Therefore, |H| (i.e., the number of elements in H) equals |H0| + |H1| + ... + |H9|. Find |Hk| and |H| and compare it with 101.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove there is a number that exists
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 24th 2011, 02:20 AM
  2. How to prove such a sequence exists
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: September 6th 2011, 08:49 AM
  3. How to prove that this limit does exists...
    Posted in the Calculus Forum
    Replies: 4
    Last Post: April 26th 2011, 07:51 AM
  4. Prove that exists m among ai whose sum is at least m
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 11th 2011, 06:11 PM
  5. How to prove that a limit exists at 0.
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: March 27th 2011, 02:22 PM

Search Tags


/mathhelpforum @mathhelpforum