Counting TechniquesDate: 12/28/97 at 10:09:37 From: Kate Subject: Counting Techniques Problem: Find the number of positive divisors of 17640, inclusive of 1 and 17640 itself. I have no idea how to do this. Please help me. Thanks. Date: 01/03/98 at 09:01:58 From: Doctor Mitteldorf Subject: Re: Counting Techniques Hello, Kate - Sounds to me like you're taking a course in fundamentals of statistics. Counting techniques are useful in building up your experience and your arsenal of techniques to apply in statistics problems. Take 17640 and look for numbers that can divide it. Well, it's certainly divisible by 2. So go ahead and divide it by 2, and find 8820. That's still divisible by 2. How many times can you divide it by 2? Keep track as you keep dividing it. When you're done, you may notice other numbers that divide it. Since it ends in a zero, it looks like it's divisible by 5, for example. Eventually, you will have decomposed 17640 into prime numbers. You will have an expression that looks something like 17640 = 2*2*2*2*3*3*5*5*5*7*7*7 This isn't the right number of 2's and 3's and 5's and 7's - you can work that out for yourself. Now you have a decomposition of your number into prime factors, how does that help you count the number of divisors? Well, let's consider a recipe for a divisor: You can make a divisor by multiplying prime factors together. You can take any combination you want, and it will still be a divisor. I won't do 17640 for you, but I'll do 504. 504 consists of 3 two's, two 3's, and a 7. (504=2*2*2 * 3*3 * 7) Then your recipe would be this: - Take any number of 2's, 0,1,2 or 3. - Take any number of 3's, 0 1 or 2. - Either take the lone 7 or leave it. You can make a divisor for 504 in any combination of ways. The first line above gives you 4 possibilities, the second line 3, and the third line 2 possibilities. So there are 4*3*2 possibilities, that's 24 possible divisors. (Have we counted 1? Have we counted 2? Have we counted 504 itself?) Please write back with some of your own thinking on the next problem. And do let me know what you got when you finished this example for 17640. -Doctor Mitteldorf, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 01/04/98 at 03:06:53 From: Kate Subject: Re: Counting Techniques Prime factorization of 17640: 2*2*2*3*3*5*7*7 = 17640 2s = 4 possibilities 3s = 3 possibilities 5s = 2 possibilities 7s = 3 possibilities 4*3*2*7 = 72 divisors! Date: 01/04/98 at 06:13:21 From: Doctor Mitteldorf Subject: Re: Counting Techniques Good work! What do you think about 1 and 17640? Are they included in your 72? -Doctor Mitteldorf, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 12/29/97 at 02:03:10 From: Kate Subject: Counting Find the no. of odd integers between 2000 and 7000 which do not have repeated digits. Date: 12/29/97 at 14:58:09 From: Doctor Mitteldorf Subject: Re: Counting Dear Kate, I'm going to interpret "no repeated digits" to mean that no two consecutive digits can be repeated; in other words, 2101 counts, but 2113 doesn't. Let's see: The first digit can be 2, 3, 4, 5 or 6 - that's 5 possibilities. The last digit can be 1, 3, 5, 7, or 9 - that's 5 possibilities. And the middle digits can be 0..9, for 10 possibilities each. Multiplying all these together there are 5*10*10*5 = 2500 odd numbers between 2000 and 7000. Let's count the ones that have the first two digits the same: there are 250 of these, starting with 22xx for 50, 33xx for 50, etc. How many have the second and third digits the same? also 250, this time 5*10*5. And 250 more have the last two digits the same. So we have 750 exceptions, and we're down to 1750. But we've double-counted some of the exceptions. We double-counted all the ones that are 222x and 333x and 444x and 555x and 666x, since we excluded them once for having the first two digits the same and once for having the 2d and 3d digits the same. So that's 25 we double- counted that have to be added back. Similarly, there are 25 more of the form x111, x333, x555, x777 and x999 that have to be added back. And 25 more of the form xxyy, where the first two digits match and the last two digits match. So we add back 75 and we're back up to 1825. One more correction: in our double-count correction, we've also done some double-counting - triple counting, actually. We have added back 3333 three times, once because it was a 333x number and once because it was an x333 number and once because it was an xxyy number. Same story with 5555. So we need to correct the add-backs by taking away two extra times 3333 was counted and two of the extra times 5555 was counted. That's a total of 4 add-backs to remove, bringing us down to 1821. This reasoning gets us to 1821, and I hope it illustrates for you one way to think about this kind of question. But 1821 is not the right answer - I've written a computer program to count explicitly, and that comes out to 1823, which I'm convinced IS the right answer. So somewhere in my reasoning, I believe that I missed by 2. I'm going to leave this for you to figure out (please tell me if you do!) or for another Doctor Math to give us a hand. -Doctor Mitteldorf, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 12/29/97 at 18:07:30 From: Doctor Mitteldorf Subject: Re: Counting Hi, Kate - Here's an addendum to my other answer. I was concerned about the difference between 1821 and 1823. The discrepancy has do to with those two numbers 3333 and 5555. When they were excluded, they were excluded 3 times each - once because they were 33xx, once because they were x33x, and once because they were xx33. Then when they were added back, they were added back three times. We need to just re-exclude them once each to make the computation whole; that is, subtract 2 from 1825 to get 1823. This is the right answer. -Doctor Mitteldorf, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 01/01/98 at 03:34:10 From: Kate Subject: Re: Counting Dr. Math, My teacher says that "no repeated digits" means none of the digits is used twice, wherever they may be located in the number. That means 2010 does not count either. How may I solve the problem with this constraint? Kate Date: 01/01/98 at 07:05:05 From: Doctor Mitteldorf Subject: Re: Counting Dear Kate, Why don't you try working this out, applying the method I described before. It's a little simpler with your teacher's definition of "repeated digit." Start with 5 possibilities for the first digit (2,3,4,5,6), 10 for the second and third digits and 5 for the fourth (1,3,5,7,9). Once you've chosen the first digit, there are 9 possibilities for the second that don't duplicate; then there are 8 possibilities for the third that don't duplicate either of the other two, so we have 5*9*8 possibilities going into the fourth digit... but then things get complicated, because there are only 5 possibilities to begin with for the 4th digit, and whether we're constrained further depends on what we used in the first three. So we could go back and do things in a different order: The first digit, then the fourth, then the other two. There are two numbers overlapping between the list of possibilities for the first and fourth digits. If there were no overlapping numbers, then we'd have 5*5 = 25 possibilities for the first and fourth together; if all 5 overlapped, we'd have 5*4 = 20 possibilities that don't repeat. As it is, we have 5 possibilities for the fourth digit if the first is chosen as 2, 4, or 6 and 4 possibilities for the fourth if the first is chosen as 3 or 5. So for allowed combinations of first and fourth, we have 3*5 + 2*4 = 23. In any case, we have 8 remaining possibilities for the second digit and 7 remaining for the third, so the total I get is 23*8*7 = 1288. A computer count gives the same. -Doctor Mitteldorf, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/