Tuesday, 24 June 2008

Pick Two

A colleague from Colorado sent me an interesting probability problem the other day. I like it because it illustrates one of those serendipitous qualities of mathematics. Here is the problem. A Jar has a mixture of Red and White balls so that if you withdraw two, the probability of getting two alike, or two of different color are both equal to one-half. You may want to stop and try it before you read on.

Ok, so we let r = the number of red ones and W be the number of white ones, and the total is r+w. So how could we draw one of each color? Well, red first, and then white, or white first and then red. If we find the probability of each of these conditional events and add them up, that will have to equal 1/2. Ok, the probability of red on the first draw is r/(r+w), and on the second ball the probability is w/(r+w-1) since one of the red balls will be missing. The opposite order is exactly the same with the w and r reversed, so the probability of getting one of each color is 2rw/[(r+w)(r+w-1)]. Setting that equal to 1/2 we get

If we exapand (r+w)2 and subtract the 4rw we get 0=r2-2rw +w2-r-w. NOTICE the symmetry, we could exchange r and w and get the same equation. We know right off that any solution (a,b) will have another soltuion (b,a).

One of the things that is often hard for students is to think of one variable as a constant and the other as a variable. I like to use the word "pronumeral", like a pronoun only instead of him or her we say "that number". It is like a variable that doesn't vary, we just don't know what it is in a particular case. So think of w as if it were fixed. We have that many white balls in the jar and we are wondering how many red can be put in to make the problem work... see it.. w is a "fixed" unknown, but r is going to "vary". That makes the equation a quadratic in r; Ar2 +Br+c=0 where A=1, B= -2w-1, and C=w2-w.

We can solve this using the quadratic formula, but if this solution is going to be a rational number, and the number of balls in a jar must be rational, then the discriminant, the expression under the squre root radical in the quadratic forula, B2-4AC, must be a perfect square. B2= 4w2+4w+1 and 4AC= 4w2-4w; so B2-4AC= 8W+1. If there is a rational solution, it must be when 8W+1 is a perfect square. Wait, I know this one! That's a problem from number theory. The numbers that make 8W+1 a perfect square are called triangular numbers; 1, 3, 6, 10, 15. They are the sum of the first n counting numbers. But a neat thing happens if we plug 1 in for W, the solution for r is 3.... and if we use 3 for w, r=6. Each time we substitute one of the triangular numbers into the quadratic, the next comes out as a solution. So the probability of drawing two balls of the same color, (or of two that are not alike) will equal 1/2 whenever the number of balls of each color are consecutrive triangular numbers. A very geometric solution to a very algebraic question.

Friday, 20 June 2008

More on The Am-Gm Inequality

The arithmetic mean-geometric mean inequality is an equality in only one situation, when all the numbers are the same. It would seem such an obvious statement would be of almost no mathematical use, but in fact, it is a very useful tool. If you graph y=(x)1/3 you notice that the function is always increasing. That means if a1/3 > b1/3 then a>b. That leads to a rather big idea in algebra/geometry.

When we seperate a number into parts that add up to that number it is called a partition of the number. One partition of 12 into three values is 6 + 4 + 2. What we get from the Am-Gm inequality is that the products of any partition is greatest when the elements of the partition are all equal. For partitions of 12 into three numbers, the highest product is 4(4)(4)=64.
Try any of others, it will always be less. (6)(4)(2) is only 48; and 6(3)(3)= 54. There are others, but none of the partitions of three numbers will be as large as 64.

You may be intuitively familiar with an example of this from geometry. Take any rectangle with a given perimeter; the one with the largest area is a square. In fact, the square is the largest area for any quadrilateral with a given perimeter.

You can prove the same propetry for triangles algebraicly with Heron's formula. You remember Heron's formula; for any trinangle with sides a, b, and c, we find the semi-perimeter S= (a+b+c)/2. Then the area is given by [S (s-a)(s-b)(s-c)]1/2. If we hold the perimeter constant, then s1/2 is a constant, and we can rewrite the area as the product of two square roots, (s)1/2 times [(s-a)(s-b)(s-c)]1/2. But since (s)1/2 is a constant, the area is larger or smaller depending on the product of (s-a)(s-b)(s-c); and from the Am-Gm inequality we know that this product is largest when all three values are equal. But s-a = s-b=s-c means that a=b=c, so the maximum area for any perimeter is when the triangle is equilateral.

With a little geometric effort, you can show that the same is true for a polygon of any number of sides, the one with the greatest area for any perimeter is the regular polygon.

