Update as of 6-2-07: All solutions to the problem below are now posted in the Comments section. Also, read Eric Jablow's astute comments and his challenge to students!
The following problem is well-known, however it is an excellent exercise for middle schoolers and as a challenge for older students as well.
Target Audience: Grades: 6-12
Prerequisite skills: Basic understanding of fractions and simple operations
Develops: Logical thinking, Systematic Counting/Listing, Fraction Concepts, Structure of Mathematical Proof
Recommended Classroom Organization for this activity: Students working in groups up to 4.
Online Resource: Here's one of the best sites on Egyptian Fractions I have found on the web. The problem is discussed but not solved!
Introduction for student:
A unit fraction is defined as 1/n, where n is a positive integer greater than 1.
The number 1 can be written as a sum of 3 unit fractions in 3 ways:
1 = 1/2 + 1/3 + 1/6
1 = 1/2 + 1/4 + 1/4
1 = 1/3 + 1/3 + 1/3
No other ways (other than rearrangement) can be found using the following reasoning:
The largest of the 3 fractions could not be less than 1/3. Why?
If 1/3 is the largest fraction, then the larger of the remaining fractions could not be less than 1/3. Why?
Here's your challenge:
There are 14 ways to write 1 as a sum of four unit fractions of the form:
1 = 1/a + 1/b + 1/c + 1/d, where a ≤ b ≤ c ≤ d.
Make a list of all of these ways. Have fun! Uh, no calculators please!
Wednesday, May 30, 2007
Unit Fractions - Pyramid Power?
Subscribe to:
Post Comments (Atom)
Posts
5 comments:
Here are some nice discussion seeds taken from MathWorld:
Each fraction x/y with y odd can be expressed as a sum of t unit fractions with odd denominator, where t is O(√log y).
You can discuss the O-notation after that.
Erdos and Straus conjectured that
4/n = 1/a + 1/b + 1/c
can be solved for every n>4, so this is probably true. ☺
Nice, Eric! I read that discussion on MathWorld but suggested a site a bit more user-friendly for middle-school students. The discussion there of the Greedy Algorithm and the proof is suitable for students in grades 7-12. Of course, I can hear the quiet desperate sobs of teachers in these grades bemoaning the lack of fraction skills and understanding! But that's another post!!
One of my calc students is including big-O notation as part of her end of year project, so I'll share your 2nd paragraph with her.
You're right -- Erdos' conjecture lacks only a proof! I believe that conjecture has been verified up to a very large value of n, but, of course, not for all n, yet.
Here are seven solutions, listed 'systematically', although you may disagree:
1. 1/2 + 1/3 + 1/7 + 1/42
2. 1/2 + 1/3 + 1/8 + 1/24
3. 1/2 + 1/3 + 1/9 + 1/18
4. 1/2 + 1/3 + 1/10 + 1/15
5. 1/2 + 1/3 + 1/12 + 1/12
6. 1/2 + 1/4 + 1/5 + 1/20
7. [2,4,6,12]
I'll let you guess what this notation means!
Ok, 7 more - watch out there are a couple that are easy to overlook.
Note: Pls correct any errors you may find!
If anyone tries this problem out, let me know how you organized it in the room and how long it took an individual or group to solve it. What was the student reaction?
Here's another demonstration of greediness not always being efficient.
Suppose you want to raise a number to a power, but you want to do so efficiently, using the least number of operations. Multiplication is a relatively expensive computer operation, you know.
x^2 = x · x. 1 operation, cheap.
x^3 = x^2 · x. 2 operations, pretty cheap.
x^4 = x^3 · x. 3 operations, not so cheap.
But, x^4 = x^2 · x^2. 2 operations, best.
Similarly, x^8 can be done in 3 operations,
x^16 in 4 operations, and so on.
Usually, you can break up an exponential into powers like x^(2^n) and get it done cheaply:
x^20 = x^4 ·x^16. It takes 4 multiplications to get x^16, in the middle of which you computed x^4. So, x^20 takes 5 multiplications.
However, there are exponentials where another scheme is faster.
x^27 = x·x^2·x^8·x^16.
It takes 4 multiplications to get x^16, which also gives you x^8 and x^4. So, this scheme for x^27 requires 7 multiplications.
Ask your students to find a way to compute x^27 using only 6 multiplications.
And about the conjecture, it was by Erdos! So it has to be true.
[Remaining solutions to the unit fraction problem appear below my response to Eric...]
Eric--
Your analysis of efficient algorithms for powers was fascinating. From my background in computer science (limited though it may be), I could appreciate the importance of reducing the number of operations and developing different schemes.
I'm sure I messed up your challenge but here's what I got:
x^9 = x^8 ⋅ x
Therefore, x^9 requires 3+1 = 4 multiplications. Then
x^27 = x^9 ⋅ x^9 ⋅ x^9 ⋅ would require 4+1+1 = 6.
Even if I'm wrong, I enjoyed this! I think many students would figure it out once they caught on to the concept of what you're doing. Definitely requires some creative thinking which is not my strength!
Now for the rest of the Egyptian Fraction solution:
[Remember, pls correct errors if you find them. I didn't copy this from a book!]
Recall that the notation I'm using below is an abbreviation for the sum of the reciprocals:
8. [2,4,8,8]
9. [2,5,5,10]
10. [2,6,6,6]
11. [3,3,4,12]
12. [3,3,6,6]
13. [3,4,4,6]
14. [4,4,4,4]
That's right. I'd prefer this alternative:
You can get from x to x^3 with two multiplications. So, you can get from x^3 to (x^3)^3 = x^9 with 2 more multiplications. And then you can get from x^9 to (x^9)^3 = x^27 with 2 more multiplications, for a total of 6.
You'll find a number of conjectures about 'addition chains' in the literature, and some sequences about them in Sloane's encyclopedia. I just looked at the Wikipedia article on addition chain exponentiation. It points out that the smallest exponent where powers-of-two are not the most efficient method is 15:
x^15 = x·x^2·x^4·x^8.
x^8 takes 3 multiplications (which compute x^2 and x^4 on the way), and thee are 3 more multiplications for a total of 6. But,
x^15 = x^3·((x^3)^2)^2.
x^3 takes 2 multiplications. Each square takes a multiplication, and there's 1 more for a total of 5.
I wouldn't say creative thinking is not your strength. On the other hand, even the most brilliant mathematician would have great problems doing this in general. Finding the most efficient scheme for an exponent is an NP-hard problem. Furthermore, the optimal schemes assume that memory is not a limited resource. A variant of the power-of-2 method requires very little scratch space:
x^3 = x·x^2
x^7 = x·(x^3)^2
x^15 = x·(x^7)^2
One actually figures which computation to make by reversing the order: 15 = 2·7+1, etc.
You need to store x at all times. You first store x^3, but you can throw it away when you've computed x^7. You need at most two memory locations to do the computation. Why should you care? Because in cryptography and in prime searches, you're often multiplying million-digit numbers!
Post a Comment