The subject of this post is an essay commonly referred to as “Lockhart’s Lament” (actually “A Mathematician’s Lament”) about mathematics education, and some of my observations and opinions relating those ideas to homeschooling and volunteering.

Before going any further, if you have not read the essay, or the articles about the essay in Keith Devlin’s MAA column, then stop reading here, and start reading there.  There are better words there, including an interesting follow-up article with a response from Lockhart to reader comments.  Even if you do not agree with all of his ideas, “Lockhart’s Lament” is a must read for anyone with a stake in mathematics education, whether you are a teacher, student, parent, or even administrator (!).

Lockhart’s essay rings very true to me.  My focus here is on two ideas in particular.  First, as I have said before, mathematics is not a vocational skill.  It seems fashionable today to try to motivate students with applications of mathematics that they will be able to use in the “real world.”  Compute the tax and tip on a restaurant bill; compute the interest earned on a savings account.  Such applications typically end up consisting of problems that, in the real world, people do not solve with pencil and paper.  They solve them with calculators, lookup tables, handbooks, or web sites.

It is this requirement of application that bothers me.  Who cares if there is an application?  I will admit that at times an application might be useful as a means of making a problem less abstract and more concrete, but why can’t the application be fun?  What kid cares about the tax on a restaurant bill?  As Lockhart suggests:

Play games! Teach them Chess and Go, Hex and Backgammon, Sprouts and Nim, whatever. Make up a game. Do puzzles. Expose them to situations where deductive reasoning is necessary. Don’t worry about notation and technique, help them to become active and creative mathematical thinkers.

How can we possibly get away with something like this?  This sounds like a mathematical environment where there is no fixed curriculum, there is no pre-planned road ahead, but instead the students have at least some influence on where the road leads, with that influence stemming from the directions in which their interest takes them.

This brings me to my second and more important point: maybe we can’t have such an environment… at least in a school system.  As one reader responded, “educational systems almost inevitably entail measuring results, an activity from which Lockhart clearly recoils.”  I completely agree here… because it is that anticipation of measurement that causes the problem.  When it is known that a school’s effectiveness will be evaluated based on student performance on specific tests of specific “skills,” the curricula naturally adapt to teach to the test, and student interest no longer has any influence on the direction of study.  It is an inadequate metaphor, but mathematics education is rather quantum mechanical; the very act of measuring disturbs that which is being measured.

(It is not just my own observation that standardized tests measure the school much more than they measure the student.  I was amused to find that, at least here in Maryland, the description of the High School Assessment program seems to acknowledge this.)

All of this suggests to me that environments with more freedom of direction have a lot of potential for engaging students.  It is a lot easier to teach when no one is watching.  Homeschooling seems like an attractive example of this… but one of which I am suspicious for several reasons.  Homeschooling is attractive because of its simple efficiency.  Whether using a fixed curricula or not, the student:teacher ratio is so much lower that there is little to hold the student back.  But accuracy is another matter.  The parent/teacher has to be able to react knowledgeably and creatively to the student’s evolving interest; as Lockhart points out:

Teaching is a messy human relationship; it does not require a method. Or rather I should say, if you need a method you’re probably not a very good teacher. If you don’t have enough of a feeling for your subject to be able to talk about it in your own voice, in a natural and spontaneous way, how well could you understand it?

How many parents are equipped to think on their mathematical feet in this way?  While we’re at it, how many school teachers are equipped to do so?  This is where I think there is great potential for something like a compromise: mathematical professionals volunteering, working with students in public schools in an independent study environment.  It works— and I speak from experience, both as a student and as a wannabe teacher.  Mathematics can indeed be beautiful and useful, pure and applied, rigorous and recreational, all at the same time.

Last week I attended a presentation where the speaker asked everyone in the audience to take off their shoes, and to put them together at the front of the room.  The speaker then asked each person to select and pick up a pair of shoes that was not his/her own.

Strange presentation, huh?  There was more to it than that; I will leave it to the reader to imagine where things could possibly have gone from there.  But just that initial selection process presented an interesting problem.  How easy– or difficult– is it for a group of people to redistribute their shoes so that no one has his or her own pair?

This problem has received plenty of attention, so much so that it is commonly known by several different names, from the “hat-check problem” to “le probleme des recontres.”  There are some very cool mathematics involved… but the subject of this post is a variant that I think is more realistic, and consequently less well-behaved.

I will re-phrase the problem in the context of the common “Secret Santa” holiday gift exchange.  Suppose that a group of people (e.g., your family or co-workers) want to exchange gifts, with each person buying a gift for one other person in the group.  The usual approach is to write each person’s name on a slip of paper, put all of the slips into a hat, and have each person in turn take a slip from the hat.  If a person draws a slip with his own name on it, he returns the slip to the hat and selects another.  Each person then buys a gift for the person named on the drawn slip.

