Problem 2 Find the number of five-digit positive integers, $n$, that satisfy the following conditions: (a) the number $n$ is divisible by $5,$ (b) the first and last digits of $n$ are equal, and (c) the sum of the digits of $n$ is divisible by $5.$

Obviously, if $n$ satisfies divisiblity by five and takes the form,

$$n = abcda$$ then $a=5$, deductively,

$$n = 5bcd5$$ And:

$$10 + b + c + d \equiv 0 \pmod{5} \implies b + c + d \equiv -10 \equiv 0 \pmod{5}$$

What do I do next? HINTS are appreciated!


Big hint: Note that the digits $b$ and $c$ can be chosen freely, ($100$ choices total); and then, whatever the choices for $b$ and $c$, there are $2$ choices for $d$. For instance if $b$ and $c$ are chosen to be $7$ and $6$ respectively, then $d$ could be $2$ or $7$ to make $b+c+d$ congruent to $0 \pmod{5}$.


Well you need to find the number of solution to the following equations:

$$b + c + d = 0$$ $$b + c + d = 5$$ $$b + c + d = 10$$ $$b + c + d = 15$$ $$b + c + d = 20$$ $$b + c + d = 25$$

I would recommend you using generating funtions. So since $0\ge b,c,d \ge 9$, consider the following generating function:

$$(1 + x + x^2 + ... + x^9)^3 $$ $$=\left(\frac{1-x^{10}}{1-x}\right)^3 = \left(\binom{2}{0}x^0 + \binom{3}{1}x^1 + \binom{4}{2}x^2 +...\right)(1 - 3x^{10} + 3x^{20} -x^{30})$$

To find the number of solution to let's say $b+c+d=k$, check the coefficient in front of $x^k$.So for $k=0$, there's only one solution, for $k=5$, there are $\binom{7}{5} = 21$ solutions. But pleas be careful for the others equation. For example for $k=10$, there are:

$$\binom{12}{10} - 3\binom{2}{0} = 66-3 = 63 \text{ solutions}$$

For $k=25$, you'll have:

$$\binom{27}{25} - 3\binom{17}{15} + 3\binom{7}{5} = 351 - 3\cdot136 + 3\cdot21=6 \text{ solutions}$$

Now calculate for $k=10,15,20$ and add all the numbers and you have the final solution.


A) Any number divisible by 5 has to have either a 0 or a 5 at the units place. But condition 2 wants first and last to be same so 0 is eliminated.

B) Between $50005$ and $59995$ there are 9991 numbers.

C) here is where it gets interesting : The "maximum" sum a 5 digit number can achieve is 45.(5*9). Subtracting 10 because first and last are already known, you want 3 digit sum to be either 5,10,15 and 20. ( no more than that) and one special case for 25.

USE: Number of ways to reach a sum N using R elements is $\large\binom{N+R-1}{R-1}$

D) Reach 5 : $\binom{7}{2}$

Reach 10 : $\binom{12}{2}$

Reach 15: $\binom{17}{2}$

Reach 20: $\binom{22}{2}$

Now, special case for 25 : 9+9+7 = total 3 ways.

Do the math! and Add them up.

  • $\begingroup$ You're using the stars and bars method which is nice solution, but you need to exclude a lot of solutions. For example $\binom{22}{2}$ counts $(20,0,0)$ as a solution which clearly isn't since $b<10$. Also for the 25 case, isn't $(9,8,8)$ a solution? $\endgroup$ – Stefan4024 Mar 3 '15 at 14:07

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.