# AIME 2013 Solutions (divisiblity)

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.

• 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? – Stefan4024 Mar 3 '15 at 14:07