5
$\begingroup$

This question poses a seemingly very simple method to solve problems of the sort "how many $x$ digit numbers are there with sum of digits $y$?", but I don't understand it. Why are the "bad" solutions in correspondence to the solutions of $y_1 + 10 + x_2 + x_3 + x_4 + x_5 = 23$? What's the idea?

For instance, what "correct solution" corresponds to taking $y_1=13$? How to solve this problem?

$\endgroup$
  • $\begingroup$ See here $\endgroup$ – Moya Sep 11 '16 at 14:12
  • $\begingroup$ @igael I don't understand why we make the substitution $y_1=x_1-10$ and not, say $x_1-14$.. the latter would also ensure a "digit"... $\endgroup$ – combinarcotics Sep 11 '16 at 14:12
  • $\begingroup$ @Moya that still doesn't explain why we take the $-10$ substitution... Why not just take $-6$ in that quesion? Why is the $10$ there? $\endgroup$ – combinarcotics Sep 11 '16 at 14:14
  • $\begingroup$ @igael I hope somebody will explain.. $\endgroup$ – combinarcotics Sep 11 '16 at 14:22
  • $\begingroup$ @Moya: yes, it is the basis of the good answer. Perhaps it wasn't well applied in the 1st question. $\endgroup$ – user354674 Sep 11 '16 at 14:31
-2
$\begingroup$

I'm also not great at combinatorics, but I'll give this a shot to give you a start. This isn't going to be an answer, but an extended comment.

First, we need to establish the number of nonnegative numbers satisfying \begin{equation}\sum_{i=1}^5 x_i=23\end{equation} (call this (*)). This is a standard stars and bars type problem, where we have $23+(5-1)=27$ stars and $5-1=4$ bars. But we've overcounted, because some of these solutions will have some of the numbers being greater than or equal to 10, which should not be allowed because we wants a 5 digit number. For this, we can use the inclusion-exclusion principle (we want the second quoted equation).

Let $A$ be the set of solutions to (*) where none of the integers is greater than or equal to 10, $B$ the set of solutions where 1 integer is greater than or equal to 10, and $C$ where two of the integers are greater than or equal to 10. After this, we're done, because at most 2 of the $x_i$ in the solutions we counted can be greater or equal to $10$. Then \begin{align} |A\cup B\cup C|= |A| + |B| + |C| - |B\cap C|\end{align} (I excluded the parts of the sum that were empty). We want to know $|A|$, we know $|A\cup B \cup C|$, so we need to compute $|B|,|C|,|B\cap C|$. How one would compute $|B|,|C|$ is given, more or less, in the answer I quoted in the comments.

How one would compute $|B\cap C|$, I'm not sure off the top of my head. We also need to exclude the solutions where $x_1=0$. In the quoted method, the number is small enough to count by hand. For this case we would need a more robust method.

Edit: See also here for ideas. I'm out the door, but best of luck to you!

Edit 2: Back, and I messed up a little in haste. $B\cap C$ is obviously equal to the number of solutions where exactly 2 numbers are $\geq 10$. So we can just take $|A\cup B\cup C|=|A|+|B|+|C|$, where $A$ is as before, $B$ is the number of solutions with exactly one number $\geq 10$, and $|C|$ the number of solutions with exactly two numbers $\geq 10$. Then we'll need to refine by excluding the case where $x_1=0$, this can be done with the trick $x_1'=x_1-1$, though some care will need to be taken.

$\endgroup$
1
$\begingroup$

The referred question asks for the number of non-negative integer solutions of \begin{align*} x_1+x_2+x_3+x_4+x_5=23 \end{align*} with only one additional restriction $0\leq x_1\leq 9$. In this case we do not need the inclusion-exclusion principle.

In order to determine all integer solutions with \begin{align*} x_1+x_2+x_3+x_4+x_5=23\qquad\qquad0\leq x_1\leq 9,0\leq x_2,x_3,x_4,x_5\tag{1} \end{align*}

we look at all integer solutions of

