Penn Alexander math club: map coloring

February 23rd, 2010

Today in math club I had the students explore map coloring. I tried to leave it as open-ended as possible to start—I just said that we were going to draw maps with countries, and try to give each country a color, so that no two adjacent countries have the same color. I was careful not to specify what a “country” is, or what it means for two countries to be “next to” each other!

Pretty much on their own, they figured out how to draw a map with four countries all touching each other, which therefore required four colors. When I challenged them to draw a map with five countries all touching each other, they came up with maps involving countries touching at a corner, and with “satellite” disconnected regions that had to be given the same color as the “mother country”. They also figured out that if we allow these things, we can draw maps requiring an arbitrary number of colors, and conjectured that without these things we can’t have five countries all touching each other. I then told them about the four-color theorem and we had fun trying to four-color a map of North America (including the US states).

Then I showed them how to interpret maps as graphs, why maps correspond to planar graphs, and how to turn the map-coloring question into a graph-coloring question. I showed them the complete graph on 5 vertices and how it would correspond to having five countries all touching each other. Then for fun I posed the three utilities problem, which after playing with for a while, they correctly guessed could not be solved within the given constraints. One student did come up with an ingenious solution involving a pair of “teleporters”, which (although I didn’t point this out to them at the time) corresponds to the fact that K_{3,3} can be embedded on a torus! I then showed them how to interpret this also as a statement about graphs (specifically, the non-planarity of K_{3,3}), and then told them Kuratowski’s Theorem (which I still find rather amazing and magical).

To finish up, I had them explore the idea of dividing up a continent into countries only by drawing straight lines that went completely from one side of the continent to the other. They correctly figured out that such maps would always be two-colorable. We looked at some examples and their corresponding graphs (which, they noted, always consist of a bunch of quadrilaterals). When I showed them the inductive proof of two-colorability, one of the students noted that the proof generalized to non-straight boundaries, as long as the boundaries are drawn as continuous lines with both endpoints on the “coastline” of the continent (which I hadn’t realized)!

All in all, this was probably our most fun and engaging meeting yet! Now that the Mathcounts competition is over, I think we’ll have a lot of fun doing some more open-ended, exploratory things like this rather than practicing with problem sets.

Irrationality of pi: the integral that wasn’t

February 11th, 2010

And now for the punchline! Today we’ll show that, for large enough values of n,


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

completing the proof of the irrationality of \pi.

First, let’s show that f(x) \sin(x) is positive when 0 < x < \pi. We know that \sin(x) is positive for 0 < x < \pi. But I claim that f(x) is too. Remember that


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

n! and x^n are clearly positive when x is positive; and a - bx is also positive when x < \pi = a/b. From here we simply note that if a function is positive over an entire interval, the integral of the function over that interval will be positive as well.

For the second part, note first that for 0 < x < \pi,


\displaystyle f(x) \sin(x) < \frac{\pi^n a^n}{n!}.

Why is this? Well, clearly x^n < \pi^n (since x < \pi), and also a - bx < a (since x > 0) and hence (a - bx)^n < a^n, so we conclude that


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

This doesn’t yet include the \sin(x), but notice that multiplying by \sin(x) can only make things smaller, since \sin(x) is at most 1. Now, here’s the slightly sneaky part: I claim that we can make \frac{\pi^n a^n}{n!} as small as we want by making n big enough. Why is this? Notice that we can rewrite it as


\displaystyle \frac{\pi^n a^n}{n!} = \frac{\pi a}{1} \cdot \frac{\pi a}{2} \cdot \frac{\pi a}{3} \dots \frac{\pi a}{n}.

Now, a—the “denominator” of \pi—might be very large. It might have fourteen million zillion digits. But no matter how big a is, there will of course be an integer z which is bigger than \pi a, so \frac{\pi a}{z} < 1. And then \frac{\pi a}{z + 1} < 1, and \frac{\pi a}{z + 2} < 1, and so on... of course, multiplying by something less than one makes things smaller. And it might take a really really long time to cancel out the enormous product \frac{\pi a}{1} \cdot \frac{\pi a}{2} \dots \frac{\pi a}{z}, but if we just wait patiently it will get smaller and smaller... and eventually there will come some n for which


\displaystyle \frac{\pi a}{1} \cdot \frac{\pi a}{2} \dots \frac{\pi a}{z} \cdot \frac{\pi a}{z + 1} \dots \frac{\pi a}{n} < 1.

Actually, even this isn’t quite small enough: we want the integral from 0 to \pi of f(x) \sin(x) to be less than 1. But that’s not a problem; to ensure that we can just pick n big enough so that f(x) < 1/\pi (if the graph of f(x) fits inside a \pi by 1/\pi box, then its integral on this interval must be less than the area of the box).

Voila! An integral which is an integer absurdly between 0 and 1, all because we assumed \pi was rational.

