7
$\begingroup$

How many numbers have a units digit that equals the digit sum of previous digits?

  • No negative number solutions.
  • No more than 3 digits
  • Digit sum of all digits except the units digit must equal the units digit

Feel free to solve without these specific restrictions

Examples of a solution:

  • 11, 22, 33...
  • 101, 202, 303...
  • 112, 224, 336...
  • 123, 246
  • 0

(347 is a solution because 3+4=7)

How many total numbers exist? And what are some requirements for solutions other than this rule?

I'm in high school and I thought of this problem and wasn't sure what field of math it would fall into but I think its an interesting challenge.

Edits:

  • @JMoravitz came up with a number of 55 solutions with 3 digits, but I was wondering if there could be a general summation for a variable number of digits.
  • @aqualubix found general expression for the number of solutions with n digits.
$\endgroup$
10
  • 1
    $\begingroup$ It's a finite problem...Just write it out for all possible unit place digits. $\endgroup$
    – lulu
    Commented May 28 at 14:15
  • 6
    $\begingroup$ If we ignore the "no more than 3 digits"... You include $101$ as an example. There is also $1001, 10001, 100001, 1000001,\dots$ so if you allow this type of example there are infinitely many. It is far more interesting if we exclude zero at which point there can only be a finite number since the largest digit possible is $9$, all such examples must be less than or equal to $1111111119$ $\endgroup$
    – JMoravitz
    Commented May 28 at 14:15
  • $\begingroup$ Yes, definitely, although I was looking for a way to find solutions other than just writing them out. By limiting either the digits to a finite amount or excluding 0 as a possible digit, the problem becomes finite. $\endgroup$ Commented May 28 at 14:19
  • $\begingroup$ As for how many numbers exist satisfying all of your conditions, we can break into cases based on final digit and number of digits. There is the number zero, there are the two-digit numbers which have to be both the same nonzero digit, and then there are the three digit numbers. Those three-digit numbers ending in $n$ will have their first digit as some number from $1$ to $n$ and the second digit equal to $n$ minus whatever the first digit was, so there are $n$ options for each. We get a total then of $1+9+(1+2+3+\dots+9)=55$ in all $\endgroup$
    – JMoravitz
    Commented May 28 at 14:20
  • 1
    $\begingroup$ With regards to "wasn't sure what field of math it would fall into", this falls under the umbrella of "enumerative combinatorics" $\endgroup$
    – JMoravitz
    Commented May 28 at 14:25

2 Answers 2

4
$\begingroup$

If we exclude $0$ and remove the limit on the number of digits appearing we can find a nice stars and bars approach to get the number. If the final digit is $9$ we start with $1111111119$. There are eight potential spaces for bars between the $1$s and after choosing which to receive bars you sum up the $1$s between them, so $11|111|11119$ would give us $2349$. As there are eight spaces there are $2^8=256$ numbers ending in $9$. Similarly, if the last digit is $n$ there are $2^{n-1}$ numbers, so the total number is $\sum_{i=1}^9 2^{i-1}=2^9-1=511$. This is the same approach suggested by lulu's comment.

$\endgroup$
3
  • $\begingroup$ exclude 0 and remove the limit on number of digits appearing. $\endgroup$
    – JMoravitz
    Commented May 28 at 14:27
  • 1
    $\begingroup$ Keep this answer but I was thinking about limiting the number of digits instead of excluding 0 to keep the problem finite. $\endgroup$ Commented May 28 at 14:28
  • $\begingroup$ @JMoravitz: good point. I have edited it in. Thanks $\endgroup$ Commented May 28 at 14:29
3
$\begingroup$

The only single digit number that works is $0.$

Let $n\in\mathbb{N}\setminus\{1\}.$ We wish to find the number of $n$ digit numbers such that, when written in their decimal expansion, the sum of all digits but the units digit equals the unit digit.

Suppose the units digit is $k,$ where $k\in\{1,2,\ldots,9\}.$ We want to avoid $k=0,$ since that just gives us $0.$ Now, we wish to find the number of solutions to $a_1+a_2+\ldots+a_{n-1}=k,$ where $a_1$ is a natural number and $a_2,a_3,\ldots,a_{n-1}$ are whole numbers. The number of such solutions is ${{k+n-3}\choose{n-2}},$ and I will justify this in the bottom of my answer. The total number of such $n$ digit numbers, then, is: $$\sum_{k=1}^9{{k+n-3}\choose{n-2}}={{n+7}\choose{n-1}}.$$

This equality follows from the hockey stick identity. Conveniently, this formula also holds when $n=1.$

Coming back to the equation $a_1+a_2+\ldots+a_{n-1}=k,$ we may subtract $1$ from both sides and write this equation as $(a_1-1)+a_2+\ldots+a_{n-1}=k-1.$ Note that now $a_1-1$ is a whole number. Similarly, from a solution to $t_1+t_2+\ldots+t_{n-1}=k-1,$ where each $t_i$ is a whole number, we get a solution to $a_1+a_2+\ldots+a_{n-1}=k,$ where $a_1$ is a natural number and $a_2,a_3,\ldots,a_{n-1}$ are whole numbers. This establishes a bijective correspondence. Hence, we may just count the number of whole number solutions to $t_1+t_2+\ldots+t_{n-1}=k-1.$

The formula for this is well-known. It's equal to ${{k+n-3}\choose{n-2}}.$

$\endgroup$
3
  • $\begingroup$ I think I follow! However, I have yet to see summation written like that, did you mean n+k-3 over n-2 or more likely something else? I found an example like yours on the wikipedia page for summation, as you said it is well-known. $\endgroup$ Commented May 28 at 14:55
  • 1
    $\begingroup$ @ElijahNelson, that is notation for the binomial coefficient. You may be more familiar with $C(n+k-3,n-2).$ In general, ${n}\choose{r}$ is the number of ways to choose $r$ things out $n$ things, where $n$ and $r$ are whole numbers, and order doesn't matter. $\endgroup$
    – aqualubix
    Commented May 28 at 14:59
  • $\begingroup$ I was about to edit my comment to say I found what it was for. Yes, I'm more familiar with nCr for combinations. I was also about to ask about writing it in Desmos but I know they have a built-in nCr function instead. I'll get back. $\endgroup$ Commented May 28 at 15:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .