2) find sum of numbers from 1000 to 10000 with distinct digits

Hi CalcBeginner,

I can address problem 2. Am I to understand that you're not allowed to use computer software for this one either? Because writing a brute force program should be pretty trivial, you just need a doesHaveDistinctDigits() function, and a simple for() loop.

But for a more paper-and-pencil approach, consider that we are looking at simple permutations, except that the first digit has to be treated in a special manner because it cannot be zero.

Before we begin, I'll tell you that the following is a complete solution, so if you want to solve it more on your own (which might increase your opportunity to learn), then you should try to anticipate my next steps, and possibly try stopping part-way through to see if you can complete the rest of the steps on your own.

So, consider 9 cases, which will basically reduce to just one case since they're so similar.

case: first digit is 1:

Numbers of the form 1XYZ, where X, Y, and Z can be any distinct integers from 0 to 9 inclusive other than 1.

It should be evident (I won't offer a proof) that for the permutations of {X, Y, Z}, each digit will appear the same number of times in each position.

So we have 3! ways to arrange them, and each one will appear in each slot 3!/3 times.

So for a particular {X, Y, Z}, we'll have (3!)(1)(10^3) + (3!/3)[(10^2)(X+Y+Z) + (10^1)(X+Y+Z) + (10^0)(X+Y+Z)] = 6000 + (222)(X+Y+Z).

Then we need to work out how many ways to get {X, Y, Z}. There are C(9, 3) ways, where C(n, k) is binomial coefficient "n choose k." Consider that if we fix X, there are C(8, 2) ways to pick {Y, Z}. That means that each digit appears in exactly C(8, 2) of the C(9, 3) combinations. So we have

\(\displaystyle \sum_{i=1}^{C(9, 3)}\big(6000+(222)(X_i+Y_i+Z_i)\big)\)

\(\displaystyle = (6000)\binom{9}{3}+(222)\bigg(\sum_{i=1}^{C(9, 3)}X_i+\sum_{i=1}^{C(9, 3)}Y_i+\sum_{i=1}^{C(9, 3)}Z_i\bigg)\)

\(\displaystyle = (6000)\binom{9}{3}+(222)\binom{8}{2}(0+2+3+4+5+6+7+8+9)\)

\(\displaystyle = (\color{red}1\color{black})(6000)\binom{9}{3}+(222)\binom{8}{2}(T(9)-\color{red}1\color{black})\)

where \(\displaystyle T(n) = \frac{n(n+1)}{2}\) is the nth triangle number, and marked in red are those things specific to choosing the digit 1 in the thousands digit place for this case.

Then simply do cases 2-9 and sum them. It looks like this, in case you had any doubt

\(\displaystyle \sum_{i=1}^9\bigg( (i)(6000)\binom{9}{3}+(222)\binom{8}{2}(T(9)-i) \bigg)\)

I have confirmed this works using a brute force algorithm.