Monday, March 30, 2009

Pascal's Triangle in TinkerPlots


The posts on this blog that have talked about Pascal's Triangle have all used diagrams drawn with TinkerPlots. Aside from its value as educational software, TP is good for drawing diagrams like these (and others, like the polygonal number diagrams described here) that are derived from calculations.

A TinkerPlots document that can draw these diagrams is found here. The images at the top of the post were created with this document, and show some of the modular patterns in Pascal's triangle (for mod 2 and mod 7).

Thursday, March 26, 2009

Pi's first six in a row

If you look at the 'pi color map' and see a vertical stripe, what you are seeing is a run of repeated digits, like 7777, 00000, or 222.

One occurs in the top left:


Sequences like this used to be important examples in motivating discussions about the law of the excluded middle. Statements like: 'the decimal expansion of pi contains the sequence 7777', according to the law of the excluded middle, are either true or false. But when you are discussing something that has never been calculated, and that might never be calculated, suggests (to constructivists), that the statement may be neither true or false, and that the sequence 7777 may be somewhat like Schrodinger's cat, neither existing nor not existing.

Now that the digits of pi have been calculated to astounding lengths, and that mathematics exists to uncover the properties the pi digit sequence, the expansion of pi is no longer an ideal candidate for constructivist thought experiments. Even some exotic questions about the decimal expansion of pi, like the convergence of the brower-heyting sequence, have been resolved. Questions about the expansion of pi that illustrate constructivist problems can still be formulated, but they need to be more complicated than they used to be.

Still, I decided to look more closely at this little sequence that occurs (relatively) early on in the pi expansion. The stripe in the pi colour map mentioned above corresponds to the sequence 999999 beginning at digit 763 and ending at digit 768. This was observed in a set of the first 2281 digits of pi.

I decided to push the software a bit further, and load 10000 digits of pi into the document.  (A file with the first 10000 digits of pi formatted for Fathom or TinkerPlots is here.) The plot below shows the digits with 9 in black and all other digits blanked out - dots are single occurrences of a 9, while vertical stripes are runs of repeated 9s.


Using Tinkerplots' runLength function we can see how frequent runs of various lengths are, and easily identify the longer ones.

Even with 10000 digits, the 999999 sequence at digit 763 was still the longest sequence of repeated digits. The other runner-up sequences in this first 10000 digits are, two instances of 2222, a single run of 8888, and four distinct occurrences of 7777.

Interestingly, an obituary for pre-digital-computer pi-expander John Wrench was posted today on the MAA Math DL site

The plot at the bottom of this post shows the distribution of even and odd digits in the decimal expansion of pi's first 10000 digits, and was inspired by a similar plot from Wolfram Math World. 


Monday, March 23, 2009

False Positives

There are plenty of probability problems that have counter-intuitive solutions. Problems like these, and how they can undermine common sense, are among the best reasons for looking at probability theory. One set of humbling questions is the family of Monty Hall problems. Another are those related to conditional probability; nice examples of these are problems that involve medical tests that give 'false positive' results.

Simulation is a way of exploring these problems that reveals more than mere theoretical probability calculations do. The structure of the simulation can reflect interesting aspects of the structure of the original problem, and the results reveal a variability that is not apparent when you simply calculate the theoretical probabilities on their own.

This post shows an example of a 'false positive' probability problem and a Fathom simulation for it. This problem was adapted from one found in the 4th edition of Ross's A First Course in Probability (p.75):

