Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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. 
Please help me and my granddaughter.
 
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/