The following question(s) are appropriate for grades 5-12. How is this possible? Well, the mathematics needed to solve it is elementary! Of course, as with most math problems of this sort, the meaning/interpretation of the question is the challenge for most. Then there is the issue of going beyond the question to look for deeper mathematical meaning...
To help the younger student get started, we will begin with an example and then proceed with the question. Older students might need the same since the language of the question may be vague or difficult to comprehend:
The number 6 can be written as a sum of one or more odd positive integers in exactly 4 ways:
5+1, 3+3, 3+1+1+1, and 1+1+1+1+1+1. As you can see, we are not considering the order of the summands.
Also, 6 can be written as a sum of one or more different positive integers in exactly 4 ways:
6, 5+1, 4+2, 3+2+1. Again, different orders are not included in our list.
Anything of interest yet? Should students naturally raise their hands and ask questions about these two problems or do we have to cue them? At this point, the educator has many options. Here are a couple:
Pair of Problems:
List all ways to write 9 as a sum of one or more odd positive integers. How many ways?
List all ways to write 9 as a sum of one or more different positive integers. How many ways?
What do you notice?
---------------------------------------------------------------------------------------------------------------
Investigation (in groups):
Make a table for positive integers from 1 through 10 as follows (I'm abbreviating the column headings). Also, include extra columns for the number of ways for each.
N..........N as a Sum of Odds...............N as a Sum of Different
1.........................1.......................................................1
2.......................1+1....................................................2
3.......
.
.
.
.
10
Comments:
(1) Can you think of at least 3 benefits from having students doing these?
(2) If class time does not permit further investigation, is it worth assigning these for homework, enrichment, extra credit, etc?
(3) Anyone imagine there might be some highly sophisticated ideas from number theory behind these simple questions? Anyone know who posed these kinds of questions originally and solved the general question?
Tuesday, December 25, 2007
Elementary Arithmetic for the New Year? A Partition Problem for Middle Schoolers or for SATs
Subscribe to:
Post Comments (Atom)
Posts
15 comments:
What level of student would you first start teaching generating functions?
If you're thinking of the mathematician who proved the equivalence between the two classes, my daughter's math teacher this year once gave detention to a student who pronounced the mathematician's name wrong!!
I always wondered if he was from Edmonton, CA!!
Happy Holidays, tc and Eric!
Eric--
I believe advanced algebra students could appreciate this topic. I seriously considered doing an investigation using generating functions for partitions. Now you're making me want to go further.
TC--
You're ruining my surprise for the week's mystery mathematician!
I didn't know there was an Edmonton in California, TC.
Dave, if you want to write a more limited set of lectures on generating functions, you could work with generating functions for probability distributions. You can go from there to probability distributions for the dice rolled in games like backgammon, Monopoly[tm], or (showing my age) D&D.
Let X be a random variable taking only finitely many integer values. Then its probability generating function or pgf is defined as the polynomial p(x) where the coefficient p_k is thr probability that X = k. For a fair die, the pgf is
p(x) = (1/6) · [x + x^2 + x^3 + x^4 + x^5 + x^6] = (1/6) ·(x-x^6)/(1-x).
Now, the sum of two probability distributions with pgfs p and q has pgf pq. So, the pgf for the sum of two fair dice is
(1/36) · (x-x^7)^2/(1-x)^2.
Now, to find the coefficient of a particular power of x, don't divide! Take the power series of 1/(1-x)^2 and multiply. 1/(1-x)^2 = 1 + 2x + 3x^2 + 4x^3 + ... So, to find he probability for rolling 10 on 2 fair dice, you want the coefficient of x^10 in that expression above. That is the coefficient of x^10 in
(1/36) ·(x^2 - 2x^8 +x^14) [1 + 2x + 3x^2+...]
The terms in the product with x^10 are (1/36)·x^2·9x^8 and (1/36)·(-2x^8)·(3x^2). These add to (3/36)x^10, and the probability is 3/36 = 1/12.
For two dice, it's easy to do this without infinite series, but for 3 or more dice it becomes tedious. You can even come up with a general formula if you use binomial coefficients for the power series. This can, however, motivate the relevant formula for unequal/odd partitions:
X's theorem:
Π_n (1+x^n) = &Pi_{n odd) 1/(1-x^n).
Oops. x-x^7, not x-x^6 in the first formula.
Eric--
Excellent development as always, although this would prove challenging for students without more background.
Actually, I was hoping to have students create an algorithm for pairing each 'distinct' partition with a unique 'odd' partition. Easy to create a procedure, very difficult I think to make it one-to-one! If this were easily done, many others would have described such a method long ago! Of course there is an easy way to demonstrate visually the well-known result that the number of partitions of N with a largest addend M is the same as the number of partitions of N into M addends. I was hoping to modify that approach for 'distinct' and 'odd' but it's not transparent.
The classic Hardy & Wright textbook on Theory of Numbers develops generating functions for partitions fairly thoroughly so I may refer to that also. Certainly we can start by developing binomial coefficients using the standard binomial expansion, however, calculus (series expansions) is required before going much further with it. I need to think some more...
Dave,
Not every partition equality has a simple derivation by 1-1 correspondences. You may be looking for something that's simply impossible. Look at the January 2008 issue of the Notices of the American Mathematical Society, on line at http://www.ams.org for an article on Ramanujan to see how complicated it can get.
Eric--
I'm not surprised! If they could reproduce the other argument (M addends vs. largest addend M), that would be more than sufficient for a reasonable investigation. I think it's instructive for students to understand that 'elementary' problems often lead to very difficult solutions or even an unsolved situation!
Neil Sloane's On-line Encyclopedia of Integer Sequences discusses the odd partition sequences in its entry A000009, and gives a fascinating list of equalities, including a fairly direct way to get the odd≡distinct relation. Note that if you look at that page, you will be spoiled for next week's "Name that Mathematician" contest.
Take a partition of n into odd parts. Suppose 3 appears 7 times. Write 7 in binary, and develop it as a sum of powers of two: 7 = 1 + 2 + 4. Then, replace the original 7 threes: 3+3+3+3+3+3+3 by 3·1 + 3·2 + 3·4. The numbers you get for a general odd partition will be distinct. Reversing this is easy too: given a partition of n into distinct parts, replace any even number a·2^k, a odd, with 2^k as.
Notice that this is not the partition dual you were using in your result on partitioning into ≤ m parts, discovered by J. J. Sylvester. But another partition scheme comes from that:
The number of partitions of n into distinct parts equals the number of partitions of n such that, if k is the largest part, all the integers from 1 to k-1 also appear. Sent to Sloane by Jon Perry.
Eric--
Thank you for that reference. The binary approach is elegant. I was working on a similar idea but I couldn't get it to be unique. The uniqueness of the binary representation does it beautifully -- darn, why didn't I think of that! Now, to develop all of this for 6th graders...
The binary technique leads to a pretty mechanical proof of the product identity.
Every nonnegative integer has a unique partition into 1s. Every nonnegative integer has a unique partition into distinct powers of 2. This leads to
1/(1-x) = 1+x+x^2+x^3+... = (1+x) (1+x^2) (1+x^4)...
Now, first replace x by x^3, then by x^5, then by x^7, and so on. Multiply all those equalities together.
Hi Dave and happy New Year to you!
Nobody has addressed the questions you posted at the end of your article. I'll have a go at the first 2:
>>(1) Can you think of at least 3 benefits from having students doing these?
(a) Any chance for students to play with (and use, manipulate and think about) numbers without calculators is a good thing. (I am very pro-technology, but only for students who have a half-decent grounding in number, then algebra.)
(b) Group discussion leading to collaborative learning is a clear benefit in your design.
(c) Perhaps "students [would] naturally raise their hands and ask questions about these two problems" if they were within a framework of a (reasonably believable) practical problem? (Nothing brilliant comes to mind, but something like numbered beads being put into bowls, or similar.) Using a concrete approach would make the lesson more memorable.
>>(2) If class time does not permit further investigation, is it worth assigning these for homework, enrichment, extra credit, etc?
I am a fan of 'extra credit' especially for topics which are not directly part of curriculum - but what is the politics of this at your institution...?
Eric--
Thanks for the explanation of the product identity.
Zac--
Nice to hear from you. How is life in Singapore these days? I still find it surprising how many views my Singapore math posts receive on a daily basis, including the post based on your input.
I appreciate your responding to my issues of pedagogy. I think such questions are a 'turnoff' for some of my readers who perhaps think I'm being too didactic, but, I believe the issue of finding a variety of ways to effectively implement these kinds of activities in the classroom is important and not at all transparent.
Since I am now retired I can only comment on what was, not is, the politics! Extra credit was always an option in classes -- no student, parent or administrator would ever object to that unless one teacher's grades were significantly inflated as a result of overusing this technique.
Although the problem of partitions was not couched in real-world terms or made concrete using manipulatives, I often used such problems in middle and secondary classrooms. The apparent simplicity and elementary nature of the questions were inviting and I used other techniques to spice it up, such as occasionally making it competitive among groups or for extra credit points as you suggested. Also, the mathematics itself was engaging, particularly if they saw how excited I was about it! Invariably one or two students would comment on the fact that the 'results' were the same for both the odd & distinct partitions and, when seeing this, most students when polled, would indicate that this was probably not a coincidence. After all, they knew I wouldn't ask some random question like this!
Hi Dave
Life in Singapore is great, thanks. December is the coolest month due to the North-East monsson, so it is quite pleasant.
I have to admit I was a little concerned to read...
"I think such questions are a 'turnoff' for some of my readers who perhaps think I'm being too didactic"
Say what? Are we doing all this for our own benefit or the learning benefit of our students...?
A key thing you sadi was the students will be more excited "particularly if they saw how excited I was about it!".
All the best for 2008.
Zac --
A great 2008 to you also!
You're right about my unsettling comment, except for the fact that, even if some readers do feel that way, I will never stop asking the questions! And, yes, you picked up on my belief re the key to teaching -- passion for your subject...
Post a Comment