15
$\begingroup$

I believe I'm overthinking this or otherwise confused but I believe that the method to solve this would be $2^n$ where n is the length of the bytes? So in this particular case it would be $2^8$ equal 256 possible.

But then I feel like that isn't right and I'm mixed up. What I thought about is that there is 4 possible ways to have an even number f zeros (i.e. 2 zeros, 4 zeros, 6 zeros, or 8 zeros).

Any insight would be awesome as I'm confused...

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ A couple things: $2^8 = 256$, not $64$. And also, your latter approach is sound but you need to consider the case when $0$ zeros appear (since 0 is an even number as well). $\endgroup$ – Xoque55 Mar 6 '16 at 17:10
  • $\begingroup$ Ah yes a dumb mistake on my part. I ended up going with that approach and noting the $C(8,0)$ as well which would come as 1 and added the values to show there are 128 possibilities. Thanks. $\endgroup$ – Jacob Johnson Mar 6 '16 at 17:17
  • $\begingroup$ Precisely half of them. $\endgroup$ – shawnt00 Mar 7 '16 at 17:21
83
$\begingroup$

Any $7$-bit word can be completed to an $8$-bit word with an even number of $0$'s in exactly one way by choosing the eighth bit suitably. So the number of $8$-bit words with an even number of $0$'s is the same as the number of $7$-bit words. This is $2^7$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Excellent! I wish I had thought of that. $\endgroup$ – S.C.B. Mar 6 '16 at 22:39
  • 5
    $\begingroup$ I read the question and immediately knew it was half of them but not why. Well here's why. $\endgroup$ – Joshua Mar 7 '16 at 1:28
  • 3
    $\begingroup$ Ah, the eighth bit is just a checksum digit. $\endgroup$ – Jeppe Stig Nielsen Mar 7 '16 at 18:30
  • $\begingroup$ Each even bit pattern can be paired one to one with an odd pattern by flipping (wlog) the final bit. $\endgroup$ – shawnt00 Mar 7 '16 at 21:40
  • $\begingroup$ I agree with the conclusion, but I think there is a hole in the proof. You show that every 7-bit word has a unique corresponding 8-bit word with an even number of zeros. That only shows that the number of 8-bit words with an even number of zeros is >= the number of 7-bit words. You need to show that every 8-bit word with an even number of zeros has a unique corresponding 7-bit word as well. $\endgroup$ – Oddthinking Mar 8 '16 at 3:37
16
$\begingroup$

HINT

Divide the cases for the number of zeros, namely $0,2,4,6,8$, which gives us $$\binom{8}{0}+\binom{8}{2}+\binom{8}{4}+\binom{8}{6}+\binom{8}{8}=\frac{2^8}{2}$$ From the Binomial Theorem.

You could also use recurrence relations to solve this problem.

|cite|improve this answer
$\endgroup$
8
$\begingroup$

There are $2^8 = 256$ different bit-strings of ones and zeros. Because of symmetry$^{(*)}$ the number of strings with an odd number of zeros must be the same as the number of strings with an even number of zeros. Specifically, half of all the possible cases have an even number of zeros, so we have have $\frac{1}{2}2^8 = 2^7$ such bit-strings.

$(*)$ The symmetry I am thinking of here is the symmetry between an even and odd count of zeros. Because we are considering all bit-strings of length eight, if we are asking how many of them have an even/odd number of zeros, there is no reason to favor even or odd over the other, so there must be the same number of each.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ I think it would help to specify which particular symmetry you were thinking of. For example reversing the order of the bits left-to-right is "symmetrical", but doesn't help in answering the OP's question. When I read your post I my immediate thought was "yeah, take a number and replace all 0's by 1's and vice versa" - but that doesn't prove it either, because the number of 0's and 1's are either both odd, or both even! $\endgroup$ – alephzero Mar 7 '16 at 3:57
  • $\begingroup$ @alephzero: Try "toggle the lowest bit" (or the high bit, or whatever other bit you like). By inspection, that's an involution that toggles partiy, so it must be a bijection. $\endgroup$ – Kevin Mar 8 '16 at 6:43
3
$\begingroup$

To find the number of ways to arrange the word

Moose, we take $\frac{5!}{2!1!1!1!}=\frac{5!}{2!}$ since we have $5$ letters in moose and only one repeated letter.

Here we are looking at the case where there are no zeroes, $2$ zeroes, $4$ zeroes, $6$ zeroes and $8$ zeroes in a 'word' of length $8$, with an alphabet consisting of $0$ and $1$.

$$\frac{8!}{8!}+\frac{8!}{6!2!}+\frac{8!}{4!4!}+\frac{8!}{2!6!}+\frac{8!}{8!}=128$$

|cite|improve this answer
$\endgroup$
3
$\begingroup$

Here's another way. The number of bytes with $n$ zeroes is the coefficient of $x^n$ in $$(1+x)^8$$ Now for any polynomial $p(x)$, the sum of the coefficients of even degree is $\frac{p(1)+p(-1)}{2}$. Hence the answer is:

$$\frac{(1+1)^8+(1-1)^8}{2} =2^7$$

|cite|improve this answer
$\endgroup$

Your Answer

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

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