4
$\begingroup$

We have 6 digit numbers 000000 to 999999, and we need to find all of the possible combinations of these 6 digit numbers that sum to 27.

000999, 999000, etc all work. I understand this will involve build up counting, so we'll need to use $n \choose k$ for this problem. I've tinkered around with it and realized the sum of a string with the same value digit follows the following pattern:

999999… 54

888888… 48

777777… 42

666666… 36

555555… 30

444444… 24

So to get the sum to 27, we’d have to subtract 1 from some of the digits in the 555555 string 3 times, giving us some combination of 555444. If we do +/– some values on each digit, we can make the same combinations of 27. I just don't know how I can use $n \choose k$ on this pattern, where I use 555444 and its combinations +/- different values on each digit.

I also found this post here, which shows the use of the stars and bars strategy for solving a similar problem. However, I'm confused about how stars and bars applies in this case, or what the summation of the $n \choose k$ setup would look like

If someone can guide me in the right direction, I would greatly appreciate it. Thank you!

$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Using inclusion-exclusion with stars and bars to separate $27$ units into the required digits will give the answer.

The raw separation of $27$ units into $6$ parts is given by $\binom{27+5}{5}$. However some of these options will involve a part that is greater than $9$, so we can "preload" each digit in turn with $10$ (to break this constraint) and observe that there are $\binom{17+5}{5}$ ways to distribute the remaining units, which we can subtract off the above result. However this will still subtracted off the cases where two digits broke the constraint; now we can pre-load 2 digits in $\binom 62$ combinations with constraint-breaking $10$ units and find that $\binom{7+5}{5}$ combinations have to be added back in (that were double-subtracted).

Giving $\binom{32}{5} - \binom 61 \binom{22}{5} + \binom 62 \binom{12}{5}$ as the total possibilities.

$\endgroup$
3
  • $\begingroup$ I think we would have to add the condition that the first digit should be strictly bigger than 0, else we wouldn't really call it a 6 digit number. $\endgroup$ Commented Oct 29, 2017 at 23:05
  • 2
    $\begingroup$ @ThomasBladt The question explicitly allows such strings. Probably the simplest way to extend this answer to cover your proposed case would be to do it all again with only 5 digits. $\endgroup$ Commented Oct 29, 2017 at 23:15
  • 1
    $\begingroup$ Just FYI: this question is the "famous" solution of the lucky ticket problem: prove that the number of lucky tickets (55,252) is the same as the number of tickets whose six digits sum to 27. $\endgroup$ Commented Jul 10, 2021 at 21:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.