Concave polygons have a angle that juts into the interior of the shape, and convex ones do not. It should be easy to see that if a shape was concave you could just flip the concave part out and keeping all the sides exactly the same length you have created
a shape with a larger area, so trivially (always be suspicious when that word is used, even now) a maximal area for any perimeter will be convex. Now imagine a convex polygon and focus on three consecutive vertices.

Now create an ellipse that has its two foci (that is the plural of focus) at the two extreme vertices, and passes through the third point. One of the properties you ought to remember about an ellipse is that the sum of the distances from any point on the ellipse to the two foci is a constant, so if we move the one point along the ellipse, we will not be changing the length of the two sides, and the perimeter of the polygon is staying constant. Now what is happening to the interior area of the polygon as we move this point along the ellipse. The only part of the interior of the polygon that changes is inside the triangle formed by the three vertices. But this triangle has a constant base, and as we move the third point around the ellipse.... we are changing the height of
the triangle. The area is the greatest where the height is the greatest, and that happens when the altitude rises from the midpoint of the two foci; and at that point, the triangle is isosceles. The area is greatest if we make these two sides of the polygon equal. Now pick three other points, and repeat endlessly until all the exterior sides are congruent to maximize the area.

Closing with a neat toy you can use if you want to post mathematical equations in your blogs or MySpace pages (and I KNOW you want to do that). You can download it atthis link ;and keep it on you web page or save it to your google homepage or ... be creative..

Tuesday, 17 June 2008

What Mean Did You Mean?

Most of your math studies have focused on equations and identities… stuff on one side equal to stuff on the other side. Lots of big ideas in math, however, involve inequalities; where one thing is always less than another, or at least less than or equal. I was thinking about one flying back to the US (and boy, are my arms tired…. Ok, very bad, forgive please) and it offered the additional chance to introduce a notation you might not have seen yet.

Most of the time when you hear the word average or mean you think of them as the same thing. Add up all the numbers and divide by how many numbers there are. OK, the actual name of this is the Arithmetic Mean; but as far back as Pythagoras the Greeks had several others . There is a a Heronian mean (remember Heron and the formula for finding the area of a triangle given the three side lengths?)although the term sub-contrary mean was used (Pythagorus lived 500 years before Heron).Another ancient mean was the harmonic mean (this is the one you use to answer questions like what is your average speed if you drive to town at 60 mph and drive home at 40 mph..and the answer is NOT 50 mph), and even the standard deviation you studied in statistics units, is a type of mean, called the RMS, for Root-Mean-Square. But today, we want to talk about the arithmetic mean, and the geometric mean and a special inequality that ties them together.

If you remember arithmetic sequences, and geometric sequences, the big idea was that one was about addition (or subtraction) and the other about multiplication. That idea about the names extends to the arithmetic and geometric means. Ok, so let’s use a little formal notation, cause it feels so good. You know the arithmetic mean… where x1 means the first number and x2 the second, etc… and you probably even remember that we can write it compacted using the Sigma notation, .
The geometric mean works the same way, except instead of adding the numbers, we multiply them, and instead of dividing by n, we take the nth root. So for two numbers , say 2 and 8, the geometric mean would be (2*8)1/2 = 4. If there were three numbers, we would take the cube root of their product, etc for more numbers. If that sounds like a screwy way to find the middle, let me point out one of the places it is useful. Suppose you have a triangle with sides of 3, 5, and 10. The perimeter is 18. What the arithmetic average gives you is the length of the sides if you wanted to make a triangle with the same perimeter and all sides equal, in this case we want each side to be 6.

