2009 « The Math Less Traveled

Archive for 2009

MangaHigh.com

Monday, December 28th, 2009

I recently received an email suggesting that I check out the website MangaHigh.com, which has interactive math-based games for elementary through high school students. Now, I am generally pretty skeptical of such things. For one, they are usually of relatively poor quality. If you really want students to be interested in a computer game, you have to compete with game companies which pour millions of dollars into detail, graphics, and gameplay—and kids can tell the difference! For another thing, trying to make math “interesting” and “relevant” by spicing it up with interactive games can backfire: why would you need to do that unless it is actually boring and irrelevant? It is like trying to get your children to eat asparagus by hiding it inside their hamburgers. Kids are not fooled by this. (In fact, asparagus is one of the most delicious vegetables I know, but only if it is fresh and cooked right; if not fresh or overcooked, it is disgusting. I will let you make the appropriate metaphorical inferences.)

Nevertheless, I was intrigued, especially since my correspondent claimed that this website was endorsed by the eminent mathematician and educator Marcus du Sautoy. So I visited the site and tried playing a few games… and was pleasantly surprised! The games are fairly high-quality and humorous (I actually spent twenty minutes or so playing the first game I tried, even though it was rather easy for me), and the site promises to track points and accomplishments for students who register (a definite requirement if you want to get students hooked on the games).

On the flip side, the commercial status of the site isn’t completely clear—you can play all the games for free but it claims this is “for a limited time”, so I’m not sure what happens after the limited time is up. The site also appears to have very little to do with Manga, so the title is a bit odd. But these are minor considerations at the moment.

I’m still not sold on the idea of interactive games for teaching math—but if you’re looking for such things, MangaHigh.com seems like one of the best sites currently out there.

Tags: education, games, interactive
Posted in games, links, teaching | 1 Comment »

Irrationality of pi: derivatives of f

Sunday, December 20th, 2009

Irrationality of pi

Irrationality of pi
Irrationality of pi: the unpossible function
Irrationality of pi: derivatives of f
Irrationality of pi: curiouser and curiouser
Irrationality of pi: the impossible integral
Irrationality of pi: the integral that wasn’t

In my previous post in this series, we defined the function

$\displaystyle f(x) = \frac{x^n(a - bx)^n}{n!}$

and showed that $f(0) = f(\pi) = 0$ . Today we’ll show the surprising fact that, for every positive integer , although $f^{(i)}(0)$ and $f^{(i)}(\pi)$ are not necessarily zero, they are always integers. (The notation $f^{(i)}$ means the th derivative of ; that is, take the derivative of , then the derivative of that, then the derivative of that, … times.) Put more succinctly: every derivative of takes on integer values at x = 0 and $x = \pi$ .

Why might this be surprising? It’s surprising because of the in the denominator of . For example, consider the function (which I just made up):

$g(x) = \frac{x^3 + 5x}{6}.$

It’s easy to see that g(0) = 0 . But let’s take the derivative: $g'(x) = \frac{3x^2 + 5}{6},$ so g'(0) = 5/6 , which is clearly not an integer. For the derivatives of to always give an integer at x = 0 (let alone at $x = \pi$ ) there must be some fancy canceling going on!

For now we will consider only $f^{(i)}(0)$ (we’ll come back to $f^{(i)}(\pi)$ later). Of course, substituting for causes every term containing to disappear, so $f^{(i)}(0)$ is just the constant term of $f^{(i)}(x)$ . Hence, we must show that the constant term of $f^{(i)}(x)$ is always an integer.

Consider the numerator of f(x) , that is,

Note that (a - bx)^n , when expanded out, is a polynomial of the form $a^n - \dots + (-b)^n x^n$ , where the ellipsis contains a bunch of terms with integer coefficients and powers of between 1 and n-1 . (In fact, we could use the Binomial Theorem to compute the precise coefficients—but it really doesn’t matter; all we will care about is that they are integers.) Multiplying by x^n , we see that

$n!f(x) = a^n x^n - \dots + (-b)^n x^{2n}$

so n!f(x) is a polynomial with terms of degree through , and hence so is f(x) , since dividing by changes the coefficients but not the exponents. (Note that f(x) has no constant term, so f(0) = 0 —but we already knew that.)

Recall that the derivative of x^k is $k x^{k-1}$ , so taking the derivative of a polynomial reduces each of the exponents by one. So the first derivative of f(x) is a polynomial with terms of degree n-1 through 2n - 1 (and hence a constant term of zero); the second derivative has terms of degree n-2 through 2n - 2 (still no constant term); and so on. We can see that none of the first n-1 derivatives of f(x) will have a constant term, so $f^{(i)}(0) = 0$ (which is certainly an integer) for i < n . What about the th derivative and higher? This is where the fancy canceling comes in!