The inescapable conclusion, which probably would have driven the ancient Greeks crazy, is that \pi is irrational!

Irrationality of pi: the impossible integral

February 6th, 2010

We’re getting close! Last time, we defined a new function F(x) and showed that F(0) and F(\pi) are both integers, and that F^{\prime\prime}(x) + F(x) = f(x). So, consider the following:

 $ \begin{align*} &\frac{d}{dx} [ F'(x) \sin x - F(x) \cos x ] \\ &= F^{\prime\prime}(x)\sin x + F'(x) \cos x \\ & \qquad - F'(x) \cos x + F(x) \sin x \\ &= F^{\prime\prime}(x) \sin x + F(x) \sin x \\ &= [F^{\prime\prime}(x) + F(x)]\sin x \\ &= f(x) \sin x. \end{align*} $

The first step uses the product rule for differentiation (recalling that \frac{d}{dx}\sin x = \cos x and \frac{d}{dx}\cos x = - \sin x); the last step is what we showed last time. Now we see the point of defining F(x): it’s just so that we have a convenient way to talk about the antiderivative of f(x) \sin x. We could just do everything directly in terms of alternating sums of derivatives of f(x)… but it’s much clearer this way, don’t you agree?

Now that we know the antiderivative of f(x)\sin x, we can use the Fundamental Theorem of Calculus to compute the following integral:

 $ \begin{align*} &\int_0^\pi f(x)\sin x dx \\ &= \left[ F'(x) \sin x - F(x) \cos x \right]_0^\pi \\ &= F'(\pi) \sin \pi - F(\pi) \cos \pi \\ & \qquad - F'(0) \sin 0 + F(0) \cos 0 \\ &= F(\pi) + F(0). \end{align*} $

Note that the value of this integral is an integer, since both F(\pi) and F(0) are integers. But next time we’ll show that it is also strictly between 0 and 1 (for a suitable choice of n), which is clearly nonsense!

Dimensions

February 3rd, 2010

I’ve only watched the trailer so far, but this looks extremely cool! Some beautiful, fascinating videos about math, with lots of extra accompanying material and explanations on the website.







Hat tip to Phil Wadler.

Divisor nim

February 3rd, 2010

Yesterday in math club I had the students play a game which I dimly remember seeing somewhere but forget where. Since I don’t know what it is really called, I’m calling it “divisor nim”. Here’s how it works:

  1. The players pick a positive integer.
  2. The two players work together to write down all the divisors of the chosen integer (being sure to include 1 and the integer itself).
  3. The players now alternate moves as follows: on a player’s turn, she must choose one of the divisors d, and then cross out that divisor as well as all of the other listed numbers which are divisible by d.
  4. On subsequent turns, players may only choose numbers which are not yet crossed out.
  5. Whoever is forced to choose 1 (because it is the only number left) is the loser!

For example, suppose the chosen number is 12. We write down the divisors of 12:

1, 2, 3, 4, 6, 12.

Now suppose the first player chooses 4 (actually, this is a bad move; I’ll let you figure out why); they then cross out 4 and 12, since 12 is divisible by 4. The game now looks like

1, 2, 3,  4 , 6,  12 .

Now it’s the other player’s turn; suppose they pick 3 (this is actually a bad move too…!), so they cross out 3 and 6. Now the game looks like

1, 2,  3 ,  4 ,  6 ,  12 .

The first player now crosses out 2, and the second player is forced to choose 1, so the first player wins.

The kids thought this was a lot of fun and it leads to all kinds of interesting discussions. First, of course, you have to figure out how to write down all the divisors of the starting number (how do you know when you’ve listed them all? what are some systematic strategies for listing the divisors?). Then you can talk about strategies for playing the game. I might talk about some of these things in some future posts. For now I will just note that this actually has some deep connections to the theory of posets (we are basically just using each integer as an abbreviation for its poset of divisors). Although I’ve played around with it a bit I don’t yet know of a general strategy — although any particular starting integer necessarily gives a winning strategy for ONE of the two players, and it’s not too hard to figure it out by working backwards. More on this later, I suppose.

In the meantime, have fun playing!

Battlestations!

February 1st, 2010

The world’s LARGEST FRACTAL DORITO!

Irrationality of pi: curiouser and curiouser

January 30th, 2010

I’ve been remiss in posting here lately, which I will attribute to Christmas and New Year travelling and general craziness, and then starting a new semester craziness… but things have settled down a bit, so here we go again!

Since it’s been a while since my last post in this series, here’s a quick recap: I’m presenting a proof by Ivan Niven that \pi is irrational, that is, that it cannot be represented as the ratio of two integers (and hence its decimal expansion goes on forever without repeating). My first post just gave some background and an outline of the general argument. In my second post, we began by assuming that \pi is rational, and defined the function


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

(really, a family of functions, one for each value of n) where a and b are the “numerator” and “denominator” of \pi. We then showed that f(0) = f(\pi) = 0, and in fact that f(x) is symmetric, with f(\pi - x) = f(x). In my third post, we showed that all the derivatives of f(x) take on integer values when evaluated at both 0 and \pi. We’re about halfway there! Today we’ll continue by defining a new function F(x) in terms of f(x), and show some of its properties. Recall too our overall plan: we’re going to wind up with an integral which is strictly greater than 0, strictly less than 1, and also an integer! Since this is clearly nonsense (there are no integers between 0 and 1) we will conclude that our initial assumption—that \pi is rational—was bogus, and that \pi must be irrational after all.

So without further ado, here’s our new function F(x). Actually, this too is technically a family of functions F_n(x), one for each n; but again, everything we prove about it will be true no matter what n is.


\displaystyle F(x) = f(x) - f^{(2)}(x) + f^{(4)}(x) - \dots + (-1)^n f^{(2n)}(x).

In words, F(x) is the alternating sum of all the even derivatives of f(x). (I say “all” because, as noted in my last post, any derivative of f(x) higher than 2n is zero.) Using Sigma notation, we can also write this more concisely as


\displaystyle F(x) = \sum_{i = 0}^n (-1)^i f^{(2i)}(x).

There are a few things to note. First, think what happens when we evaluate F(0): since all the derivatives of f(x) take on integer values at 0, and F(x) is just a sum of a bunch of derivatives of f(x), F(0) must be an integer too. Of course, the same thing goes for F(\pi).

Next, consider


F^{\prime\prime}(x) + F(x).

Since the derivative of a sum is the sum of the derivatives, we can compute F^{\prime\prime}(x) as


F^{\prime\prime}(x) = f^{(2)}(x) - f^{(4)}(x) + \dots + (-1)^{n-1}f^{(2n)}(x).

That is, f(x) turns into f^{(2)}(x), -f^{(2)}(x) turns into -f^{(4)}(x), and so on. “But wait a minute,” you say. “Shouldn’t the (-1)^n f^{(2n)}(x) at the end of F(x) turn into (-1)^n f^{(2n+2)}(x) in F^{\prime\prime}(x)?” In fact, it does—but as noted before, f^{(2n+2)}(x) is zero, so that term just goes away. Now we note that every term of F(x) has a corresponding term in F^{\prime\prime}(x) of the opposite sign, except f(x), which has no corresponding term. So when we add F(x) and F^{\prime\prime}(x), everything cancels except f(x):


F^{\prime\prime}(x) + F(x) = f(x).

Astute readers will note a funny resemblance between the definition of F(x) and the Taylor series for \cos(x)… and indeed, next time we’ll start making some connections with our old trigonometric friends, \sin and \cos.

Perfect age

January 10th, 2010

Today is my birthday! This is the second and (barring any miraculous advances in medical science) final time that my age will be a perfect number. Unfortunately, the first time my age was a perfect number, I didn’t know what a perfect number was.

Book review: Riot at the Calc Exam and Other Mathematically Bent Stories

January 8th, 2010

You’ve heard the story of Rumpled Stiltsken, right? You know, the one where the topologist’s daughter is locked in the grad student lounge and forced to turn coffee into theorems by morning? …what’s that, you say you haven’t heard that one? Funny, I thought everyone knew that story. Well, it’s a fascinating and sobering tale full of insight into life and the nature of… oops, wait, those were my notes for The Kite Runner. Rumped Stiltsken is… well, just read it, OK?

Colin Adams entertains us with this and many other humorously mathematical (mathematically humorous?) stories in his new book, Riot at the Calc Exam and Other Mathematically Bent Stories. Tips on how to avoid RERI (Repetitive Eye Roll Injury), advice from a mathematical ethicist, stories about everyone’s favorite Principal Investigator, Dirk Mangum, P. I., a transcript from the hit radio show Math Talk with Plug and Chug… the list goes on. Some are funnier than others, of course (by the end, the conceit of anthromorphizing/metaphorizing mathematical theorems and the process or proving them had gotten particularly old), but on balance my Funny-o-Meter was definitely pointing somwhere between “amusing” and “hilarious”. This book would make a great gift for that special person in your life who likes to read funny stories about math while they are in the bathroom, or for anyone who likes reading funny stories about math in general, or anyone who likes funny stories, or who likes math. This book would not make a good gift for grumpy people who hate math. Don’t say I didn’t warn you.

Full disclosure: the AMS kindly sent me a free review copy of this book. Also, Colin Adams was actually one of my professors in college, which you might think would make me somewhat biased, which is probably true, but it also means that I happen to know that he really is quite funny, and also that he is the Fastest Draw(er of 3D surfaces with colored chalk) in the West(ern Massachusetts). Also also, this morning for breakfast I ate a bowl of shredded wheat cereal.

MangaHigh.com

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.