4
$\begingroup$

How many bit strings of length $8$ have either exactly two $1$-bit among the first $4$ bits or exactly two $1$-bit among the last $4$ bits?

My solution:

A bit only contains $0$ and $1$, so $2$ different numbers, i.e., $0$ and $1$. For the first part we have $2^6=64$ ways. Similar for the other way. Hence there exists $2^4=16$ bit strings. Is my answer true?

Update: I mean $2^6+2^6-2^4=112$ bit strings

$\endgroup$
0
0
$\begingroup$

How many bit strings of length 8 have either exactly two 1-bit among the first 4 bits or exactly two 1-bit among the last 4 bits?

The simplest solution is the best. There are only 256 possibilities to check so just list them!

00000011 00000101 00000110 00001001 00001010 00001100 00010011 00010101
00010110 00011001 00011010 00011100 00100011 00100101 00100110 00101001
00101010 00101100 00110000 00110001 00110010 00110011 00110100 00110101
00110110 00110111 00111000 00111001 00111010 00111011 00111100 00111101
00111110 00111111 01000011 01000101 01000110 01001001 01001010 01001100
01010000 01010001 01010010 01010011 01010100 01010101 01010110 01010111
01011000 01011001 01011010 01011011 01011100 01011101 01011110 01011111
01100000 01100001 01100010 01100011 01100100 01100101 01100110 01100111
01101000 01101001 01101010 01101011 01101100 01101101 01101110 01101111
01110011 01110101 01110110 01111001 01111010 01111100 10000011 10000101
10000110 10001001 10001010 10001100 10010000 10010001 10010010 10010011
10010100 10010101 10010110 10010111 10011000 10011001 10011010 10011011
10011100 10011101 10011110 10011111 10100000 10100001 10100010 10100011
10100100 10100101 10100110 10100111 10101000 10101001 10101010 10101011
10101100 10101101 10101110 10101111 10110011 10110101 10110110 10111001
10111010 10111100 11000000 11000001 11000010 11000011 11000100 11000101
11000110 11000111 11001000 11001001 11001010 11001011 11001100 11001101
11001110 11001111 11010011 11010101 11010110 11011001 11011010 11011100
11100011 11100101 11100110 11101001 11101010 11101100 11110011 11110101
11110110 11111001 11111010 11111100

There are 156 such strings.

Do you still believe there are only 112? If so, then which ones did I either list twice, or list in error?

$\endgroup$
1
  • $\begingroup$ I am convinced, thank you $\endgroup$ – user530832 Feb 15 '18 at 13:13
3
$\begingroup$

I lost your logic. By symmetry, amount of strings with exactly 2 ones in the first four (call this group $F$) is identical to the ones with exactly 2 ones in the last four (call this group $L$).

Then your desired amount is $|F| + |L| - |F \cap L|$.

To compute $F$, note that you have exactly $\binom{4}{2} = 6$ ways to pick the location of the ones in the first four, which fixes your picks to be ones and the other two of the first four to be zeros. In other words, this fixes the first four bits, and the rest can be manipulated in $2^4=16$ ways.

Can you finish computing $|F|$? We already said $|L|=|F|$ and can you compute $|F \cap L|$ by a similar technique?