As we noted above, when expanded out f(x) is a sum of a bunch of terms of the form

$\displaystyle \frac{c_i x^{n+i}}{n!}$

where $0 \leq i \leq n$ and c_i is some integer. When we take the derivative, this term will turn into $(n+i) c_i x^{n+i-1}/n!$ ; if we take the derivative again, it will become $(n+i)(n+i-1) c_i x^{n+i-2}/n!$ ; another derivative gives us $(n+i)(n+i-1)(n+i-2) c_i x^{n+i-3}/n!$ , and so on. Do you see what is happening? After taking the derivative exactly n+i times, we will end up with the constant term

$\displaystyle \frac{(n+i)! c_i}{n!}$

and here’s our fancy canceling: (n+i)! is clearly divisible by , so this is some integer times c_i , which is also an integer. Voila! Said a different way, and more succinctly: since each term of f(x) has degree at least , by the time we have taken the derivative enough times for it to yield a constant term, the will be canceled from the denominator, since we will have taken the derivative at least at each power of from down to .

Finally, if we take the derivative of more than times, we get , so no problems there.

Great, so $f^{(i)}(0)$ is always an integer. But what about $f^{(i)}(\pi)$ ? Well, remember, last time we showed that $f(\pi - x) = f(x)$ . If we take the derivative of both sides with respect to (being careful to use the chain rule on the left side, noting that the derivative of $\pi - x$ with respect to is ), we get

$\begin{align*}\frac{d}{dx}f(\pi - x) &= \frac{d}{dx} f(x) \\ -f'(\pi - x) &= f'(x) \end{align*}$

We can repeat this process to find that $f^{(2)}(\pi - x) = f^{(2)}(x)$ (the two negatives cancel on the left side), $-f^{(3)}(\pi - x) = f^{(3)}(x)$ , and so on. But the extra negative sign for odd derivatives doesn’t really matter: in either case, $f^{(i)}(\pi) = \pm f^{(i)}(\pi - \pi) = \pm f^{(i)}(0)$ , which is an integer.

Getting closer! Next time, we will define another special function F(x) in terms of f(x) and its derivatives; this function F(x) will help us compute $\int_0^\pi f(x) \sin (x) dx$ —which (if you recall the punchline) will turn out to be an integer strictly between and (which is impossible).

« Previous in series | Next in series »

Tags: derivatives, irrationality, Ivan Niven, pi, proof
Posted in calculus, famous numbers, proof | 10 Comments »

Math Teachers at Play #21

Saturday, December 19th, 2009

Math Teachers at Play #21 is up at Math Mama Writes…, and it includes this cute puzzle, which Sue apparently made up herself:

The Numberland News runs personal ads. 21 was looking for a new friend and put an ad in.

Two-digit, semi-prime, triangular, Fibonacci number seeks same. I’m a binary palindrome, what about you?

Will 21 find a friend?

A semi-prime is a number with exactly two prime factors, like 6. See this post for a definition of triangular number, this post for some hints on how to figure out a general formula for computing triangular numbers, and this one for the solution. Fibonacci numbers are discussed here. Finally, a palindrome is a number (or word, or phrase) which is the same forwards and backwards; a binary palindrome is a number which is a palindrome when expressed in base two.

Tags: binary, fibonacci, MTaP, palindrome, puzzle, semi-prime, triangular
Posted in fibonacci, links, number theory, puzzles | 13 Comments »

The haybaler

Wednesday, December 16th, 2009

At Penn Alexander’s math club yesterday, the students worked on a fun puzzle that I’d never seen before. It goes like this:

You have five bales of hay.

For some reason, instead of being weighed individually, they were weighed in all possible combinations of two. The weights of each of these combinations were written down and arranged in numerical order, without keeping track of which weight matched which pair of bales. The weights, in kilograms, were 80, 82, 83, 84, 85, 86, 87, 88, 90, and 91.

How much does each bale weigh? Is there a solution? Are there multiple possible solutions?

Unfortunately, the problem seemed a little beyond them (or at least, they thought it was beyond them, so they quickly lost interest) but this seems like a great problem to use in middle school or high school math classes. In middle school, keep them talking and focus on the methods they employ to try to solve it. In high school, perhaps once they solve it you could get them to try generalizing the problem (to other sets of weights, more than five bales, etc.).

Tags: bales, hay, weights
Posted in arithmetic, challenges, logic, puzzles, teaching | 10 Comments »

The Christmas Price Index

Monday, December 14th, 2009

I’ve written before about the mathematics of the traditional song “The Twelve Days of Christmas”. For a different angle, check out PNC Bank’s “Christmas Price Index”: apparently, every year they compute the total cost of all the gifts in the song as a whimsical measurement of the economy. This year they have a really cute video along with games and activities that can be used by educators—give it a look! This year, a True Love would have to shell out $87,402.81 for all 364 gifts (up only 1.8% from last year)!

