Bit strings (pigeonhole principle)

Question

Here is how the question is posed:

Let $s_1$, $s_2$, $s_3, \ldots, s_{90}$ be 90 bit strings of length nine or less. Prove that there exist two strings $s_i$ and $s_j$ with $i \neq j$ that contain the same number of 0s and the same number of 1s (for example, 10110 and 11100).

I've tried figuring out how many bit strings of length nine have one 1 and eight zeroes, two 1s and 7 zeroes, etc. But I'm still confused...

Any idea how I might approach this? Thanks!

Answer 1

Put each string in a bucket labeled $(a,b)$, where $a$ and $b$ are nonnegative integers such that $a+b\leq 9$, according to the following rule: the string $s$ goes in the bucket $(a,b)$ if and only if $s$ has exactly $a$ 0s and $b$ 1s.

So you want to show that there is at least one bucket that has more than one string in it.

How many buckets are there? How many strings are there?

Answer 2

Note that checking two strings $s_i$ and $s_j$, with $i \neq j$, contain the same number of $0$'s and the same number of $1$'s essentially boils down to checking the sum of digits of the two strings are same.

Let $B_k$, where $1 \leq k \leq 9$, be the box containing strings of length $k$. Since there are $90$ strings, there exists an $n \in \{1,2,\ldots,9\}$, such that there are at-least $10$ strings of length $n$ in the box $B_n$.

Now note that a string of length $n$ can have any sum from $1$ to $n$. But we have at-least $10$ strings of length $n$ and $10 > n$. Hence, there exists two strings in $B_n$ with the same sum which also means that the number of $0$'s and the number of $1$'s in the two strings are the same.

Hence, there exists $s_i$ and $s_j$, with $i \neq j$, containing the same number of $0$'s and the same number of $1$'s.