Thread: Prove there exists two strings

Let s₁, s₂, ..., s₁₀₁ be 101 bit strings of length at most 9. Prove that there exist two strings, s_i and s_j, 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)

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.

could you explain more on this?

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 = H₀ ∪ H₁ ∪ ... ∪ H₉ where ∪ denotes the union of sets and H_k = {(m, n) | m + n = k} for each 0 ≤ k ≤ 9. Also, all H_k are disjoint. Therefore, |H| (i.e., the number of elements in H) equals |H₀| + |H₁| + ... + |H₉|. Find |H_k| and |H| and compare it with 101.