The resulting assignment mapping each person in the group to his or her gift recipient is a derangement, or permutation of persons in the group with no fixed points.  The process of drawing names from the hat is effectively a means of generating a random derangement.

There are two interesting observations about this process.  First, it can break: it is possible for the last person to draw to find that the only remaining slip in the hat has his own name on it.  What happens then?  Earlier in the process, drawing your own name is remedied by simply returning the slip and drawing another.  But for the last person there is no other slip to draw.

It is a nice probability puzzle to determine how frequently this situation occurs.  I do not yet know the answer as a function of the group size , other than for some specific small .  Let me know if you find a solution.  [Edit: Over a year later, there is a description of the solution to this problem here.]

The second observation is that the process is not as random as you might think.  Even if we discount the “end of the line” failure described above, the resulting distribution of derangements that are generated is nowhere near uniform.  That is, suppose that if the last person gets stuck with his own name, we simply return all of the slips to the hat and start over, effectively conditioning the resulting permutation on the failure not occurring.  We can consider the resulting probability distribution of derangements that are generated… and we would like that distribution to be uniform, so that each assignment is equally likely.

Some initial experiments suggest that the most extreme deviations occur where you might expect, namely for the last person to draw a slip.  For example, the last person in line is least likely to end up buying a gift for the first person in line, and is most likely to end up buying for the person next to last in line.

What I did not expect was the extent of the difference; the ratio of those two probabilities is nearly two to one (for , the largest group that I looked at, the ratio is approximately 1.94869)!

We can draw a couple of conclusions.  First, we can fix these problems very simply with a more extreme rejection algorithm: everyone draws a slip, and after everyone has drawn, if anyone has his or her own name, then return all of the slips to the hat and start over.  This guarantees uniformity, and the usual hat-check problem solution now applies, so that we can expect to have to re-draw only about times.

Of course, the second conclusion is that if you are Charlie Brown in love with the little red-haired girl, and you want to be her Secret Santa, then the drawing order that maximizes your chances is with you and her at the end of the line, with you drawing last.  Good luck.

Someone at work this past week asked me about the problem of computing the probability that, in a group of people, some pair of persons share the same birthday.  I am not sure what prompted the question, despite the interesting coincidence that in fact he and I share the same birthday.

The problem is a commonly used example of the failure of our intuition when dealing with probabilities in general and probabilities of “coincidences” in particular.  A survey of university students asked for an estimate of the number of people required for the probability of a shared birthday to exceed 1/2 (see here).  The median response was 385 people.  Think about that– more than half of those surveyed guessed a number of people that is guaranteed to yield a shared birthday.

So what is the correct answer?  I think this problem makes for a great experiment for students, since it can be approached in several ways.  First, the mathematics: the desired probability is 1 minus the probability that all birthdays are distinct.  Assuming all birthdays are equally likely (we’ll address this assumption shortly), we have

Next, the programming: students can write a function to compute , which requires both iteration and some thought about order of operations.  It will not do to compute the numerator and denominator explicitly and then divide, at least in most languages that lack arbitrary-precision arithmetic.

A plot showing versus , and thus the answer to the problem, can be seen here.  (<soapbox> I find it interesting and amusing when I hear comments about Wikipedia not being a useful source of information.  Such comments seem to be based on content that is almost always political or religious.  What does one expect in those cases?  That is simply not the type of content for which the “anyone can edit” approach is useful.  Particularly for technical information, I think Wikipedia contains a lot of useful starting points… that still require a brain in the head of the viewer to verify or extend the results found there.</soapbox>)

Finally, the experiments: the answer to the birthday problem may be sufficiently non-intuitive that students may not trust the mathematics.  A classroom of 25-30 students, or better yet, collection of data from multiple classrooms, provides a handy experimental sample to corroborate the analysis.  This is also a good time to come back to the uniformity assumption that all birthdays are equally likely.  Students can do Monte Carlo analysis, writing programs to generate “classrooms” of data, possibly with non-uniform distribution of birthdays… and observe for themselves that such non-uniformity actually increases the likelihood of shared birthdays.

I was motivated to write this post by the Wikipedia article mentioned earlier.  One small section describes a variant of this question that I think is more directly applicable to the cryptographic “birthday attack,” so named for its relation to this problem.  Suppose that a movie theater is offering a free ticket to a new movie to the first person at the box office with the same birthday as someone earlier in line.  Where should you stand in line?  What is the expected position in line to win the free ticket?

This is also a nice problem for students, particularly because its exact solution does not require evaluation of any of the actual probabilities!  In fact, the answer may be obtained from no more than the root of a quadratic.  I won’t spoil it for those wanting to work out the solution, but I will point out that this is a good example, as mentioned above, where Wikipedia gets it wrong (at least at time of this writing).  Unless I misunderstand the statement, the solution does not involve maximizing the difference between probabilities for consecutive positions in line.

