1
$\begingroup$

How many words at the length of n above {0,1} alphabet the amount of zeros is even.

I understand the answer is $2^{n-1}$. I'm trying to come up with a reasonable explanation for why that is.

If I could prove that the amount of even and uneven numbers is always the same, I could arrive to the conclusion that even numbers are $2^{n-1}$. Help?

$\endgroup$
  • $\begingroup$ n מעל {0,1} מספר האפסים הוא זוגי? נסו לפתור במספר דרכים שונות, אך הגישו לבדיקה רק דרך אחת שלטעמכם היא הפשוטה והבטוחה ביותר. What's this? $\endgroup$ – Gyanshu Jan 12 '17 at 17:17
  • $\begingroup$ @Gyanshu looks like the same question but in a different language? Could it be? $\endgroup$ – RGS Jan 12 '17 at 17:20
  • 1
    $\begingroup$ The Hebrew question asks for the simplest (P'shutah) way to prove this. $\endgroup$ – Mark Fischler Jan 12 '17 at 17:27
  • $\begingroup$ I think the induction/last digit argument is the simplest. Go us! $\endgroup$ – mdave16 Jan 12 '17 at 17:28
4
$\begingroup$

HINT: If you're given a word and you change the last letter, what happens to the number of zeros?


EDIT: This hint can give the answer without induction. Let $E_n$ be the number of words of length $n$ with an even number of $0$'s and $O_n$ the number of words of length $n$ with an odd number of $0$'s. Define $\phi:\{0,1\}^n \to \{0,1\}^n$ to flip the last letter of the word. Then $\phi^2 = \text{id}$ with $\phi(E_n) \subset O_n$ and $\phi(O_n) \subset E_n$. This immediately implies that $|E_n| = |O_n|$ Since there are $2^n$ total words, this implies $|E_n| = |O_n| = 2^{n-1}$.

$\endgroup$
3
$\begingroup$

A proof by induction could be done:

If $n=1, 2^n = 2^0 = 1$ and $1$ word of length $1$ has an even amount of $0$s, which is the word $1$.

Now imagine you have a sequence of length $k-1$. If it has an odd number of $0$s, then you can append a $0$ to the end of it. If it has an even number of $0$s, you can append a $1$ to it.

Assume then that it is true that, for words of length $k$, there are $2^{k-1}$ words with an even number of $0$s.

To those $2^{k-1}$ which have an even number of $0$s you add a $1$, making $2^{k-1}$ words of length $k+1$ that have an even amount of $0$s. To the other $2^{k-1}$ that have an odd number of $0$s, you add a $0$, making another $2^{k-1}$ words that have an even number of $0$s and length $k+1$. Therefore, you have a total of $2^{k-1} + 2^{k-1} = 2\cdot2^{k-1} = 2^k$ words, of length $k+1$, with an even number of $0$s, concluding your proof.

$\endgroup$
3
$\begingroup$

What you are considering are numbers $0000\dots0$ to $1111\dots1$ in binary. Indeed in total there are $2^n$ numbers.

Now, notice it is true for $n=1$. Assume it might be true for the number before your favourite natural number $k-1$.

Now, consider the possibilities for $k$. The last digit is either $0$ or $1$. So the total amount with even number when last is $0$, is all the $k-1$ length strings with odd amount, i.e. $2^{k-1}$. When last is $1$, we seek all the $k-1$ length strings with even amount, i.e. $2^{k-1}$.

Now, the total number would be $2^{k-1} + 2^{k-1} = 2^k$. So it's true for all the numbers you care about.

$\endgroup$
1
$\begingroup$

Two cases: If $n$ is odd, then any word of length $n$ containing an odd number of zeros is a word containing an even number of ones. So under the mapping that turns every one into a zero and every zero into a one, every word that contains an odd number of zeros corresponds to a word with an even number of zeros. That implies that half the words have an even number of zeros.

If $n$ is odd, then omit the last digit of the word. Note that half the words in that $n-1$ universe have an even number of zeros, and will pair with an last digit of zero to give an even number. And half the words in that $n-1$ universe have an odd number of zeros, and will pair with an last digit of oneto give an even number. So the fraction of words of length $n$ with an even number of zeros is $\frac12\cdot \frac12 + \frac12\cdot \frac12 = \frac12$.

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