# How many 7-digit numbers are there whose digits have an even sum? [duplicate]

Possible Duplicate:
The total number of seven digit numbers,the sum of whose digits is even are?

How many $7$-digit numbers are there whose digits have an even sum?

-

## marked as duplicate by Ross Millikan, Stefan Hansen, Calvin Lin, Chris Eagle, Ittay WeissJan 29 '13 at 8:00

same as math.stackexchange.com/questions/34537/… this. –  jim Jan 29 '13 at 5:06

In the $1$ digit case, the sum of digits is the number, so there are $5-1=4$ (excluding $0$) such numbers.

In the $2$ digit case, either both digits must be even or both must be odd. There are $5 \times 5$ where both are even, $25$ where both are odd, but you must subtract the ones with leading zeros - these are $00,02,04,06,08$. So you have $50-5=45$ such numbers.

In the $3$ digit case, all three must be even, or two must be odd and one must be even. There are $5 \times 5 \times 5$ all evens, and $3 \choose 2$ $\times$ $5 \times 5 \times 5$ numbers with one even and 2 odd - think of the forms $112$, $121$, and $211$. Then subtract the ones with leading $0$'s ($000,,002 \ldots 098$), which there are $50$ in total. You get $4 \times 5^3 - 50$ such numbers.

Edit:

In the case of $4$ digits, you need to find all the ways to make the sum even as before. $0 + 0 + 0 + 0$ and $1 + 1 + 1 + 1$ work, as do any combination of two $0$ and two $1$. Thus you have $5^4 \times (1 + 1 + {4 \choose 2})$ such numbers, and as usual, you subtract $5 \times 10^4 = 500$ off to get a total of $4500$.

In the case of $n$ digits, with $n$ odd, you can have all evens ($0$'s), but you cannot have all $1$'s, so start with partioning $n$ choosing $2$ odd's and the rest even's. Then since you cannot have $3$ odds and the rest even, do $4$ odd and the rest even. You get something like:

$${n \choose 0} + {n \choose 2} + \ldots + {n \choose n - 1}$$

Similarly in the even case, you can have all $1$'s, but you still cannot have an odd number of $1$'s and the rest even. So:

$${n \choose 0} + {n \choose 2} + \ldots + {n \choose n}$$

The funny thing is that both of theses sums are equivalent, since if you plug $n=m+1$ into the odd case you get the even case, or in other words, $n \choose 0$ is equal to $n \choose n$.

Since $2^n$ is the sum of the binomial coefficients, $2^{n-1}$ is the sum of the binomial coefficients you are interested in. Thus you always have $2^{n-1} \times 5^n$ such numbers, including the ones with leading $0$'s, but you always need to get rid of the ones with the leading $0$, for which there are always $10^{n-2} \times 5$ of them. $2^{n-1} \times 5^n - 10^{n-2} \times 5 = 10^{n-1} \times 5 - 10^{n-2} \times 5 = 10^{n-2} \times 45$, for $n \gt 1$.

-

Call a number whose digit sum is even good. We need to take account of the fact that for example $037$ is (usually) not considered to be a $3$-digit number.

Look first at $2$-digit numbers. Such a number can start with any of $4$ even digits, and any of $5$ odd digits. An even start can be completed to a good $2$-digit number in $5$ ways (append any of the $5$ even digits). An odd start can be completed to a good number in $5$ ways. Thus there are $(4)(5)+(5)(5)=45$ good $2$-digit numbers. But there are $90$ $2$-digit numbers, so half are good and half are bad.

Now look at $3$-digit numbers. A good $2$-digit numbers can be completed to a good $3$-digit number in $5$ ways. A bad $2$-digit number can also be completed to a good $3$-digit number in $5$ ways, for a total of $450$ good $3$-digit numbers.

Similarly, there are $4500$ good $4$-digit numbers, and so on.

-

Hint: how many total $6$ digit numbers are there? Do you permit leading zeros? Then if you are given the first six digits, how many numbers are there that have an even sum of digits?

-

Choose the digits one at a time. There are 9 choices for the first digit (all possibilities but 0). Then we can choose all digits but the first and last in $10^{n-2}$ ways. Finally, the last digit can be chosen in $5$ ways, since half the choices will make the sum of the digits even, and the other half will make the sum odd.

So, for example, for $1000$ digit numbers, there are $45*10^{998}$ choices.

-

Suppose the sum of $x$'s digits is even, $x \in {0,\ldots,9999999}$. Then the sum of $x+1$'s digits is odd and vice-versa. Therefore, $$\frac{10^7}{2}$$

-
Don't forget the guys with leading $0$'s! –  tacos_tacos_tacos Jan 29 '13 at 5:48
Not true. For example 19 to 20 –  Carl Jan 29 '13 at 5:48
Even then it should work... because it works for the last digit. –  UnadulteratedImagination Jan 29 '13 at 8:52