[There's a wonderful discussion in the comments regarding the challenge problem at the bottom of this post. Read tc's and mathmom's astute explanations that generalize to the combinatorial problem of placing k indistinguishable objects into n containers.]
Just a quiet acknowledgment to my readers, an expression of gratitude for helping a math blogger who was unknown before 1-2-07 to reach the 25,000th visit on October 7th. Thank you...
And for our middle schoolers and on up, here's a simple A.P. (that's arithmetic progression, not advanced placement!) problem that is designed to help students see the variety of problem-solving techniques one can employ before they reach for the calculator or plug into a formula.
Could a 6th or 7th grade student or group find a way to determine the 25,000th positive odd integer? How would the instructor guide the process?
Well, let's see...
1st.....2nd.....3rd.....4th.....5th.....
1.......3.......5.......7.......9.......
If students have tackled similar problems and are accustomed to making and analyzing tables, looking for patterns, making conjectures (forming hypotheses) and testing their ideas, perhaps some would arrive at the result. They may even surprise you with their ingenuity!
I'll share my favorite approach but don't expect students to think the same way:
Position...1st...2nd...3rd...4th...5th...25,000th...nth
Even.......2.....4.....6.....8.....10....50,000.....???
Odd........1.....3.....5.....7......9....?????......???
Now, what is the formula for the nth positive even integer? the nth positive odd integer?
Today's problem may not be sophisticated but the issue of pedagogy is never trivial, is it?
Oh, ok, I know my readers want more of a challenge to sink their teeth into. So, I'm adding the following:
The answer to the above problem is 49,999. The sum of the digits of this 5-digit positive integer is 40. Determine the number of 5-digit positive integers with this property. This combinatorial problem should keep you busy for at least a few nanoseconds!
Monday, October 8, 2007
The 25,000th Positive Odd Integer to Celebrate!
Subscribe to:
Post Comments (Atom)
Posts
16 comments:
Congratulations, Dave. I would like to stress that it is the content of this blog that brings the visits.
If you have statistics on the number of unique visitors, that would give some insight into how obsessed your visitors really are :-)
TC
tc--
I certainly don't have 25000 unique visitors, nor do I believe I have 5 visitors, 5000 times each! My 'free' stat counters give me a sense of unique visitors for a limited duration, although, even there the accuracy is somewhat dubious.
Also, I am fully aware there are bloggers who have more than TEN times my total count, so I have no false illusions of my fame!! I'm just very grateful to the tc's and mathmom's of the world who bring so much more to my posts. You are truly enriching the experience and you're dead on when you say it's all about the content. Quality always will win out...
My blog is generally focused on pedagogy and developing conceptual understanding so I don't expect it to compete with some others. My journalistic bent of late is something however that is a bit different and it's something I've come to enjoy. Let me know if this is of any interest to you or my other readers. I do think that Alec Klein has something important to say about gifted education and that it should generate interesting discussion.
By the way, no one has responded to my challenge problem at the bottom of the page...
As with most combinatorial problems, this one is easy once you know how to do it.
The answer is 9C5.
In my meanderings, however, I was also able to derive a 2-D generating function N(x,y), for N(k,M), where k is the number of digits and M is the desired sum. I get
N(x,y) = (y-1)/(x.y^10 + y - x -1)
Of course, this did not help me any in solving the problem.
TC
The correct result is 126 numbers which is 9C5 as tc pointed out. There are several ways to do this but, tc, can you illuminate us as to why 9C5 works! I get the idea that we need to remove a total of 5 from the digits of 99,999. I did this by partitioning 5 and counting using combinatorial methods, but I'm not sure why 9C5 accomplishes that in one step. Where is the 9 coming from? I guess I'm missing the obvious here??
Think of it as five bins having 9 identical balls each, and you need to remove five balls from this to get the number of values. This is the same number as arranging five identical balls in five bins. Arranging n identical balls in k bins is a well-known problem (is actually the basis of Bose-Einstein statistics) and the answer is (n+k-1)!/n!(k-1)!. One way to derive this is to have k-1 bars between the balls, and the number of arrangements is the number of positions in which you can have the bars.
It is certainly not obvious. I have to rederive the expression many times to convince myself of it.
Cheers,
TC.
I guess the previous post was my Eric Jablow impression :-)
TC
This kept me busy for more than a few nanoseconds, and I finally ended up looking up the formula for choosing items with replacement where order doesn't matter. This was because I wanted to choose one of the five digit positions to subtract one from, five times. With replacement because I can subtract from a given digit more than once. And order doesn't matter because we don't care which order we did the subtractions in at the end. But I couldn't come up with a derivation for this on my own. 5^5 overcounts, but not by an factor that I could figure out to divide by, because when you have replacements, not all of the combinations have the same number of permutations (that is, 11111 has only 1 permutation, but 11112 has 5, and so on). So I looked it up and found a decent explanation here
The formula for choosing k items from n, with replacement, unordered is (n+k-1)Ck (which works out to 9C5 for this problem).
The basic idea is that we could set up a string of five zeros and five ones, with each zero representing a digit position, and the number of 1's immediately preceding it would represent the number to subtract out of that digit position. Since a 1 after the last zero doesn't make sense, the last digit has to be zero. So there are 9 places for the ones to go, and we have to choose 5 of them.
Dave, I'd like it if you went into a little more detail about your approach as well. I'm not "seeing" it immediately from your description.
mathmom and tc--
Sorry for not replying sooner...
My argument was much less elegant than the 9C5 approach but let me give you my take on your ideas. It's an elusive concept and one I frequently forget. I'm taking what each of you explained and reworking it for my brain:
We're trying to place 5 identical objects into 5 containers (bins). This can be simulated with bars (separators) like tc mentioned or zeros as in mathmom's approach. However, my brain actually saw this better with checkers which come in 2 colors, RED (R) and BLACK (B). We have a total of NINE checkers, 5 RED checkers (to place into the 5 bins) and 4 BLACK checkers to denote the spaces between the containers. Examples are much better here than words:
(1) RBRBRBRBR symbolizes placing one checker in each bin or the 5-digit number 88888. Each B denotes a separation between bins.
(2) BRRBBRRBR: Skip bin #1, place 2 objects in bin #2, skip bin #3, place 2 objects in bin #4 and 1 in bin #5.
(3) RRRBRRBBB: Place 3 objects in bin #1, 2 in bin #2, skip bins 3,4, and 5.
I guarantee that if I don't think about this type of problem for awhile, I will forget the details of this method again! Anyway, that's how my mind was able to make sense of your explanations. And, yes, I see now how the general formula for placing k identical objects into n containers works!
Now for the elementary approach using cases (perhaps easier for students the first time around, since the idea of solving a sum of digits problem by using a model of removing 5 objects from 5 bins, each of which contain 9 objects, requires some adjustment!).
(A)Remove 5 from 1 bin: 5C1 = 5 ways;
(B) Remove 4 from 1 bin and 1 from another bin: (5C1)(4C1) = 20;
(C)Remove 3 from 1 bin, 2 from another: (5C1)(4C1) = 20;
(D) 3,1,1 (symbolism ok?)
(5C1)(4C2) = 30 (this is not totally obvious);
(E) 2,2,1: (5C2)(3C1) = 30;
(F) 2,1,1,1: (5C1)(4C3) = 20;
(F)1,1,1,1,1: 5C5 = 1
for a total of 126 ways. I know this is a bit more tedious than 9C5, but, for students, this may be an instructive initial approach (and the details are not trivial). I chose this method even though I knew there was some other bin-separator approach because my brain could not easily reconstruct the latter! That's why I depend on the two of you!! Now, using formulas for binomial coefficients, PROVE the sum of all my cases is mathematically equivalent to 9C5. Just kidding!
The same concept can be applied to another problem I encountered in one of my classes eons ago:
How many 7-digit numbers have non-decreasing digits?
TC
Now I know what tc really stands for:
TOO CLEVER!!
But you didn't throw me this time. 9C7 would be the number of strictly 'ascending' 7-digit numbers, therefore, 9^9 - 9C7 would give the number of 'non-decreasing ones'.
I absolutely love these kinds of combinatorial problems, since, as we know, the really tough problems that require the most logic and reasoning are not in the calculus textbook! That's why most math educators remember with horror the probability part of that prob/stat class they had to take...
oops--
That's 9^7 - 9C7 (looks better too!).
Also, I should have stated that 9C7 is the number of strictly 'descending' numbers (not ascending) and that excludes the 'descending' numbers that have zeros (which we can ignore). Other than these 'few' mistakes, I think it's ok until I recognize a new batch of errors I've made!
Hi Dave.
It looks like my problem statement was not too clear, or you are pulling my leg.
A 7-digit number with strictly ascending digits would be something like 1356789. One with non-decreasing digits would be something like 1112344. 112342 is not permissible number.
As you point out, the number of 7-digit numbers with increasing digits is 9C7 (it cannot start with zero!). 9^7 - 9C7 gives the number of 7-digit numbers whose digits are not strictly increasing, but I do not believe it gives the number whose digits are non-decreasing.
Calculating the number of 7-digit numbers with non-decreasing digits is a combinatorial problem similar to what we have been discussing. Think bins and identical balls.
TC
tc, I think I need to go back to sleep now!
Ok, I'll pretend to have a brain:
Let's try 15C7. The 15 comes from 7+9-1. We are choosing 7 digits from 9 bins. The first bin contains seven 1's, the 2nd bin contains seven 2's, etc. For example, suppose we consider the nondecreasing 7-digit number 1137899. This corresponds to the 15-character sequence:
1 1 B B 3 B B B B 7 B 8 B 9 9 where the B's represent blanks or separators or colors like in my earlier solution. Did I mess it up again? Be kind to sleep-deprived humans...
Bingo!
Adding my two cents regarding Dave's comment, "I absolutely love these kinds of combinatorial problems, since, as we know, the really tough problems that require the most logic and reasoning..."
We just started our new topic of probability in math team yesterday. A couple of kids wanted a formula that works with every problem. They didn't like my response of think.
I'm enjoying following the conversation - but I liked the summer more when I had time to actually try the problems.
Hey Dave, don't feel badly. You totally had me convinced. "Complementary counting -- great approach!" It didn't occur to me that the sets were not really complementary either. ;-)
I've learned the trick with separators before, but it hasn't stuck. Maybe this time. :)
I agree 100% with the comments about how these are great problems for making people think. (And, you can't make a calculator do the hard work for you, at least not until you get the the point of knowing you have to compute 15C7, the computation of which is really the easy part, even without a calculator.)
Post a Comment