A laboratory blood test is 95 percent effective in detecting a certain disease when it is, in fact, present. However, the test also yields a "false positive" result for one percent of healthy persons. (That is, if a healthy person is tested, there is a 0.01 probability that they will test positive for the disease, even though they don't really have it.) If 0.5 percent of the population actually has the disease, what is the probability that a person who has a positive test result actually has the disease?


Here are the attribute definitions that you could use to build a Fathom simulation for this problem:


The attributes are enough to run the simulation, but it is better to also add the following measures:



To run the simulation you can add new cases (try ~500). Using a measures collection, you can re-run this experiment hundreds of times (collecting a 100 measures re-runs the 500 person experiment 100 times).

If you are calculating the theoretical probability by hand, it helps to write down all of the probabilities (fill in the blanks...):


It also helps to visualize the probabilities in a tree diagram:

The outer tips of the tree are filled in using the multiplicative rule for conditional probabilities:
One nice thing about doing this is that you can see how the tree diagram used to calculate the theoretical probabilities is structured in the same way as the "if" statements in the simulation.

A Fathom document implementing this simulation can be found here.

Thursday, March 19, 2009

Explaining

The difficult thing here is not to dig down to the ground; no, it is to recognize the ground that lies before us as the ground.

For the ground keeps giving us the illusory image of a greater depth, and when we seek to reach this, we keep on finding ourselves on the old level.

Our disease is one of wanting to explain.

Ludwig Wittgenstein, Remarks on the Foundations of Mathematics, section VI-31


So the logic of explicaiton calls for the principle of a regression ad infinitum: there is no reason for the redoubling of reasonings ever to stop. 
. . .
Explication is not necessary to remedy an incapacity to understand. On the contrary, that very incapacity provides the structuring fiction of the explicative conception of the world. It is the explicator who needs the incapable and not the other way around; it is he who constitutes the incapable as such. To explain something to someone is first of all to show him that he cannot understand it by himself. Before being the act of the pedagogue, explication is the myth of pedagogy, the parable of a world divided into knowing minds and ignorant ones, ripe minds, and immature ones, the capable and the incapable, the intelligent and the stupid.

Jaques Ranciere, The Ignorant Schoolmaster: Five Lessons in Intellectual Emancipation 


Mathematics educators generally spend a lot of their time explaining. The standard view holds that the best educators are the ones who are good at unpacking and breaking down difficult concepts. However, as the quotes above suggest, there are those who think that an emphasis on explaining is a problem both for mathematics and for education. For Wittgenstien, the perpetual search for explanations in mathematics leads towards a foundational morass and away from the reality of mathematical practice. Ranciere identifies the process of explanation with one of stultification that leads away from intellectual emancipation. This contrarian view suggests that mathematics itself, and the learning of mathematics, is experienced and revealed only in the act of doing mathematics.

Decimals to Fractions

Some students get their first look at manipulating equations when they learn how to convert a repeating decimal to its corresponding fraction (rational numbers yield terminating decimals, or non-terminating repeating decimals). Playing with fractions and decimals is always good in itself, but there are also two nice side-benefits to this simple calculation: first, you can see the surprising result that  0.999... = 1, and second, it helps answer the question 'which fractions lead  to terminating decimals, and which lead to repeating decimals?' Better still, it leads to other questions.

1. The calculation - turning decimals into fractions

A repeating decimal like 0.633633... can be written as a fraction by writing out the equation x =  0.633633..., and then manipulating it so that the infinitely long repeated parts get eliminated. The manipulation is done by multiplying the equation by the right power of 10 to shift the digits, and then subtracting off the original equation.


Perhaps you have a more complicated repeating decimal that you want to fractionalize. The procedure remains essentially the same: obtain two equations that have the same "decimal part" that can be eliminated by subtracting. You might have to shift twice in order to accomplish this. Here is an example:


2. Showing that 0.999... = 1

This school mathematics result has been made into a popular topic of discussion on the Internet. Try doing a search on "0.999 = 1", and see what you find. 


3. Which fractions terminate, and which keep going?

A fraction can sometimes give us a terminating decimal, and sometimes a repeating decimal. It is reasonable to wonder what kind of fractions lead to each kind of decimal.

Thinking about the procedure above might give you an idea for how to think about this question.

If we have a situation where a fraction x = p/q is a terminating decimal, it means that there must be some power of 10, say 10^n, that if we multiply x by  this power we can completely eliminate the decimal (i.e. multiplying by 10^n gives us an integer). This could only happen if the denominator q divides 10^n. This would require q to be of the form (2^m)(5^k), where the exponents m and k are non negative integers (possibly zero), and n = max(mk).

So, a fraction p/q terminates if and only if the denominator is of the form (2^m)(5^k). Consequently, fractions such as 1/2, 3/5, 9/25, 7/8, 3/200, are all terminating, and, for example, any fraction of the form 1/p where p is a prime that is not 2 or 5, will be non-terminating and repeating.

It is reasonable to ask questions about how long the decimals or their repeating parts can be. For a non-terminating repeating decimal, questions about the length of the repeating part are harder to answer.

Friday, March 13, 2009

Resources from this blog

I've started posting some resource files for the posts from this blog here. So far, there isn't much - but in honour of Pi Day (tomorrow) there is the 'Pi Colour Map' TinkerPlots file as described in this post.

Monday, March 9, 2009

Monty Hall and the Three Prisoners

Brian Hayes (http://bit-player.org) recently provided some evidence that there are still many out there who are confounded by the Monty Hall problem (read more about this here).

The Monty Hall problem, perhaps the best-known counter-intuitive probability problem, gets a nice treatment in Jeffery Rosenthal's Struck by Lightning: The Curious World of Probabilities, and is also explained well (perhaps better) in Mark Haddon's novel The Curious Incident of the Dog in the Night-time. Professor Rosenthal has some further Monty Hall explanations here.

I just found an alternate version of the problem in Martin Gardner's The Second Scientific American Book of Mathematical Puzzles and Diversions (published also by Penguin in a slightly different form as More Mathematical Puzzles and Diversions). In the chapter "Probability and Ambiguity" (chapter 19 in both versions of the book), Gardner describes the problem of the three prisoners. Here is a condensed description of the problem:

Three prisoners, A, B, and C are in separate cells and sentenced to death. The governor has selected one of them at random to be pardoned. Finding out that one is to be released, prisoner A begs the warden to let him know the identity of one of the others who is going to be executed. "If B is to be pardoned, give me C's name. If C is to be pardoned, give me B's name. And if I'm to be pardoned, flip a coin to decide whether to name B or C."

The warden tells A that B is to be executed. Prisoner A is pleased because he believes that his probability of surviving has gone up from 1/3 to 1/2. Prisoner A secretly tells C the news, who is also happy to hear it, believing that his chance of survival has also risen to 1/2.

Are A and C correct? No. Prisoner A's probability of surviving is still 1/3, but prisoner C's probability of receiving the pardon is 2/3.

It is reasonably easy to see that the 3 prisoners problem is the same as the Monty Hall problem. Seeing the problem in this different formulation might help those who continue to struggle with it.

It is a nice activity to simulate both the 3 prisoners problem and the Monty Hall problem in Fathom - try it and confirm the surprising results that the "second prisoner" is pardoned 2/3 of the time, and that 2/3 of the time, the winning curtain is not the one you selected first.

There are many, many, ways to write these simulations. Here are the attributes and formulas for a Fathom implementation of the three prisoners:


The table below (click on it to see a larger version) shows a separate simulation for the Monty Hall problem. Here we are assuming three curtains "1", "2", and "3", one of which has a prize behind it. You pick one, and then Monty reveals the contents behind one of the other curtains (the curtain with the prize behind it is not shown). In the game, you have the option of switching your choice for the curtain that has not been revealed.



After creating the attributes, you can "run the simulation" by adding data to the collection (Collection->New Cases...), the more the better.

Incidentally, Gardner's use of A, B, and C reminds me of Stephen Leacock's "A, B, and C: The Human Element in Mathematics."

Addendum

A quick search shows that the connection between the Monty Hall problem and the Three Prisoners is well known (see the wikipedia entries on Monty Hall and the Three Prisoners), and that both are alternate formulations of an older problem, known as Bertrand's box paradox.

Dividing Polynomials - The Grid Method

Update: try out the polynomial division example generator page here.

Students generally learn to divide polynomials using  long division or synthetic division. This post is about another method for dividing polynomials,  the "grid" method. Although this method is used at some schools, I have not found it in any textbook (if you know of any, please let me know).

The grid method makes polynomial division a fun calculation - an almost SUDOKU-like process. The recreational challenge here is to master the method, and to convince yourself that it actually works in all cases (which cases does it work well for, and which are more difficult?).

Before tackling polynomial grid division, you need to be familiar with polynomial grid multiplication. It is the symbolic analog to the familiar "algebra tiles" manipulative, so if you have worked with these, it should be reasonably familiar.

Polynomial Grid Multiplication

In polynomial grid multiplication, the two factors are arranged on the edges of a grid - the number of terms of the factors determine the number of horizontal and vertical lines that make up the grid.

The overall product is found by filling in the cells of the grid with the product of the terms for the row and column, and then summing up all the contents of the interior of the grid. 

What polynomial grid multiplication does for us is provide an explicit way to keep track of the distributive property: each term-by-term product gets its own cell.

In the example below, the two factors are placed along the edges of the grid (1). One factor provides the row headings, the other provides the column headings. Then each cell is filled in with the product of the terms from the row and column (2). Finally, the cells are added together (like terms are combined) to find the final product (3). If the terms of the factors are placed according to the same order (descending powers of x, in our example) and there are no missing terms, then like-terms of the product are found along the diagonals of the grid.


Polynomial Grid Division

Polynomial grid division works the same way as polynomial grid multiplication, but in reverse - we start by knowing one of the factors (placed along the edge of the grid), and by knowing what we want the product to be (without knowing exactly how it is 'split up' in the grid). Using this knowledge we work backwards, filling in the grid and the top edge one cell at a time until we are done. 

Consider the example below. In (1) we create an empty grid with the denominator (divisor) playing the role of one of the factors. Since this question involves a degree 3 polynomial divided by a degree 1 polynomial, we know that the other factor (the quotient) must be degree 2. This allows us to create a grid with the correct size. In step (2) we use the highest power of the dividend (the numerator) to begin to fill in the grid - we know that 27x^3 must be in the top left. This in turn tells us that the first column entry must be 9x^2 (so that the row and column multiply to 27x^3). In step (3) we use this to fill in all of the first column, multiplying 9x^2 by the terms of the row entries.



In step (3) we now have a quadratic term -18x^2. But we know from looking at the dividend (numerator) that in the final answer we actually want 9x^2. Consequently, the other entry on the quadratic diagonal must be 27x^2, so that the whole diagonal sums to 9x^2 .  Filling this in for step (4) tells us what all the entries in the second column should be (step 5). Now that we have a linear entry -18x, we know that we need to add in a 15x so that the overall sum gives a -3x (step 6).



Having a 15x tells us that the top entry must be 5 (the product of 5 and 3x gives us 15x). Filling this in in step 7 allows us to complete the table, and we see that our final constant entry is -10, as hoped for. Now that the grid has been filled in and it matches the dividend, we can read the answer off the top - the factor that we have uncovered is the quotient we were hoping to calculate.

This method is actually easier than it seems at first, and when all steps are carried out on the same grid, is quite compact.

Here is another example for you to try it out on.




In these two examples, the division worked well - there was no remainder. In the case where we are dividing f/g and g is not a factor of f, and the degree of g is less than the degree of f, there is polynomial remainder whose degree is strictly less than that of g. So, for example, when g is a linear function (degree 1), f/g can have a constant remainder (degree 0).

In this case we proceed as above, attempting to fill in the grid with the numerator (dividend). However, if when we are done the grid does not match the numerator, we have a remainder. The remainder is the additional amount that we have to add to the grid in order to arrive at the numerator.

Consider a division question almost identical to the first one that we looked at, except here we change the numerator slightly so that it doesn't factor well.



Following the same steps as before, we end up with a grid sum that does not match our desired answer: we have -10 instead of -9 for the final constant term. This tells us that we have a remainder of +1, that we choose to write next to the grid. In our final answer, the remainder tells us the "remaining fractional part" that we have to add at the end.


Update: See this post on generic rectangles.
Another Update: See this post for more examples.
Again with another update: See this post on what happens when you do "backwards" division
Again again with another update: See this post about the division example generator.