# How many numbers have unit digit $1$?

Let $f(n)$ be the number of positive integers that have exactly $n$ digits and whose digits have a sum of $5$. Determine, with proof, how many of the $2014$ integers $f(1), f(2), . . . , f(2014)$ have a units digit of $1.$

HINTS ONLY

EDIT:

for $f(2)$ we have: $x + y = 5$ with $x \ne 0$, which gives: $\binom{5}{1}$

$f(5)$ gives: $x + y + z + t +w = 5$ so: $\binom{8}{4}$

$f(4)$ gives, $\binom{7}{3}$

For $f(n)$ we have: $f(n) = \binom{n + 3}{n-1}$

$f(n) = \frac{(n+3)(n+2)(n+1)(n)(n-1)!}{24(n-1)!} = \frac{(n+3)(n+2)(n+1)(n)}{24}$

PROOF CHECK:

Consider $N = \overline{a_1 a_2 ... a_n}$ with $a_i$ as digits such that $a_1 \ge 1$. We have a string of $n$ characters, $a_1, a_2, a_3, ..., a_n$ with $a_1 \ne 0$, thus this string with $a_n$ gives the $n$th digit numbers. the number of numbers corresponds to the solutions of: $a_1 + a_2 + ... + a_n = 5$ for nonnegative integers with $a_1 > 0$. By the stars-and-bars principle there exist: $\binom{n + 4 - 1}{n-1} = \binom{n+3}{n-1} = \frac{(n+3)(n+2)(n+1)(n)}{24}$ numbers, thus giving an explicit formula for $f(n)$.

Is this enough for a proof? Or is induction needed for a stronger argument?

So we have: $f(n) \equiv 1\pmod{10}$.

Since $f(n)$ is a combinatoric coefficient, $f(n) \in \mathbb{Z+}$, which implies that: $\frac{(n+3)(n+2)(n+1)(n)}{24} \equiv (n+3)(n+2)(n+1)(n) \pmod{10}$. Since the numerator was divisible by the denominator for all $n$.

Now help is needed:

How to solve this modular arithemetic expression?

• Does $491$ have a digit sum $5$ or $14$? The problem does say "whose digits have sum $5$", which I would interpret as $491$ giving $14$. – Arthur Nov 15 '15 at 19:13
• Do you mean with repeated digit sum $5$? Because $950\equiv 5\pmod 9$ but $9+5+0\neq 5$. "Digit sum" to me means $9+5+0$. – Thomas Andrews Nov 15 '15 at 19:14
• @ThomasAndrews, source: Waterloo Euclid Conest 2014, cemc.uwaterloo.ca/contests/past_contests/2014/… – Amad27 Nov 15 '15 at 19:16
• @Arthur, source: cemc.uwaterloo.ca/contests/past_contests/2014/… – Amad27 Nov 15 '15 at 19:16
• (Am I supposed to read that whole text to find your question? Help people help you.) – Thomas Andrews Nov 15 '15 at 19:23

If you want to solve $$\frac{n(n+1)(n+2)(n+3)}{24}\equiv 1\pmod{10},$$

You can multiple both sides by $3$, since it is relatively prime to $10$, but when you multiply by $8$, you have to apply that to the modulus, to. So, you are trying to solve:

$$n(n+1)(n+2)(n+3)\equiv 24\pmod{80}$$

Solve this in pairs, using Chinese remainder theorem:

$$n(n+1)(n+2)(n+3)\equiv 24\pmod{5}$$ $$n(n+1)(n+2)(n+3)\equiv 24\pmod{16}$$

As it turns out, the second only depends on $n\pmod 8$.

• (+1) The separation seems really difficult, is there an easier approach? – Amad27 Nov 16 '15 at 13:07
• If we have $a/b \equiv 1 \pmod{10}$ then could it follow that $a \equiv b \pmod{10}$? If yes then, $n(n+1)(n+2)(n+3) \equiv 24 \pmod{10} \equiv 4 \pmod{10}$. Then, $n = 10k + 4$ or $n = 10k + 3, n = 10k + 2, n = 10k + 1$. The ones gives: $\{201.4, 201.1, 201.2, 201.3 \}$ as the numbers for the number of $k$ values. Then check: $k=0$: works. Thus, from $k=0 \to 201$ gives: $201 - 0 + 1 = 202$ values of $k$, thus $202$ values of $n$? Is this justified? – Amad27 Nov 16 '15 at 13:13
• But the reverse is not true - if $b$ divides $a$ and $a\equiv b\pmod{10}$ it is not necessarily true that $a/b\equiv 1\pmod{10}$. Take, for example, $a=15,b=5$ or $a=12,b=2$. Solving $n(n+1)(n+2)(n+3)\equiv 24\pmod{10}$ will give you false answers. For example, $n=6$ is a root of the $\equiv 24\pmod{10}$ equation, but not the original. – Thomas Andrews Nov 16 '15 at 13:20
• Okay. So, how did you separate it into $\equiv 24 \pmod{80}$? – Amad27 Nov 16 '15 at 13:47
• You keep using that word "separate." Not sure what you mean by that. – Thomas Andrews Nov 16 '15 at 14:40