The Perfect Combinatorics Problem

In this post, I’m going to extol the virtues of my favorite combinatorics problem.  You’ve probably heard it, or some version of it, before:

A pizza parlor offers ten different toppings on their pizza.  How many different types of pizza are possible to make, given that a pizza can have any number of toppings, or no toppings at all?

Just in case you aren’t familiar with this problem and want to work it out for yourself first, I’m putting most of this post after the jump.  First, a shout out: I remember doing this problem with Michigan State Professor Bruce Mitchell, who used to teach Saturday-morning math enrichment classes at my middle school, and whose enthusiasm and humor kept me coming back.  Second, some pizza:

http://www.neatorama.com

You may prefer to pretend you never saw that.

Postgame Analysis: the Towers of Hanoi

I recently gave my juniors the classic Towers of Hanoi puzzle to play with in small groups.  It went something like this:

You have three plates, and plate #1 has a stack of 5 pancakes, in order from the largest one on the bottom to the smallest on top.  The puzzle is to get the stack onto plate #2 using as few moves as possible.

Two rules: (i) you can only move the top pancake on a stack, and (ii) at no time can any larger pancake be on top of a smaller pancake.

They spent a couple minutes getting familiar with the mechanics of it, and then settled into working together, shifting pancakes and keeping a count of their moves.

The Problem That Never Fails

[This post also appears as a guest post over at Sam Shah’s blog.]

This is a post about a problem that never fails.  It’s the problem I used for my sample lesson when interviewing for jobs four years ago.  It’s the one I almost always use on the first day of class, and it’s also what I give to parents on back to school night.  Because… well…it. never. fails.  Seriously.

The perfect, ineffable jewel of a problem to which I refer is the classic Bridges of Konigsberg problem.   Here’s the story, in case you don’t know it:

(image from wikipedia) 

As shown in the image above, the town of Konigsberg once had seven bridges.  Back before some of these bridges were bombed during WWII, the residents of the town had a long-standing challenge: to walk through the town in such a way that you crossed each bridge exactly once—i.e., without missing any bridges, and without crossing any of them twice.

So, why is this problem so great for a high school classroom?  Well, first of all, whenever I tell this rather contrived tale to my students (or their parents, for that matter), they are inevitably scribbling on their scrap paper before I can even finish.  It’s a compelling puzzle, simple as that.

Before long, students have redrawn the thing enough times that they’re annoyed with all the extra time it takes to draw all the landmasses and bridges, and so they simplify it:

(image from wikipedia)

Voila: in a completely natural fashion, they have reduced the problem just like Euler did.  At this point, I usually bring them together for a moment to appreciate what’s going on here: reducing a problem to its essential components, finding the simplest way to represent the underlying structure of the situation.  (And I also mention to them that this is precisely the move that Euler made when he invented graph theory based on this initial problem.)  Even if they never went any further, this is already a nice lesson in problem solving.

[SPOILER ALERT: notes on the solution below the fold]

Mimi, I am that student.

Yesterday I opened class with this question, taken from the University of Maryland High School Mathematics Competition (2005):

What is the value of    log (2/1) + log(3/2) + log(4/3) + … + log(99/98) + log (100/99) ?

Students who remembered their logarithm properties (from the last time we had class…) saw almost immediately that they could multiply the arguments together and, ta-da, have the numerator cancel with the denominator until it becomes just log (100) = 2.   But there were a few groups who didn’t remember this property.  Well, one group knew they could expand the arguments into log 2 – log 1 + log 3 – log 2… but didn’t follow this logic far enough to solve the problem.  That would’ve been cool, and it’s exactly why I ask students to share ideas that didn’t work– sometimes it’s a bad idea, other times it’s bad execution.