(Note, when I visit the site I get a warning about a bad security certificate—but after poking around a bit nothing fishy appears to be going on, it should be OK to tell your browser to make an exception if you get a similar warning.)

Tags: Christmas, gifts, index, PNC Bank, price
Posted in games, links, video | 1 Comment »

Irrationality of pi: the unpossible function

Saturday, December 12th, 2009

Irrationality of pi

Irrationality of pi
Irrationality of pi: the unpossible function
Irrationality of pi: derivatives of f
Irrationality of pi: curiouser and curiouser
Irrationality of pi: the impossible integral
Irrationality of pi: the integral that wasn’t

Recall from my last post what we are trying to accomplish: by assuming that $\pi$ is a rational number, we are going to define an unpossible function! So, without further ado:

Suppose $\pi = \frac{a}{b}$ , where and are positive integers. Define the function like this:

$\displaystyle f(x) = \frac{x^n(a - bx)^n}{n!}.$

(In case you’ve forgotten, , pronounced “n factorial,” is the product of all the numbers from 1 to .) “OK… but… what is ?” I hear you ask. Good question. The short answer is, it doesn’t matter: can be any positive integer. We will show a bunch of things that are true about no matter what is. Later, we will see that we get a contradiction only for values of which are “big enough.” But that’s OK; since everything we prove up to that point will be true no matter what is, we can pick a value of which is as big as we like.

Let’s explore some properties of f(x) . First, it’s easy to see that $f(0) = \frac{0^n a^n}{n!} = 0$ . It’s not too hard to see that $f(\pi) = 0$ as well (remembering that $\pi = a/b$ , of course, which means that $a-b\pi = a - a = 0$ ):

$\begin{align*}f(\pi) &= \frac{\pi^n (a - b\pi)^n}{n!} \\ &= \frac{\pi^n 0^n}{n!} = 0.\end{align*}$

So f(x) has zeros at x = 0 and $x = \pi$ . But more is true: in fact, f(x) is symmetric (a mirror reflection of itself) around the line $x = \pi/2$ . That is,

$f(x) = f(\pi - x) = f(a/b - x).$

Let’s prove this:

$\begin{align*}f(a/b - x) &= \frac{(a/b - x)^n(a - b(a/b - x))^n}{n!} \\ &= \frac{(a/b - x)^n(a - a + bx)^n}{n!} \\ &= \frac{(a/b - x)^n b^n x^n}{n!} \\ &= \frac{(a - bx)^n x^n}{n!} = f(x). \end{align*}$

“I don’t see what’s so unpossible about so far,” you say? Patience! (Of course, it isn’t really itself which is the problem; the problem is our insistence that is actually defined in terms of the “numerator” and “denominator” of $\pi$ …)

Next time, we’ll see that the derivatives of also have some special properties.

« Previous in series | Next in series »

Tags: irrational, Ivan Niven, pi, proof, symmetric
Posted in calculus, famous numbers, proof | 6 Comments »

Irrationality of pi

Monday, December 7th, 2009

Irrationality of pi

Everyone knows that $\pi$ —the ratio of any circle’s diameter to its circumference—is irrational, that is, cannot be written as a fraction a/b . This also means that $\pi$ ’s decimal expansion goes on forever and never repeats …but have you ever seen a proof of this fact, or did you just take it on faith?

The irrationality of $\pi$ was first proved (according to modern standards of rigor) in 1768 by Lambert, but his proof was rather complicated. A more elementary proof, using only basic calculus, was given in 1947 by Ivan Niven. You can read his original paper here, but it’s rather terse! Just as I did for Calkin and Wilf’s paper, Recounting the Rationals, I plan to write a series of posts explaining Niven’s proof in a bit more detail, with some accompanying intuition. I’ll assume a basic knowledge of calculus; if you don’t know calculus, just hang tight for a few posts!

Here’s the basic outline of the proof. We begin by supposing that $\pi$ is rational: in particular, suppose $\pi = a/b$ for some integers and . We’ll then use these values of and to define a special function f(x) , about which we will show the following:

$\int_0^\pi f(x) \sin(x) dx$ is an integer, AND

$0 < \int_0^\pi f(x) \sin(x) dx < 1$ .

But this is absurd! There are no integers greater than zero and less than one. The inescapable conclusion will be that our initial assumption—that $\pi = a/b$ —was false.

In my next post, we’ll define the special function f(x) and begin exploring some of its properties.

| Next in series »

Tags: irrational, Ivan Niven, pi, proof
Posted in calculus, famous numbers, proof | 13 Comments »

Carnival of Mathematics this Friday!

