# Bit strings (pigeonhole principle)

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!

-
What is the symbol between $i$ and $j$ supposed to be? Is it $\neq$? –  Arturo Magidin Nov 28 '11 at 3:44
yes, the not-equals sign –  FrodoHackins Nov 28 '11 at 3:52
Okay, I've fixed it; the website supports $\LaTeX$ (see here, for example). –  Arturo Magidin Nov 28 '11 at 3:54

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?

-
there are 90 strings and there are as many buckets as there are values of a and b such that a+b <= 9. –  FrodoHackins Nov 28 '11 at 3:55
@TwirlingHearth: And how many buckets is that? If it's fewer than 90 buckets, then... So, is it fewer than 90 buckets, or is it exactly 90, or is it more than 90? –  Arturo Magidin Nov 28 '11 at 3:56
It would be 10+9+...+3+2. If the bit string is nine long, then it could be zero 0s and nine 1s, one zero and eight ones, etc. Then, it's one less than that for the subsequent 8-bit, 7-bit, etc. strings. 54 total. –  FrodoHackins Nov 28 '11 at 4:02
@TwirlingHearth: So, since there are only 54 buckets, but you are putting 90 strings in them, then... –  Arturo Magidin Nov 28 '11 at 4:13
Indeed that is the conclusion. Thank you very much! :-) –  FrodoHackins Nov 28 '11 at 5:16

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.

-
+1 Neat solution. –  Srivatsan Nov 28 '11 at 4:49