But anyway, I write because one group was kind of sitting and starting at the problem.  I heard one of them say, “You know the first one is going to be the biggest, and the others get smaller… and they are getting closer to 0.”   And I thought: cool!  They just turned this log properties problem into a sequences problem, even looking at what the terms are approaching!   I missed this structure of the terms because I had so quickly calculated the answer.   I had acted exactly like the students Mimi was talking about in her post (A critical mass problem)– I missed subtlety in my haste to get the answer.   It was a little unfortunate that this group couldn’t actually solve the problem with their realization.  It’s always fun when a cool insight actually helps you to solve the problem.  Maybe next time.

Learning to Read

Yes, this is math class, but especially in a problems-based curriculum we are teaching reading at the same time, right?

I recently gave two classes the following problem*: “How many triangles are there whose three vertices are points on this 3×3 square grid?”

Once they put their heads together, kids are able to make nice progress on this problem.  It’s intended to teach the habit of “taking things apart” (most kids tend to say, “break it down”), and comes with a suggestion to count the number of triangles you can make within a 2×2 grid, then a 3×2 grid, then the full 3×3 grid.  Not all kids take this suggestion (and good for them), but most wind up categorizing triangles by type somehow and then counting how many there are of each type of triangle.

Looking back, I think about the little things that tripped up the kids, all of which had to do with implicit assumptions about what the problem was asking.  Some kids wanted to know if the vertices of the triangles had to be on the dots in the grid, or if they could be in between.  Other kids assumed that the triangles had to be right triangles, or else asked if it was okay to use non-right triangles; these kids thought that there was real ambiguity in the question.  I want too much to be helpful, and for the students to be able to get on with their math, so in this case I answered their questions directly rather than doing what (I suppose) I should do: telling them to read the question again.  At times I have done a better job guiding students back toward the question.  I resolve to be so good again!

Other questions that the kids had about the wording of the problem struck me as more legitimate.  One question that came up was, “if two triangles are the same shape, should we count them as different triangles?”  Here I think the kids have a case that the question is ambiguous.  After all, we are just beginning to study graph theory, in which we’re about to call several pairs of isomorphic graphs that look nothing alike “the same.”  I’ve encountered many problems over the course of teaching that, while not ambiguous to someone “in the know,” can actually be read a few different ways by an attentive student.  I suppose that teaching students the conventions  of mathematical language is also “teaching them to read.”

*this problem appears in our textbook, inspired by a problem on a Math Counts competition.

Giuseppe’s Fingers

I assigned the following problem last week in my class:

Giuseppe likes to count on the fingers of his left hand, but in a peculiar way.  He starts by calling the thumb 1, the first finger 2, the middle finger 3, the ring finger 4, and the pinkie 5, and then he reverses direction, so the ring finger is 6, the middle finger is 7, the first finger is 8, the thumb is 9, and then he reverses again so that the first finger is 10, the middle finger is 11, and so on.

One day his parents surprise him by saying that if he can tell them some time that day what finger the number 1,234,567 would be, he can have a new sports car.  Giuseppe can only count so fast, so what should he do? 

Here’s how it went down:

 Some of my students realized instantly that counting up to 1,234,567 on their fingers wouldn’t be a very effective use of their time (or Giuseppe’s!).  Others counted up to about 180 until they “abandoned ship” on the brute force method.

Mice and Wine

This is one of my favorite problems:

You’re planning a huge party for tomorrow, which will include a toast exactly 24 hours from this moment.  You have 1000 bottles of wine, but one of them is contaminated with a slow-acting poison that will kill any living thing within 24 hours of being ingested.  You happen to have 10 altruistic mice on hand who have volunteered to test the poison.  How many bottles of wine can you safely serve at the toast?

I’ve given it to a number of classes, ranging in age and strength, and it’s produced wonderful discussions every time.  Here’s a reconstruction of how many of these have gone.

Right off, several students come up with the idea of splitting up the 1000 bottles evenly among the 10 mice.  When one of the mice dies, they explain, you would know that the poisoned bottle was among the 100 that it drank, and so the remaining 900 would be safe to serve.