Associated Topics || Dr. Math Home || Search Dr. Math

Enumeration in Combinatorial Analysis

Date: 11/28/96 at 00:36:03
From: Bill L. Mauer
Subject: Digital Sums

My eleven-year-old granddaughter has the following question from her
math homework: How many 3 digit numbers have the digital sum of nine?

I can sit down and write all the numbers from 100 to 999 and count the
ones that have a digital sum of 9.  I know, however, that there has to
be a formula but I have no idea what it is.  I've always considered
myself to be fairly up on math, but this simple question stumped me.

Thank You!

Bill L. Mauer
billmaue@interl.net

Date: 11/28/96 at 04:15:06
From: Doctor Pete
Subject: Re: Digital Sums

Hi,

I think this is a pretty tough question for an 11 year-old, but it's
very interesting because it demonstrates counting techniques
(combinatorial counting, or enumeration, not "1, 2, 3,..." counting).

Think of picking digits one at a time, the hundreds digit first (let's
call that digit "h"), followed by the tens ("t"), and finally, the
ones ("u").  Notice that if you pick the hundreds and tens, there can
be at most one unique ones digit that will give a digit sum of 9.  For
example, if I'd picked h = 2, t = 4, then u must be 3, so that
h+t+u = 2+4+3 = 9, and 100h + 10t + u = 243.  However, if I'd picked
h = 7, t = 4, then no value of u will allow h+t+u = 9.  So we must
distinguish between these two cases.

The way to do this is to note that we can pick h to be between one and
nine, inclusive (which means h can be any of the whole numbers between
one and nine, including one and nine).  But then our allowed values
for t will depend on what we have picked for h; in particular, t must
be between 0 and 9-h, inclusive (if h = 9, then t = 0).  Since these
restrictions guarantee that we can pick exactly one u, we can make a
table of h versus the number of ways to choose t:

h:   1   2   3   4   5   6   7   8   9
# of ways to choose t:   9   8   7   6   5   4   3   2   1
(# of ways to choose u
for each choice of t:   1   1   1   1   1   1   1   1   1)

Therefore, if we sum over all these possibilities, there are
9+8+7+6+5+4+3+2+1 = 45 3-digit numbers whose digit sum is 9.

You'll notice that you can easily generalize this for larger numbers,
or for numbers with a different digit sum.  It's perhaps not the most
elegant way of solving the problem, but it's a great example of how
enumeration works in combinatorial analysis.  Your granddaughter's
teacher may have expected her to do this problem the brute force way
by writing down all the numbers between 100 and 999 and perhaps
noticing a pattern, but this way should save some time.  I hope this
helps!

-Doctor Pete,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/

Associated Topics:
High School Permutations and Combinations
High School Puzzles
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search