3
$\begingroup$

Find the sum of all 5 digit numbers that can be formed using $0,0,1,1,2,3$.

I think this problem requires a lot of cases.The problem caused is due to the repetition of digits $0,1$ else it would have been a standard problem.Also we have to subtract the cases when $0$ comes in the ten thousands place.

Of course , a lot of brute force may yield the answer the question is how do i efficiently tackle the problem.

Background:This problem is "Pathfinder for Olympiads".This exercise comes just after an example involving calculating the sum of all 5 digit numbers using digits $0,1,2,3,4$.

Related Post Find the sum of all 4 digit numbers which are formed by the digits 1,2,5,6?

$\endgroup$
2
3
$\begingroup$

Maybe a simpler solution. Forget about starting zero and consider all digits equally. You have six digits, pick one and denote it with $d_i$. That digit could be first, second, ...., fifth. We have 5 remaining digits and we have to pick 4 from the set to complete the number. We can do that in $5\cdot4\cdot3\cdot2$ different ways. As you shift the digit $d_i$ from the first to the fifth place, the chosen digit contributes to the total sum with the following value:

$$d_i\cdot5\cdot4\cdot3\cdot2\cdot(10^4+10^3+10^2+10^1+10^0)$$

If you take all available digits, the total sum is:

$$(d_1+...+d_6)\cdot5\cdot4\cdot3\cdot2\cdot(10^4+10^3+10^2+10^1+10^0)=$$

$$(0+0+1+1+2+3)\cdot120\cdot11111=9333240$$

We have to avoid overcounting becuase we have two ones and two zeroes. A pair of ones doubles the total sum, and also a pair of zeroes. So if we elliminate duplicate ones and zeroes, the total sum is:

$$\frac{9333240}{2!\cdot2!}=2333310$$

The last step: we have to elliminate all numbers starting with zero. It's like asking about the total sum of 4-digit numbers made of 0,1,1,2,3 (one zero has been elliminated). If we apply the same logic, the total sum of all numbers starting with zero is:

$$\frac{(0+1+1+2+3)\cdot4\cdot3\cdot2\cdot(10^3+10^2+10^1+10^0)}{2!}=93324$$

So the final result is $2333310-93324=2239986$

$\endgroup$
1
  • $\begingroup$ your answer is really logical, thanks $\endgroup$ Oct 26 '20 at 16:46
2
$\begingroup$

There is a trick to this problem which is that there are just as many six digit numbers as there are five digit numbers. There is also an easy one-to-one mapping from one to the other. For each five digit number tack on the last number from the set of six numbers at the end (On the right side). This means that if we add all of the six digit numbers together without carrying over. We can then remove the last digit to get the sum of five digit numbers. An example of what I mean by adding numbers without carrying over is 123+456+789=(1+4+7)(2+5+8)(3+6+9)=(12)(15)(18). This would be 1368 with carry. What I'm going to do later is remove the last digit of the sum without carry over. If I do this operation in the example it would just be (12)(15). It is alot easier to add all six digit numbers than all five digit numbers.

If the left leading digit is a $1$ then there are $5!$ ways of arranging the other five digits, however $0_a0_b$ is the same $0_b0_a$ so the combinations are cut in half. This gives $\frac{5!}{2}$ $(60)$ numbers. The numbers where the zeros are in the same place can be grouped so that the other three digits can be summed. [123],[132],[213], [231],[312], and [321]. This sum is $12$ for each digit. There are a total of $\binom52$ $(10)$ groups. In six of the ten groups any one of the five digits is non-zero. $6×12=72$. So the sum of all numbers where the leading digit is a $1$ is $(60)(72)(72)(72)(72)(72)$. Now to get the sum of all five digit numbers with a leading $1$. I remove the last digit to get $(60)(72)(72)(72)(72)$. After all of the carry over the final result is $679992$.

If the leading left digit is a $2$ or a $3$ then again there are $5!$ ways of arranging the other five digits, but $0_a0_b1_a1_b$, $0_b0_a1_a1_b$, $0_a0_b1_b1_a$, and $0_b0_a1_b1_a$ are all the same. So there are two sets of $\frac{5!}{4}$ (30) combinations.

If the left leading digit is a $2$ the numbers that have zeros in the same place can be grouped so that the digits can be summed. [113], [131], and [311]. The sum is $5$ for each digit. There are a total of $\binom52$ $(10)$ groups. In six of the ten groups any one of the five digits is non-zero. $6×5=30$. So the sum of all numbers where the leading digit is a $2$ is $(60)(30)(30)(30)(30)(30)$. Now to get the sum of all five digit numbers with a leading $2$. I remove the last digit to get $(60)(30)(30)(30)(30)$. After all of the carry over the final result is $633330$.

If the left leading digit is a $3$ the numbers that have zeros in the same place can be grouped so that the digits can be summed. [112], [121], and [211]. The sum is $4$ for each digit. There are a total of $\binom52$ $(10)$ groups. In six of the ten groups any one of the five digits is non-zero. $6×4=24$. So the sum of all numbers where the leading digit is a $3$ is $(90)(24)(24)(24)(24)(24)$. Now to get the sum of all five digit numbers with a leading $3$. I remove the last digit to get $(90)(24)(24)(24)(24)$. After all of the carry over the final result is $926664$.

Finally we add $679992+633330+926664=2239986$

Special thanks to @Saulspatz for pointing me in the right direction.

$\endgroup$
4
  • $\begingroup$ Excellent, I had the same solution, but you were faster. +1 $\endgroup$
    – Oldboy
    Oct 24 '20 at 17:50
  • $\begingroup$ Are you making $5$-digit numbers or $6$-digit numbers? The question asks for $5$-digit numbers. $\endgroup$
    – saulspatz
    Oct 24 '20 at 18:53
  • $\begingroup$ @saulspatz Yes you're right I made a mistake I did six digit numbers instead of five but found out a relatively quick fix $\endgroup$
    – quantus14
    Oct 24 '20 at 19:06
  • $\begingroup$ Please check my solution :) $\endgroup$
    – Oldboy
    Oct 24 '20 at 19:37

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.