As a mathematician, computer scientist, engineer, and wannabe teacher, I found a lot to be pleasantly surprised about in Visual Python, or VPython.  This is a Python module that provides an easy to use API for creating and animating 3D graphics.  I had looked at VPython a couple of years ago, but then tossed it into one of the dustier bins in the back of my mind, mostly because of awkwardness of installation.  But just last week a student suggested that I take a second look… and it is definitely worth a second look.

There are a lot of different environments, languages, libraries, etc., for creating graphics.  So what makes VPython special?  It does a lot of important things right.  First, it is now very easy to install, as easy as Python itself, on at least the Windows and Mac OS X platforms that I have tested (although it also advertises Linux which I have no reason to doubt).  Jumping easily between Windows and Mac is a pretty important requirement for students, with Macs at school and often Windows at home.

Second– and this is the cool part that makes VPython stand out in my opinion– it eliminates the need for the programmer to handle the details of window system management and multi-threading that is always a part of any graphical application.  You do not have to think about decoupling rendering and event handling, things that are a part of the graphics solution space.  Instead, you spend your time thinking about the problem space of the 3D objects and how they move and interact.  When you create a sphere, or plot of a function, or whatever, the window in which to display the graphics is created for you.  When you change the object’s position or add points to the function plot, a separate rendering thread handles the update to the window display for you.

For non-programmers, this may not sound like such a big deal.  But this is an attribute lacking in even the simplest of graphics APIs, including Python’s built-in turtle module.  (Ok, I have used the Allegro game programming library, which uses this approach, but it is not what I would call an easy one-click install, particularly for multiple platforms.)

It is this simplicity of the “Hello World” ease with which you can create non-trivial graphical displays, move objects around, etc., that makes VPython a potentially great resource for educators, including parents working with their children at home.

I say “potentially,” because I have not yet begun working with VPython with my small group of students.  But I plan on it, am excited about it, and hopefully the students will be excited as well.

Recall my recent post about mouse-picking, motivated by a “hidden object” puzzle adventure game that my wife and I played?  We have since moved on to another similar game, Penny Dreadfuls: Sweeney Todd.  We enjoyed this game even more, since it included more challenging puzzles to solve in addition to the hidden object scenes.  (I am still fascinated by how addicting just the hidden object scenes are.)  Those puzzles often have some interesting mathematics hidden inside them.

Before continuing, consider this a possible spoiler warning: this week’s post concerns the final puzzle that you must solve to “capture” Sweeney Todd to finish the game.  I am always looking out for puzzles or problems that might serve as a vignette for students to investigate some cool mathematics, or perhaps to study as a computer programming project.  But you might find this puzzle interesting, too, and want to solve it yourself.  You have been warned.

In the puzzle, you are a detective chasing Sweeney Todd through the streets of London, as in the following picture:

Initial state of the final Sweeney Todd puzzle.

You are the detective in blue, and Sweeney is red.  You and he alternate turns, where a turn consists of moving to an adjacent vertex.  You move first.  You win if both you and Sweeney occupy the same vertex.

After working out a solution, and being pleased by the interesting mathematics involved, I checked out some online walkthroughs of the game that describe how to catch Sweeney.  Interestingly, all of them essentially suggest to “just keep moving towards him and try to back him into a corner.”  This rather vague advice fails to capture a necessary part of the solution, namely how important that diagonal edge in the center of the graph is.  It is not difficult to show that if neither you nor Sweeney traverses that diagonal edge, then Sweeney can evade you indefinitely.

To see this, consider the graph with the diagonal edge removed, and consider the distance (i.e., number of edges on the shortest path) between you and Sweeney, which is initially 4.  The key observation is that after every turn, that distance changes by +1 or -1.  Thus, you can never capture Sweeney on your turn, since your distance from him will always be odd.  And on Sweeney’s turn, if he is ever just a single edge away from you, there is always another edge he can traverse to increase his distance to 2.

It turns out that this problem has been studied quite extensively, and is typically referred to in the literature as “pursuit-evasion,” or “cops and robbers.”  An early paper by Aigner and Fromme (“A Game of Cops and Robbers“) is available online and describes the basic game and its many variants.  I found it interesting that almost all of the papers on the subject, including this one, seem to focus on the so-called passive version of the game, where the robber (Sweeney) has the option to not move on his turn.  In this passive version, Sweeney wins, since if you (the cop) ever traverse the diagonal edge, he can stay put for a turn, maintaining the parity of distance in the grid subgraph.

Another interesting paper that applies here but unfortunately requires a journal subscription is by Neufeld and Nowakowski, “A game of cops and robbers played on products of graphs” (Discrete Mathematics 186 (1998) 253-268).  They generalize the result that the active robber (that must move on each turn) can evade indefinitely on the graph product of any two trees, of which the grid above is a special case, being the product of two paths of length 5.