The Problem That Never Fails

Hi.   I’m Anand Thakker, a teacher at the Park School of Baltimore.  Sam has been generous enough to invite me to make a guest post here, in honor of the new math teaching blog my colleagues and I are starting.   We’re psyched to be joining the conversation.

So, having dispensed with that bit of shameless self-promotion, I thought I’d share with you the problem that never fails.  This is 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]

But, often, they do go further.  It is, in fact, impossible to walk all the bridges exactly once, and so the students soon find themselves frustrated.  Eventually, they start claiming that it’s impossible.   I, of course, ask why… and at this point, it’s often fruitful to have a brief discussion about how “I haven’t figured it out yet” is not actually a legitimate reason for why something is impossible.  So, they go looking for a reason why it must be impossible.  Sometimes, they have the key insight: that if an island has an odd number of bridges going to it, then it has to be either the starting point or the ending point of the walk.

But even if they’re stuck, there’s a fruitful (and fun) recourse: I can ask how they could change the town’s layout to make it possible, and even to invent their own bridge-and-island layouts as puzzles for their classmates to try.   This way, they end up generating lots of data, making it much more accessible for them to look for what the “possible” layouts might have in common.   With the benefit of this data, it’s not hard for them to see that it’s about islands having and even or odd number of bridges going to them.   Once they see this, it’s quite natural to ask, “What happens with ‘odd’ islands, as opposed to ‘even’ ones, and why?”  And once they’re looking for it, someone almost always realizes that when you get stuck, it’s always on an “odd” island.  From here, it’s a quick jump to the essence of the proof: that every island except the starting and ending ones must have an even number of bridges, so that for every time you arrive at the island, you can also leave.  As you can probably imagine, when students come up with this rather elegant general argument, after all of the struggle and frustration of the initial problem being impossible, they find it immensely satisfying.

So, to recap: what makes this a perfect problem?  (1) It is instantly engaging, and instantly accessible.  Students can begin thinking, without my help, right away.  (2) It can’t be resolved with a simple, correct answer — it inherently requires reasoning and argument. (So that “show your work” or “justify your answer” need not be artificial commands on my part.)  (3) The underlying math the students ultimately uncover is beautiful to the point of goosebumps… so that, hopefully, they get a glimpse of what’s so great about math beyond its usefulness for science and finance.  (4) There’s much, much more to graph theory, if they’re into it, so there’s somewhere to go from here.

About these ads

9 thoughts on “The Problem That Never Fails

  1. Thank you, Anand. I also love this problem, but never would have called it the problem that never fails. I feel like a dunce as a teacher, because, once I read this post, your ideas seem so natural. But I know I never managed to get it to flow like this.

    I think the key is giving the low-key suggestion you did: I can ask how they could change the town’s layout to make it possible, and even to invent their own bridge-and-island layouts as puzzles for their classmates to try.

    I’m eager to try this one again.

    • Ah, well about that “flow”… I should mention that there’s quite a lot of messiness that happens along the way.

      For example, when they first decide that it’s impossible, they sometimes come up with convoluted arguments involving testing all of the different possible paths… in which case it’s not always easy to get them to back up and look for a *property* of the graph that causes it to be impossible.

      Other times, they jump a bit too quickly to theories about the number of islands, or the number of bridges, etc… and so we end up spending a good bit of time seeking counterexamples for one theory after another.

      But, ultimately, even though the flow isn’t perfectly smooth, those diversions and false starts feel worthwhile to me–they’re part of the process. (And that’s what real inquiry is always like.)

  2. There’s a really good iPad app that goes hand in hand with this lesson called uconnect. The students learn real quick that they need 0 or 2 odd numbered nodes.

  3. Nothing to add except that I have a crush on you guys at Park School. John Burk sent me your math habits like a year ago and I’ve been a groupie ever since. Oh..and….you know…those late night phone calls are totally not from me…….

  4. When I was in high school this problem would have failed for the opposite reason—some of us had seen the proof years earlier. One problem with “old reliable” problems is that everyone uses them, and they lose a lot of their punch the second time around (and are excruciatingly boring on the 5th or 6th time someone “challenges” you with them).

  5. […] #split {}#single {}#splitalign {margin-left: auto; margin-right: auto;}#singlealign {margin-left: auto; margin-right: auto;}#splittitlebox {text-align: center;}#singletitlebox {text-align: center;}.linkboxtext {line-height: 1.4em;}.linkboxcontainer {padding: 7px 7px 7px 7px;background-color:#ffffff;border-color:#000000;border-width:0px; border-style:solid;}.linkboxdisplay {padding: 7px 7px 7px 7px;}.linkboxdisplay td {text-align: center;}.linkboxdisplay a:link {text-decoration: none;}.linkboxdisplay a:hover {text-decoration: underline;} function opensingledropdown() { document.getElementById('singletablelinks').style.display = ''; document.getElementById('singlemouse').style.display = 'none'; } function closesingledropdown() { document.getElementById('singletablelinks').style.display = 'none'; document.getElementById('singlemouse').style.display = ''; } How I Failed, Failed, and Finally Succeeded at Learning How to CodeThe Problem That Never Fails […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s