# Thread: Prove there exists two strings

1. ## 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)

2. ## 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.

3. ## Re: Prove there exists two strings

could you explain more on this?

4. ## 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.