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...

$\endgroup$
3
  • 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, 2016 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, 2016 at 17:17
  • $\begingroup$ Precisely half of them. $\endgroup$
    – shawnt00
    Mar 7, 2016 at 17:21

5 Answers 5

Reset to default
82
$\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$.

$\endgroup$
5
  • 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, 2016 at 1:28
  • 4
    $\begingroup$ Ah, the eighth bit is just a checksum digit. $\endgroup$
    – Jeppe Stig Nielsen
    Mar 7, 2016 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, 2016 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, 2016 at 3:37
  • $\begingroup$ @Oddthinking: Yes, for absolute completeness one should add that every word with an even number of $0$'s arises in this way. $\endgroup$
    – André Nicolas
    Mar 8, 2016 at 3:45
17
$\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.

$\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.

$\endgroup$
2
  • 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, 2016 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, 2016 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$$

$\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$$

$\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.