Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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
add comment

2 Answers 2

up vote 3 down vote accepted

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?

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
+1 Neat solution. –  Srivatsan Nov 28 '11 at 4:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.