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 email@example.com
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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.