Tuesday, December 1st, 2009

The next Carnival of Mathematics goes up this Friday at $\Sigma$ idiot’s blog—get your submissions in!

Tags: Carnival of Mathematics
Posted in links, people | No Comments »

Who Am I?

Sunday, November 29th, 2009

An excellent puzzle from JD2718:

There are five true and five false statements about the secret number. Each pair of statements contains one true and one false statement. Find the trues, find the falses, and find the number.

1a. I have 2 digits
1b. I am even

2a. I contain a “7”
2b. I am prime

3a. I am the product of two consecutive odd integers
3b. I am one more than a perfect square

4a. I am divisible by 11
4b. I am one more than a perfect cube

5a. I am a perfect square
5b. I have 3 digits

Please don’t post the solution in a comment, so as not to spoil it for others. But feel free to leave a comment if you need a hint, or to email me if you think you have solved it and want to check if you are correct. (Actually, it’s easy to check yourself: just make sure that each of each pair of statements, exactly one is true and one is false!)

Tags: number, puzzle, secret
Posted in challenges, logic, number theory, puzzles, teaching | 13 Comments »

m-bracelets code

Friday, November 27th, 2009

By popular demand, here is the Haskell code I used to generate the images in my previous post. This post is literate Haskell; you can simply copy and paste this entire post into a file called BraceletGraph.lhs (or anything you like, as long as it ends with .lhs) and run it yourself. Also, I used Robert Greayer’s lovely BlogLiterately tool to write and format this post.

First, a few imports: we use Martin Erwig’s fgl functional graph library for constructing graphcs, and Ivan Miljenovic’s bindings to the Graphviz library in order to output graph descriptions.

> import Data.Graph.Inductive
> import Data.GraphViz
>
> import System.Environment

A "link" in a number bracelet is a pair of digits; knowing a pair of digits completely determines the remainder of the bracelet.

> type Link = (Int,Int)

The next link in a bracelet is obtained by adding and taking the result mod m.

> nextLink :: Int -> Link -> Link
> nextLink m (a, b) = (b, ((a + b) `mod` m))

We construct the list of all possible links.

> braceletLinks m = [ (a,b) | a <- [0..m-1], b <- [0..m-1] ]

We now also construct the list of all the "edges" from one link to the next.

> braceletEdges m = [ (l, nextLink m l) | l <- braceletLinks m ]

We will also need a function to convert a link into a unique numeric representation, since the graph library assumes that vertices are named by integers.

> linkToLabel m (a, b) = a*m + b

The rest of the code simply interfaces with the fgl and graphviz libraries to create a graph and output it as a .dot file. This was the hardest part of the code to write—but it was hard only in the sense that it took me a while to look through the documentation for the fgl and graphviz libraries to figure out how to do what I wanted.

> braceletGraph :: Int -> Gr Link ()
> braceletGraph m = mkGraph (map mkNode (braceletLinks m))
>                           (map mkEdge (braceletEdges m))
>   where mkNode l       = (linkToLabel m l, l)
>         mkEdge (l1,l2) = (linkToLabel m l1, linkToLabel m l2, ())
>
> dotGraph m = graphToDot True (braceletGraph m)
>                              []
>                              linkAttrs
>                              (const [])
>
> linkAttrs (_, (a,b)) =
>   [ Label . StrLabel . show $ a
>   , Shape Circle
>   , Color [colors !! a]
>   , FillColor $ colors !! a
>   , Style [SItem Filled []]
>   ]
>
> colors = cycle $ map ColorName [ "lightblue"
>                                , "red"
>                                , "orange"
>                                , "yellow"
>                                , "green"
>                                , "blue"
>                                , "purple"
>                                , "brown"
>                                , "pink"
>                                , "grey"
>                                ]
>
> main = do
>   (m:_) <- fmap (fmap read) getArgs
>   putStr . printDotGraph $ dotGraph m

We can run this program by passing it the value of m we want to use, and it outputs a file in .dot format, which we can turn into an image using one of graphiz’s graph layout tools, like neato or circo. For example:

$ ghc --make BraceletGraph.lhs
$ ./BraceletGraph 9 > bracelets9.dot
$ neato -Tpng bracelets9.dot > bracelets9.png

Tags: bracelets, graph, graphviz, Haskell, literate
Posted in arithmetic, computation, links, pictures, programming | 2 Comments »

The Math Less Traveled

Archive for 2009

MangaHigh.com

Irrationality of pi: derivatives of f

Irrationality of pi

Math Teachers at Play #21

The haybaler

The Christmas Price Index

Irrationality of pi: the unpossible function

Irrationality of pi

Irrationality of pi

Irrationality of pi

Carnival of Mathematics this Friday!

Who Am I?

m-bracelets code

Pages

Archives

Categories