3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Arthur Nov 15 '15 at 19:13
  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Nov 15 '15 at 19:14
  • $\begingroup$ @ThomasAndrews, source: Waterloo Euclid Conest 2014, cemc.uwaterloo.ca/contests/past_contests/2014/… $\endgroup$ – Amad27 Nov 15 '15 at 19:16
  • $\begingroup$ @Arthur, source: cemc.uwaterloo.ca/contests/past_contests/2014/… $\endgroup$ – Amad27 Nov 15 '15 at 19:16
  • 2
    $\begingroup$ (Am I supposed to read that whole text to find your question? Help people help you.) $\endgroup$ – Thomas Andrews Nov 15 '15 at 19:23
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ (+1) The separation seems really difficult, is there an easier approach? $\endgroup$ – Amad27 Nov 16 '15 at 13:07
  • $\begingroup$ 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? $\endgroup$ – Amad27 Nov 16 '15 at 13:13
  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews Nov 16 '15 at 13:20
  • $\begingroup$ Okay. So, how did you separate it into $\equiv 24 \pmod{80}$? $\endgroup$ – Amad27 Nov 16 '15 at 13:47
  • 1
    $\begingroup$ You keep using that word "separate." Not sure what you mean by that. $\endgroup$ – Thomas Andrews Nov 16 '15 at 14:40

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.