\begin{align*} x_1+x_2+x_3+x_4+x_5=23\qquad\qquad\qquad\qquad 0\leq x_1,x_2,x_3,x_4,x_5\tag{2} \end{align*}

and subtract all solutions of

\begin{align*} x_1+x_2+x_3+x_4+x_5=23\qquad\qquad\qquad x_1\geq 10, 0\leq x_2,x_3,x_4,x_5\tag{3} \end{align*}

The solutions of (3) are the so-called bad solutions in the referred question, meaning the invalid solutions which are to subtract when determining the solutions of (2).

In order to calculate (2) with the nice range $x_1,x_2,x_3,x_4,x_5\geq 0$ we can use the stars-and-bars technique and obtain \begin{align*} \binom{23+4}{4}=\binom{27}{4}=17550 \end{align*}

In order to calculate (3) we transform the range by a proper substitution which enables us to apply the stars-and-bars technique again. Instead of $x_1\geq 10$, we substitute $x_1=y_1+10$ and the range $x_1\geq 10$ can then be transformed to $y_1+10\geq 10$ or equivalently $y_1\geq 0$.

This way we obtain from (3)

\begin{align*} x_1+x_2+x_3+x_4+x_5&=23\qquad\qquad\qquad x_1\geq 10, 0\leq x_2,x_3,x_4,x_5\\ (y_1+10)+x_2+x_3+x_4+x_5&=23\qquad\qquad\qquad 0\leq y_1,x_2,x_3,x_4,x_5\\ y_1+x_2+x_3+x_4+x_5&=13 \end{align*}

We are now in the same situation as in (2) and can apply the stars-and-bars technique again.

\begin{align*} \binom{13+4}{4}=\binom{17}{4}=2380 \end{align*}

$$ $$

We finally obtain the number of wanted solutions as the total number of solutions of (2) minus the number of solutions of (3) \begin{align*} \binom{27}{4}-\binom{17}{4}=17550-2380=15170 \end{align*}

$\endgroup$
  • $\begingroup$ +1. Nice job. The complication comes from the subtraction. Something likes $00599$ is not allowed. $\endgroup$ – Felix Marin Sep 14 '16 at 21:19
  • $\begingroup$ @FelixMarin: Many thanks, Felix! Btw. $00599$ is a valid string as well as $0000\color{blue}{23}$. Subtraction avoids counting e.g $\color{blue}{10}0580$. $\endgroup$ – Markus Scheuer Sep 15 '16 at 7:32
0
$\begingroup$

If $x_1 + x_2 + x_2 + x_3 + x_ + x_5 = 23$ and one or more of the $x_i$ has more than one digit. Than one or more terms is at least $10$. We can replace the $x_i$s with $x'_i$s where one of the $x'_i = x_i -10 \ge >0$ and the rest of the $x'_j = x_j$. Then $10+ x'_1 + x'_2 + .... + x'_5 = 23$.

So if we eliminate all of those solutions we have eliminated all the solutions in which at least one $x_i$ was double digit.

So we are only left with solutions in which all terms are single digit.

We did not eliminate any extraneous solutions because if $x_1 + ... x_5 = 23$ and all $x_i$ are single digit and $10 + x'_1 +.... + x'_5 = 23$, it is not possible for $x'_j = x_j$ for all but one term; that would make the $x'_i = x_i -10 < 0$.

====

Argh. WRONG!!

By eliminating solutions to $10 + .... = 23$ we will elimate an answer with two multidigit terms twice.

E.G. $10 + 11 + 0 + 1 + 1$ will be eliminated by eliminating $10 + ( 0+ 11 + 0 + 1 + 1)$ and by eliminating $10 + (10 + 1 + 0 + 1 + 1)$ as well.

To avoid double counting we must re add thus with two multidigits.

So the solution should be:

# solut to $x_1 + x_2 + ... + x_5 = 23$ - # solutions to $10 + x_1 + ..+x_5 = 23$ + # solutions to $10 + x_1+.... + x_5 = 23$

Which could be very complicated for sums greater than 30. Best to come up with another method altogether.

$\endgroup$

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.