$\endgroup$
7
  • $\begingroup$ I still belive that it should be $2^6+2^6-2^4=112$ ways. $\endgroup$ – user530832 Feb 14 '18 at 16:40
  • $\begingroup$ @M.Rasmussen your mistake is not automatically setting the other 2 bits to zero. The way you compute, consider, for example, the first group, with exactly 2 ones in the first four bits. $2^6$ you are getting counts the number of bit strings with 6 places, but (a) you did not count that there are multiple ways in spreading the ones among the first four and (b) you are including the string 11111111 as legal, whereas you must have exactly 2 ones in the first four, and this string has 4. $\endgroup$ – gt6989b Feb 14 '18 at 17:25
  • $\begingroup$ Ohh okay. I see, so all other "empty" spaces must be 0 if you know what I mean. $\endgroup$ – user530832 Feb 14 '18 at 17:49
  • $\begingroup$ Update: I get 156 now. But to make sure I understand it, what if I change the problem to this: "How many bit strings of length $12$ have either exactly four $1$-bit among the first $6$ bits or exactly four $1$-bit among the last $6$ bits?" Then I get the answer: 122655 is that correct? I did the same proces like the original question. $\endgroup$ – user530832 Feb 14 '18 at 17:57
  • $\begingroup$ @M.Rasmussen Then both elementary groups are $|F| = |L| = \binom{6}{4} \cdot 2^6$ and their intersection is $|F \cap L| = \binom{6}{4} \binom{6}{4}$ so you end up with $$|F| + |L| - |F\cap L| = 2 \cdot \binom{6}{4} \cdot 2^6 - \binom{6}{4}^2 = 960 - 225 = 715.$$ $\endgroup$ – gt6989b Feb 14 '18 at 21:45
3
$\begingroup$

Let $A$ be the set of bit strings with exactly two $1$-bit among the first $4$ bits, and $B$ be the set of bit strings with exactly two $1$-bit among the last $4$ bits.

\begin{align} \#A &= \binom{4}{2} 2^4 = 6\cdot2^4 \\ \#B &= 2^4 \binom{4}{2} = 6\cdot2^4 \\ \#A\cap B &= \binom{4}{2}^2 = 6^2 \\ \#A\cup B &= \#A + \#B - \# A \cap B \\ &= 6 (2^4 \cdot 2 - 6) \\ &= 6 \cdot 26 = 156 \end{align}

$\endgroup$
2
$\begingroup$

Among the first $4$ bits, choose $2$ to set them to one and the other two would be set to $0$ and there are $4$ of them with absolute freedom.

$$\binom{4}{2}\cdot 2^4$$

Similar when we focus on the last $4$ bits.

When we focus on intersection. We would pick $2$ from the first $4$ and pick $2$ from the last $4$.

So my overall answer would be

$$2\binom42 \cdot 2^4 - \binom42^2$$

Remark: I think your mistake is thinking that you can set arbitary $6$ bits to anything.

$\endgroup$
6
  • $\begingroup$ I see many of you get 156, but I just think on Inclusion–exclusion principle and the way I did it here was drawing the problem: i.stack.imgur.com/jYOXA.png $\endgroup$ – user530832 Feb 14 '18 at 16:38
  • 1
    $\begingroup$ The keyword is exactly $2$ ones in the first $4$ bits, which means exactly $2$ ones and exactly $2$ zeros in the first $4$ bits. $\endgroup$ – Siong Thye Goh Feb 14 '18 at 16:59
  • $\begingroup$ Update: I get 156 now. But to make sure I understand it, what if I change the problem to this: "How many bit strings of length 12 have either exactly four 1-bit among the first 6 bits or exactly four 1-bit among the last 6 bits?" Then I get the answer: 122655 is that correct? I did the same proces like the original question $\endgroup$ – user530832 Feb 14 '18 at 17:58
  • $\begingroup$ @M.Rasmussen: There are not even that many 12 bit strings period. There are only 4096 strings of length 12 so how could there possibly be 122655 of them that have some property? You need to get in the habit of checking your answers for reasonableness. $\endgroup$ – Eric Lippert Feb 14 '18 at 20:55
  • $\begingroup$ @M.Rasmussen would you like to show the working of how you obtain that number? $\endgroup$ – Siong Thye Goh Feb 14 '18 at 21:58
0
$\begingroup$

As a programmer (and a relatively naive mathematician) I immediately thought of reducing the 8-bit string to a hexadecimal string. Two digits, each made of four bits exactly as the problem is divided.

And, out 16 digits (0-F), 6 of them are valid (exactly 2 1-bits) digits.

So, we have 16×6 valid numbers (the first digit can be anything) and out of the the remaining 16×10 numbers, 6×10 of those will also be valid.

Now we have 16×6 + 6×10 = 156

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy