Let $s _ { 1 } , s _ { 2 } \ldots , s _ { 101 }$

question 145

Essay

Let $s _ { 1 } , s _ { 2 } \ldots , s _ { 101 }$ be 101 bit strings of length at most 9. Prove that there exist two strings, $s _ { i }$ and $s _ { j }$ where $i \neq j$ that contain the same number of $0 \text { 's }$ and the same number of $\text { 1's. }$ (For example, strings 001001 and 101000 contain the same number of $\text { 0's }$ and the same number of $\text { 1's. }$ )