If a rectangle has sides of 2 and 8 then its area is 16; but what if we wanted to make a rectangle with the sides all the same that had the same area. That would be a square, so we take the square root of 16 and get 4. The geometric mean of 2 and 8 is 4. We can do that with a solid too. Take a box with length, width and height of 2, 9, and 12 respectively. The volume is 216 cubic units. If we want a perfect cube with the same volume, we take the cube root of (2*9*12) and get 6. We say the geometric mean of 2, 9 and 12 is (216)1/3. Of course we could do the same thing with any number of values, but the meaning in four-space or five-space etc, is a little harder to visualize. We even have a symbol for multiplying that allows us to write products in a condensed form similar to the sigma notation. The symbol we use is a capital Greek Pi. We can write when we want to multiply (1+2) (2+2)(3+2)(4+2)(5+2). Notice we incremented through the numbers from 1 to 5 and added 2 to each, but instead of adding as we do with sigma notation, we multiply. Then we can write the geometric mean as when we mean [(x1)(x2)…(xn)]1/n. If you remember how you can write a sequence in your TI-calculator and use the "sum" command to do the sigma notation, then you will be thrilled to know there is a command to find the product of the numbers in a string (look one line below the "sum" entry on your calculator.

So NOW we are ready to get to the big inequality we wandered through all that to get to; for any group of numbers, the geometric mean is always less than or equal to the arithmetic mean. Try a few simple ones, with two numbers, say 4 and 9, the geometric mean is 6, but the arithmetic mean is 6.5; or pick any three numbers of your choice and try it again.

For two numbers there is a really cool (is it still ok to say “cool”) geometric proof that is totally visual, and it gives me a chance to show you one more way that the geometric mean is MEANingful (couldn’t resist). If we take two lengths, call them a and b, and place them together on a single line, then M is the midpoint of a+b, and a+b/2 is the distance from m to either end of the line segment. But if we let the line comprising a and b be the diameter of a semi-circle, the perpendicular distance c from P, where a and b join to a point on the semicircle is the geometric mean of a and b, and r is the arithmetic mean. It is clear that r, being the hypotenuse of a right triangle, is always going to be greater than or equal to c, a leg. It is also easy to show that c = (a b)1/2, the geometric mean of a and b. Since r=(a+b)/2, then the distance MP is r-b, which is (a-b)/2. So we have r2 = c2+MP2 . Substituting in we get (a+b)2/4 = c2 + (a-b)2/4 so 4c2= (a+b)2 –(a-b)2 . The right side of this is a2+2ab+b2 – (a2-2ab+b2) and when we subtract we are left with 4c2 = 4ab, or just c2 = ab, hence c=(ab)1/2 and is the geometric mean of ab.

Later, I will try to show a really nice application of this inequality to solve the birthday problem.

Friday, 13 June 2008

Mr Galloway's Jumping Frogs.

Mr Galloway sent me an animated puzzle on a excel spreadsheet that he and Mr Brock had been trying to solve (Ok, obviously they have WAY to much time on their hands) It is supposedly from a 2nd grade test in China or somewhere (don't belive everything you read on the internet, children). You can play it (and save to your own computer if you want) here . I'm going to wait to publish the solution, but if you are going crazy, here are two helpers... One, If you post a comment, someone will respond...even if it has to be me.. two,, a generous tip... two in a row of the same color is wrong, and finally a tip from old Sherlock Holmes who said"When you eliminate the impossible, what is left, is possible... I'll get back to this in a few days. THINK! And if you solve it, send me a comment.

Ok, too easy for some.. so there is a 2 dimensional variant of the puzzle here

The problem was first published by
Eduard Lucas, a 19th century French Mathematician; but versions of the problem may well date back to 8th century Arabia.

Lucas also created the Towers of Hanoi problem, try it here. He also did LOTS of work on the Fibonacci sequence (1,1,2,3,5,8,13...) and developed a generalized version that is called the Lucas sequence

Thursday, 12 June 2008

Counting with Polynomials

Here is a little counting problem I just came across that makes me glad to live in the age of computer algebra systems. You already know that there are 538 electoral votes distributed among the fifty states, and probably also know that it takes 270 of them to get elected. If you didn't know, you get them in clumps. Winning the state of Texas gives you 34 votes, winning Utah only nets 5. The number of votes for each state is here in case you want to try to solve the problem yourself.

The problem involves a mathematical idea we call a "critical coalition". The idea is to find enough states that could be grouped together (hence the coalition part) to add up to 270 or more, but only JUST enough. The critical part means your coalition is balanced so that if any state drops out, you do NOT have 270 or more votes. That's it, just make a list of everyway you could combine states to make a critical coalition; no fuss about political realities... just pure counting math. If you can handle that problem by ANY method, you can probably stop reading now because I have little to teach you. I'm bringing it up because I saw a really great solution Isabel Lugo who writes the blog "God Plays Dice", which is very worth reading.(and if you are doing the problem, I will give her numeric solution at the bottom so that you can check your work, or hers). If you are young and not used to a lot of variables, pick up a pencil, make lots of notes, read slowly, reread, struggle with it...it really is powerful stuff.

Isabel's solution was to multiply (1+x^55)*(1+x^34)*(1+x^31)*(1+x^27)*(1+x^21)^2*(1+x^20)*(1+x^17)*(1+x^15)^3*(1+x^13)*(1+x^12)*(1+x^11)^4*(1+x^10)^4*(1+x^9)^3*(1+x^8)^2*(1+x^7)^4*(1+x^6)^3*(1+x^5)^5*(1+x^4)^5*((1+x^3)^8-1). Ok, this is only part of the solution, but when you multiply that big polynomial, what it will give you is the number of coallitions you can put together of EVERY size that includes at least one of the states with three electorial votes. This is a polynomial of degree 538, and it has encoded in the coefficients of the terms some of the numbers you need to answer the questions.

To try to make that understandable to my high school readers, here is a smaller, but similar problem. What are the critical coalitions of pools of 2, 2, 3, and 4? Those total to 11, and you need 6 to get a victory. I think you can figure this one out by hand, so let's do that first. The set 4+3 is a critical coalition, they add up to 6 or more, and if you take either of them away, it doesn't. Likewise 4+2 forms two coalitions, one with either 2. Another is found by 3+2+2, and I think that is all of them. So we have a total of four coalitions. Now doing this one with a polynomial is longer than doing it by hand, but it shows you how to get the answer by polynomials (with a computer's help of course).

To represent the solutions with a polynomial, we use (1+x^4) for the pool with four votes, (1+x^3) for the pool with three votes, and (1+x^2) for each of the pools with two votes. For a minute I will ignore the -1 at the end of one Isabel's solution, but fear not, we will bring it back in a few lines. When we multiply (1+x^4)(1+x^3)(1+x^2)^2 (the last is squred because there were two of them) we get x^11 + 2 x^9 + x^8 + 2 x^7 + 2x^6 + 2x^5 + 2x^4 + x^3 + 2x^2 + 1. So what?, you ask. If you look at the coefficients of each term (the numbers in front) you get the number of coalitions (not critical, just any old coalition) that can be formed that have as many votes as the power of x. For example, the 2 x^9 tells us that there are two coalitions that have 9 votes. We can see that would be 4+3+ 2 and 4+3+(the other )2. And what about 2 x^7? Well, we can have 4+3 for one coalition, and 3+2+2 for another. See how that works? Check the others to be sure I didn't mess up (and if I did, write a nice correction comment to help me out).

Now that doesn't answer the critical coalition question, but it is a great calculating tool. And if you are still trying to figure out how many eight letter words can be made using the letters in Mississippi that I asked in my recent blog, Yes, Barbie, Math is Hard, then the polynomial method described above should help.

But what about this problem? We can count all the coalitions, and even tell if they have a majority (2+2 is still a coalition, even 2 or 3 by itself is a considered a coalition, but they don't have a majority), but we can't figure out if it is critical or not. And that is where the -1 in the last term of Isabel's polynomial comes in; it allows us to eliminate all the coalitions that don't contain some solution. In our mini-problem, if we change the last term to (1+x^4)(1+x^3) ((1+x^2)^2 -1) we get a listing of all the coalitions that contain a 2. x^11 + 2 x^9 + x^8 + 2 x^7 + 2x^6 + 2x^5 + 2x^4 + x^3 + 2x^2 + 1 - ((1+x^4)(1+x^3)) . That leaves us x^11 + 2 x^9 + x^8 + 1 x^7 + 2x^6 + 2x^5 + 1x^4 + 2x^2. Now each of these coalitions have at least one member who had two votes, so we want to only count the ones that have a total of 6 or 7 since those are the only ones which would be critical. The two is the smallest member, so his absence would only impact the success of coalitions with 7 or less votes. Looking at the terms with powers of 6 and 7 we see that there are 3 such critical coalitions, (3 + 2 + 2; 4+2 and 4+ (other)2). Ok.. so what about coalitions that DON"T have a two... We just take the x^2 term completely out of the mix, and multiply again with -1 on the x^3 term.....(1+x^4)((1+x^3)-1) gives us x^7 + x^3. Since only the x^7 is a winning coalition, and it must be critical because if we took away the 3, the total is less than 6. And that is all of the winning coalittions, if we leave out all that have a 2 and a 3, we are left with 4, which will not win. Add the three that include a 2, and the one that does not, and you get all four coalitions. When Isable did that with her BIG equation, she came up with ...wait for it...51,199,463,116,367 ... that is how many different critical coalitions of states could be combined to get the 270 electoral votes needed to be elected President.

Ok, so now a practice problem for you.. suppose we had voting pools of 2, 3, 3, 5, and 7 for a total of 20.. that means 11 for a majority. Can you figure out how many critical coalitions there are.. if you want to submit a comment, we can walk you towards the answer with some hints and (if needed) corrections. Good luck.

Tuesday, 10 June 2008

Thoughts While Avoiding Grading Papers

Trying to avoid actually grading semester exams, I was playing around with a problem from F. Mosteller's classic, "Fifty Challenging Problems in Probability." Problem two concerns a three-set tennis match in which the player, a youth named Elmer, will alternately play against his father and the club pro, given the club pro is a better player than the father. He will win a prize if he can win two consecutive matches of the three. The question is whether he is better of playing the sequence father-pro-father or pro-father-pro.

The counter-intuitive part is that his odds of winning are better if he plays the better play, the pro, more often. (This reminds me of Parrondo's paradox, which I will try to write about soon) Here is a simple explanation (I hope). If we let f represent the probability he wins against his father, and p the probability he beats the pro, then to get two consecutive wins, he must win the first two or the last two, so we need the probability win, win added to the probability of Lose, win, win.

For the sequence father-pro-father the probability of success is fp + (1-f)pf. We can distribute the 1-f to get fp + fp - fpf, and factoring fp out of each term we get fp(2-f).

If we do the same with the sequence pro-father-pro we just interchange the p and f to get pf(2-p). Now since we are given that p is smaller than f (he is LESS likely to beat the better player) we see that 2-p must be larger than 2-f, and so the pf(2-p) is the higher probability.

The advantage when actually calculated is very small. For example, Ifthe probability of beating his father is .4, and the probability of beating the pro is .2, his probability of winning in the father-pro-father sequence is about .128 . By switching the order to play pro-father-pro his probability of success increases to .144(which is twice what it would be if he only played a three set match against the pro).

What happens if we change these probabilities of success, but keeping the order so that the pro is better than the father? Letting p remain at .2 and raising his level against his father to .5 improves his chance of success to 18%. In fact, if we substitute the value .2 into the expression pf(2-p) we get .2f(1.8).... the probability of success is a linear equation, .36f. If we let his probability against his father go to one, you can see tha the has a 36% chance of winning if he goes Pro-father-pro. But if you look at the other sequence, fp(2-f), and again substitute in the .2 value against the pro, the equation is quadratic, .4 f - .2f2. Visualizing the graph of this negative quadratic, we can see that he vertex will occur when f= 1, so that is the maximum, and when f=1 we get a probability of success of .2, exactly what his probability against the pro in a single game would be. This makes sense if you consider that if he ALWAYS beats his dad, the match really depends on the one game in the middle against the pro.

How would a fourth game alter the mix? does it matter in which order he plays? It would seem that with four games both orders might be equal, but lets look at the possible winning paths for each.

When the order is p-f-p-f two wins can happen with probabilities pf + (1-p)fp + (1-p)(1-f)pf. Now compare the probability when the order is reversed, fp + (1-f)pf + (1-f)(1-p)fp. Note that all the terms except the second are the same. Once more the fact that 1-p must be larger than 1-f (because f is greater than p) leads us to conclude the best order is to play the pro first.

Sunday, 8 June 2008

Indexed... commentary on a 3x5 card

Jessica Hagy has a blog that probably has less words per blog than any on the net, yet it often says more than most as well. The one above is a recent example. READ, REFLECT, ENJOY?

A Little Arithmetic Test

OK, quick, evaluate the two arithmetic expressions below

3 + 5*7............. 2+5 * 8

Ok, if you remember high school algebra, the answers are 38 and 42. If you don't remember high school algebra, you may have gotten 56 on both. The formal order of operations that we try to get across to high school students is that these questions should be done by first completing the multiplication or division operations, and then do the addition or subtractions. (for the one on the left, you should multiply 5 * 7 first, then add the 3)

The amazing thing, according to research by cognitive psychologists David Landy and Robert Goldstone from Indiana University, is that you were more likely to miss the second than the first, and even if you are an old hand at simple arithmetic, the second may have taken a micro-scosh longer... because of the way they are spaced. Notice that in the first I have grouped the multiplication operation more tightly and in the second the addition operation is grouped tightly. The researchers write,"When physical spacing was inconsistent with
order of precedence rules, six times as many errors were made relative to when the spacing was

The grouping by proximity seems to be a natural process affecting how we read and write expressions. In the authors own words:
"Specifically, we propose that formal notations are diagrammatic as well as sentential, and that the property conventionally described as syntactic structure is cognitively mediated, in part, by spatial information. Elements of expressions are “bound” together through perceptual grouping— often induced by simple spatial proximity."

According to the research, it even effects the way you write the expressions. They tested people by giving them random mixed expressions using words with addition and multiplication in both orders, such as "Four plus seven times three". and asking people to write them down. It seems that people wrote them down with the multiplication operation more closely grouped than the addition.

The suggestion of the researchers is that this grouping tendency may be observed from parents and teachers and become part of our reading and writing style even if we do NOT remember the order of operations. However, there was a greater accuracy of the results of people who tended to group, "Consistently spaced submissions were also more likely than either inconsistent or
unspaced expressions to be correct; 53% of consistent equations were correct, compared with
only 37% of inconsistently spaced and 50% of unspaced equations." To me this would seem to support a written response that indicates a cognitive bias based on knowing the order of operations more profoundly.

Thursday, 5 June 2008

I give up, Math is really not hard

OH GOD, I give up, Math is really not hard (but it really is)…..

A BBC article finally broke the news to the British people, “The British are uniquely happy to admit being bad at maths.” If I didn’t have a calendar in front of me I would swear it was the early eighties and I was reading the same articles that appeared all over America during the years when the National Council of Teachers of Mathematics developed their “agenda for action”..
The article had lines like “Imagine a famous television presenter joking that they couldn't read” and later, a successful “former maths teacher” (for the non-studious, he don’t teach math no more, but that doesn’t mean he won’t tell you what’s wrong with math education…) “John Dunford, general secretary of the Association of School and College Leaders and a former maths teacher(emphasis added), publicly bemoaned the fact there were Lord Mayors who proudly said they couldn't do maths.

"I think people see maths in a different light to English language. They see it as being hard but it's no harder than other subjects”. Okay, that seems reasonable, but wait, the article says that people would never suggest they couldn’t read (because they can) but they admit that they have difficulty understanding math… wait… does that mean that, in fact, Math IS different, mathIS harder???

Ok, one more time… Here is one of many reasons why math is harder than other areas of study. Try to think of a problem in literature, social studies, whatever your favorite field of interest is; but there is a catch. The problem has to be simple enough that any 15 year old could understand it completely, but so difficult that no one on earth can solve it, or maybe someone can solve it, but only about ten people in the world would understand the answer. Wait, let’s add a third rule, the problems has to be one that has been studied for over a century… Got one???? Well math has, lots of them…

In 1900 when David Hilbert, whom many believe was the best mathematician of the era, listed the great unsolved problems for the future of math, several of them could be understood by a typical high school student. Some of those same problems still remain unsolved, and many are understandable, by a 15 year old high school student. How about an easy one from geometry, it was his third problem. Math folk know that if you take any planer closed simple polygon (a rectangle, or pentagon or any of those).. you can cut it up into a finite number of pieces and reassemble the parts into another polygon, ANY other polygon, that has the same area. If the problem is a three dimensional solid, there is no such nice relationship, in fact, it has been proved that there are some solid shapes that you definitely can NOT cut up and reassemble into some other particular shape.. The problem is easy, but the solution is a bear (0K, I was going to say bit**, but trying to keep it clean here).

Wait, there is more. Hilbert’s eighth problem was simple enough for a grade school student to understand, every even integer greater than two can be expressed as the sum of two primes. NO fancy language… 4 = 2+2; 6 = 3 + 3; 8 = 5+3; 10 = 5+5…etc.. Simple, but guess what.. not only was there no proof in 1900, there still wasn’t one in 2000, and my bet is that there won’t be one by 2100. Ok, I know its true, you know its true… John Dunford, (he was the guy earlier who said “math is easy”) knows its true, but he can’t prove it either.

OK, if you haven’t been sleeping under a rock, you’ve heard about Fermat’s Last Theorem. It’s sort of like the Pythagorean theorem (of course you remember, a2 + b2 = c2. It works for non-zero integers; for example 32 + 42 = 52). There a proof that there is at least one set of integers that make it true. Somewhere back about the fourth century AD (about the time the Bible is being put together), a guy named Diaphantus suggested that it couldn’t be done with cubes or fourth powers or anything higher than squares. Jump forward to the seventeenth century, and a guy named Fermat, (the guy in the picture at the top) just an amateur mathematician who proved lots of hard stuff. He owned a copy of Diaphantus book, and next to the problem he wrote something like, “I have a marvelous solution, but it is too large for the margin of this book.” Then he died… ohhhh … very evil.. So now everyone is looking for Fermat’s proof. A hundred years pass, then two hundred; three hundred; four hundred… I’m in high school, I hear the story.. I’m sure I can do it but…. NOPE.. never happened.. then just before the dawn of the 21st century, a guy comes along and proves the thing. Huge press releases.. but they don’t last long. To prove the theorem, he had to piggyback on four hundred years of other peoples efforts and then, solve a theorem in a field so unusual that it was suggested that only eleven people alive in the world could understand the proof.

Let me break it down one more time… MATH IS HARD.. Harder than almost anything else you will try.. harder than skipping rope.. Harder than juggling (but just), and at least as hard as riding a unicycle (I can’t do that yet, so I’m thinking it may be VERY hard).

That’s why people who think it is no big deal to read or write or run big companies will say… I’m not very good at math. You can be pretty bright and still struggle with math… maybe the guys who want to tell people how easy it is should do some of those tough things that other people can do who find math a bit challenging… Try walking across Michigan on Stilts, for instance.

Tuesday, 3 June 2008

Shakespeare, Starlings, and Exponential Growth...

It is an everyday springtime scene across America, you walk out of the house and there it is, the big messy pool of bird droppings. You look to the eves of the house, or the trees next to the driveway, and mentally curse the little winged creatures who left the mess,… but the fault dear Butkus, is not in our trees, but in our Bards… Yep, Blame it on Shakespeare.
Your problem began in a place far, far away, both in time and space. Sometime just before 1600 Shakespeare, apparently conscious of the ability of the starling to mimic the sounds of other birds, was writing Henry IV. Remember that scene? Hotspur plots to drive the king mad by “, I’ll have a starling shall be taught to speak nothing but ‘Mortimer’ “, the name of Hotspur’s in-law whom the King refuses to ransom.
That’s essentially all it took… well, that and a somewhat strange group who operated in America late in the 19th century, the American Acclimatization Society. Their goal was to introduce every bird mentioned in Shakespeare into the US. Keep in mind that Shakespeare names over 600 birds in his works…(honest, I counted) including the starling, and the sparrow… Yep, the one you call a common house sparrow… they are English, …. Not a native at all, and the same people brought them to America. WHY??? Because Shakespeare wrote:

Not a whit, we defy augury. There is special providence in the fall of a sparrow. If it be now, 'tis not to come; if it be not to come, it will be now; if it be not now, yet it will come—the readiness is all. Since no man, of aught he leaves, knows what is't to leave betimes, let be".

Knowing that Laertes is out to kill him, he still accepts the contest, giving himself over to fate......The reference to the sparrow comes from St. Matthew, chapter 10: (29-31) "Are not two sparrows sold for a farthing? and one of them shall not fall on the ground without your Father.(knowing)"

By the way, the augury of which Hamlet spoke refers to predictions from a priest, called an augur, who studied the birds to predict the fates of men.
But I digress, so back to Shakespeare and the bird-brains (oops bird-lovers) of the Acclimation Society. In 1890 and 1891 they released about 100 starlings into Central Park in New York City……and from that motley band, they grew, and flew, and grew some more. By 1960 they had spread coast to coast and were in every county in the 48 United States (I’m omitting those late-comers in Alaska and Hawaii, but I bet Alaska has starlings too. In the 1960’s, they were considered such a threat to the economy of California that there was a mass attempt to exterminate them, killing over 9 million of the birds. There were numerous other attempts to kill them off around the country, especially in agricultural states where they were thought to pose a threat to grain crops. The starlings just scoffed, and went on growing…growing….growing… until today there are 200 Million in North America, (Mr. Bush’s fence and treaties with Canada have not restricted their holidays in both neighboring countries). I read a quote by a Jeffrey Rosen who said, “It isn’t their fault that they treated an open continent much as we ourselves did.”

I did the arithmetic, and even ignoring the millions killed in the fifties and sixties, they grew at upwards of 13% a year. I expect it was actually much faster, and that the growth follows a logistic curve with an upper lever somewhere near the present population. Kill a few million and they will almost immediately repopulate to their present number. But if they can acclimate to a little more heat in the south of Mexico, or the cold north of Hudson’s Bay… they could tack on another 100 million easy.

Eventually, they may create enough pressure on the native American birds, that the “Blue Bird on My Shoulder” will be the only one left. Then New York and Missouri will have to find a new state bird (yes Virginia, the Eastern Blue Bird IS the state bird of Missouri).

By the way, we got our revenge... The English are being ravaged by the American Grey Squirrel.

Sunday, 1 June 2008

Yes, Barbie, Math IS Hard!

A short while ago in in “Average, Percent, and other Misunderstood Math Terms”, I wrote about the fact that even simple math was particularly hard in application. I got three replies that suggested I had committed some unpardonable sin, and two even reminded me of the hassle when Mattel released the talking Teen-talk Barbie, who expressed a similar concern in her tiny little recorded voice by adding “Math is Hard” to her other stereotypical exaggerations of modern teens, such as “I like to shop.” I figured if a merchandising mishap 17 years ago by a toy company is the best they can do to challenge my statement, I MAY actually be right.

But to be fair, I wanted to explain why I thought math was hard, and while I was thinking about it, a couple of VERY good mathematicians brought up a minor variation of a somewhat easy and common high-school text book problem.. Only this problem is VERY hard. Its a high school problem that IS in a high school textbook, although it probably shouldn’t be, and it had the wrong answer in the back of the book .. we know it is wrong, …too big.. but we don’t have the right answer yet… keep in mind that teen talk Barbie is older than most of the students in my classes who would have been expected to solve the problem. You can still buy her on the Amazon link in the last sentence, and she still says “Math is hard”,… hang in there Barbie.

So here is how an easy problem crosses the border from easy to incredibly hard in a few steps. We begin with a linear permutation. To make the problem even easier than the one in the textbook, lets deal with only five beads.

Question one, easiest… Five different colored beads are to be placed in a row. How many ways can it be done…Easy, five factorial or 120 ways. You have five choices for the first color, then four choices for the next .. etc.. so the answer is 5(4)(3)(2)(1) = 120…

Question two, a minor variation… How many ways can the five colors be laid in a circle? Now we have a clinker (think Christmas Story and the furnace). Red, orange, yellow, green, blue is the same as orange, yellow, green, blue, red. It is also the same if we write them starting with yellow, green… etc.. so in the case of a circle, we can only get 5 factorial divided by 5 or 24 different circles.

Question three, a spatial flip.. Now instead of putting them in a circle on the ground, we put them on a hoop of wire, for a necklace or bracelet or something. Ok, still a circle so 24,… but wait.. we can reverse the necklace so that now blue, green, yellow, orange, red is the same as red, orange, yellow, green, blue.. and similarly for any list of colors, so we have to divide by 24 by two and now we are down to twelve unique necklaces that can be made… think goodness it can’t be any harder than that….(gotcha’)

Question four (really hard and if you go up to 20 beads, as the text book did, a total mess) What if there are not five colors, let’s be really easy, what if there are three red and two blue? Now the problem requires us to look at every possible order of the beads and decide how many ways it can be reflected in space or rotated around the wire… You could have 3 reds together and 2 blue…or you could have two reds, a blue, a red, and another blue… We could also have red, blue, red, blue, red… is that it? What if we had a blue, two reds, a blue, and another red… NOPE, that one is already counted.. can there only be three ways to order these five beads on a necklace. Math got hard because all the way down to the last problem we had some formula approach we could use if we understood the problem… and then… it all fell away..

If you need a challenge, the original problem had fourteen beads of one color and six of the other.. try your luck.

A very similar problem uses the letters in the spelling of Mississippi.. Writing words is a linear permutation, so we don’t have to worry about flipping the necklace or circular similarities, but that doesn’t make it easy. Students are taught, using the same rule we used for the beads in a row, that with six distinct letters there are 6 factorial orders (that’s 720) . With 11 letters there are 11 factorial (a lot more than 720, in fact almost forty million) . But then if we repeat letters, we show them that they have to divide by how many letters appear more than once..

If you write out all the 11 factorial arrangements of the eleven letters, all of them have two p’s that are indistinguishable. If we switched the two p’s no one would know; so we have to divide 11 factorial by 2. But then, there are four letters s in the word, so you have to divide by the 24 ways they could be switched around, and then there are four letters i, so we have to divide by 24 yet again. Finally we have reduced the unique orderings of Mississippi down to only 34,650 (IF I did that right) . You can list them out to check, but that may take a while… If you want to try an easier one that you can see how, try finding all the possible orders of TOOTH; there should be only thirty…

Now we make a subtle change in the problem and make it horrible, what if we don’t use all the letters? What if we only use eight of the letters in Mississippi at a time? One word has all four of the letters s, another might only have three, and some would only have one s (with eight letters, there has to be at least one of the letters s in the word, can you see why?) Try your luck figuring out how many three letter “words” you can make with tooth.

I think that is the big difference between math and other subjects, that razor fine line where easy problems become totally intractable. Maybe math is easy, and I (and Barbie) are just not too bright). By the way, how many eight letter "words" could YOU find using the letters in MISSISSIPPI?