P versus NP lecture, a good place to start on winning $1 million

Here's a lecture, sponsored by the Clay Mathematics Institute (yes, the folks who put up $1 million for the solution of any of the remaining six Millennium Problems) by MIT professor, Michael Sipser.  Not claiming this is a walk in the park, but it's an excellent introduction to what is considered the most accessible of the prize problems, as well as to the vital subject of computational complexity theory. The solution to the P versus NP problem would have many important consequences.

  

Hexaflexagons and other Flexagons

Here is the webpage with a host of resources for today's activity, including links to Vi Hart's videos that got us going.  Have fun and have a great break. I will see you in January and expect that you'll be bringing us hexaflexamexifood.

Update: here is an interesting, somewhat relevant resource: you can make calendars for the new year on various polyhedra and other 3-dimensional shapes. Everything you need is there to print, cut out, and assemble. Enjoy!

December 11, 2012 - Art Gallery Problem => Math Works!

A Challenging Art Gallery

Nothing is more intriguing (to me, at least), than a recalcitrant example of a math problem I thought I had mastered but which refuses to cooperate. In our recent work on graph theory, we had looked last week at a family of related problems called "art gallery problems." We worked through the thinking that led to Fisk's constructive proof of the "art gallery theorem" that Chvatal had proved through more formal (and difficult to understand) means on a few years earlier. Fisk demonstrated precisely how to calculate and arrange the minimum number of "vertex guards" in a polygonal art gallery so as to "cover" the entire interior of the gallery. In simpler terms, this means finding the minimum necessary number of stationary guards placed only at vertices of a simple (non-intersecting) polygonal-shaped "gallery" so that every point inside or on the interior walls of the gallery are in view of at least one guard. We could test such an arrangement by drawing a straight line that stayed entirely inside the gallery between a given point and at least one vertex guard. If such a line exists for every point in the gallery, we have "covered" it and all the art works on the walls or "free standing" (e.g., sculptures, mobiles) are protected 

As I said in a previous post, this number can be found by taking the integer portion (or "floor") of n/3, where n = the number of vertices (or edges) of the gallery. The resulting number is the smallest number of guards that are sufficient for a given gallery and also the smallest number necessary for a "worst-case" arrangement of n vertices. Fisk showed that by triangulating the graph, it is always possible to have n - 2 triangles created by adding n - 3 diagonals connecting vertices which stay completely inside the figure. 

As the above graph has 20 vertices, the floor of n/3 is 6. So 6 vertex guards are sufficient. But are they also necessary or are fewer possible (because it turns out that this is NOT a worst-case for 20 vertices)? 

Assuming we have triangulated correctly, we proceed in Fisk's method by doing a proper (minimal) graph coloring of the vertices (so that no two vertices that are connected by an edge have the same color). Since we have nothing but triangles, it should always be possible to do this with exactly 3 colors. We then count how many vertices have a given color, and whatever the minimum-appearing color turns out to be is where we should place guards.

When we worked on the above-pictured gallery last week, I found a triangulation and coloring for which two colors appeared six times each, and the third color was used seven times. Since six was the number the formula produced, I assumed that this was indeed a worst-case scenario.

However, Taylor pointed out that he placed guards at five of the vertices and could (apparently) "cover" every point in the gallery. This was very strange. If the math worked, then something was wrong. One possibility was that Taylor only thought he had every point in the gallery covered with his five vertex guards, but really there was at least some tiny area that they couldn't cover. Unfortunately (for me), I couldn't see any way that this was actually the case. In fact, it seemed that his five guards were sufficient. And that meant only one of two things: math doesn't work, or I had not found the best way to triangulate and/or color the graph. 

I left the problem "unsolved" over the weekend with the thought that this was an opportunity for the students to grapple with a seeming paradox and to find out if math does indeed have to make sense (at least in this case). In all honesty, I was convinced that I was just stuck in a visual rut and that one or more students, looking with fresher eyes and a more flexible mind, would figure out something that satisfied both the obvious fact that Taylor was right and that the algorithm makes sense. 

Students worked diligently on finding a better way to triangulate and color this gallery. Some found clever but, it turned out, flawed solutions. One easy way to check if the triangulation and coloring are correct is first to see if the resulting triangulation uses exactly 17 diagonals to form 18 triangles. Second, there must be a total of 20 vertices in any coloring. It was this last criterion that showed the mistake students made in trying to draw a "continuous" straight line between the bottom point (labeled 6) and, say, point 20 and point 9. But that is NOT a straight line, as can be seen clearly above. Rough sketches sometimes mask this point. 

A very careful check of the graph above, however, shows that everything is correct. We have exactly 18 triangles created with exactly 17 diagonals, each of which connects two vertices  and none of which is ever external to the polygon. And this better triangulation than mine allowed this student to find a coloring for which, as indicated, only five vertices needed to be colored orange, while six are blue and 9 are purple. The total of 20 is correct, and checking the triangles, no connected vertices have the same color. And so Taylor's informal arrangement of 5 guards, while not unique (his placement differed from the above), was indeed minimal and correct. 

I still have to check a few other student papers, but the one I've shown here was done by Denali. I thank her for pulling my chestnuts out of the fire and proving once again that mathematics makes sense. 

Catching Up

An "art gallery"

Sorry for the hiatus to those who've been following this blog. We've been reveling in the wonderful world of graph theory for  the last few weeks and will be wrapping this up tomorrow and getting back to our textbook, since the necessary manipulatives have arrived, allowing us to move forward to section 1.3 & 1.4.

Meanwhile, things we've explored: the nature of and criteria for Euler paths and Euler circuits, and some real-world applications thereof. From there, we moved on to graph-coloring, one of my favorite topics in all of mathematics because of its many intriguing applications for solving real-world and abstract problems.

First, we looked at how to use proper graph coloring (finding the minimal number of colors necessary) for maps. We explored maps of Australia, the southern part of Africa (some students also did the entire map of Africa), and South America. Students saw how doing a proper graph coloring always led to ways to color a map with either three or four colors so that no two countries or states that share a border   (not a single point, as is the case in the "Four-Corner" US states in the far west) have the same color. An important requirement is that the territories in question must be continuous, so that Michigan, which has two main separated pieces, has the potential to violate basic conditions. We spoke about the famous Four-Color Map Theorem, finally proved in 1975, that shows that in fact there can be no map following the rules that requires more than four colors. We also talked about the 3 Utility Problem and watched a video by the young British mathematician, James Grimes, that offered an ingenious 3-dimensional proof of the impossibility of solving this problem that is grounded in Euler's beautiful formula for the relationship between the edges, vertices, and faces of a certain class of polyhedra. The proof helps explain why the Four-Color Theorem is true, though it is not a proof of that theorem.

We next looked at conflict graphs. These are similar to graph coloring for maps, but unlike the case there, there is theoretically no upper limit to the number of colors necessary to do a proper coloring of a conflict graph. Our examples included finding the minimum number of secure (and costly) cabinets needed to store a set of 7 chemicals where certain chemicals cannot be safely stored with certain others, and the minimum number of cars needed to take students on a trip to a museum when certain students cannot ride "safely" with certain others. Other classic examples (that we didn't look at) include scheduling final exams so that no student has to be in two or more exams at the same time. This is a very real issue that schools face every term, and the software used to figure this out is all grounded in conflict graphs.

Our final exploration in graph theory began today as we looked at a family of related problems called "Art Gallery problems." The picture at the top shows the graph for a theoretical art gallery with paintings on all the inner walls. The rules require that the gallery be a simple (but not necessarily regular) polygon, which means all walls must be straight lines, and walls may only adjoin/intersect at end points: no "bow-tie" shaped art galleries. In the basic problem, guards may be placed only at vertices and may not move (fixed vertex guards). The assumption is that any painting not in view of a guard will be stolen, and the task is to A) determine the minimum number of guards necessary to "cover" (that is, keep in view) all of the inside of the gallery, and B) determine a workable placement of that number of guards. The solution is generally not unique for B, but the solution for A for a "worst-case" gallery with n vertices is unique. The formula is floor(n/3), where the floor function gives the largest integer less than or equal to x (the real number inside the parentheses). So for n = 3, 4, & 5, it is possible to cover any n-sided gallery with 1 guard (note that, for example, n/3 is 1.67 and floor(1.67) = 1). For n = 6, 7, 8, no matter how convoluted our gallery, 2 guards suffice.

The method for actually placing the guards is to triangulate the interior of the graph of the gallery. This is guaranteed to create n - 2 triangles by adding exactly  n - 3 interior diagonals (a fact that has already cropped up in our problem from several weeks ago of creating a "complete graph" on an n-sided polygon). After the graph is triangulated, we perform a proper graph coloring on it. We then count the number of vertices for each color. Whichever one(s) have the minimum number tells us the MAXIMUM number of guards that is NECESSARY, and by picking any one of the colors with this number, we have a valid placement for the guards: just put one at each vertex of the color in question.

Tomorrow, we'll apply this to some worst-case scenario galleries, then look at some of the countless art gallery problems that have emerged since the problem was first posed at Rutgers University in the 1970s. This branch of graph theory is continuously growing, with conferences and journals dedicated to the subject. Perhaps you can speak with your child about some of the problems we look into tomorrow. Maybe some of our students can craft original problems or find new solutions to existing ones. We already have one student thinking hard about the remaining six Millennium Problems, the solution for any of which carries a prize of $1 million.

November 15th, 2012

Leonhard Euler (1707-1783)

Today, we spent the first half of class finishing our exploration of problems involving two jars. We first determined that for jars of size 5 and 7, it was possible to measure precisely every whole number from 0 to 12 gallons. Students conjectured that this would not be true if both jars held an even number of gallons. They also argued that if one of the jars held 1 gallon and the other held n gallons, we could make any whole number from 1 to n + 1 gallons. Informal arguments were offered to support these claims.

Some students then speculated that for us to perform the task in question, both jars needed to be prime numbers. However, this was clearly not true, since most mathematicians do not consider 1 to be a prime number. I then asked them to investigate the case of jars holding 4 and 9 gallons, respective, neither of which are prime. They discovered that this combination did in fact allow the completion of the task.

Finally, one student suggested that the requirement was that the two numbers (for jar sizes) had to have 1 as their greatest common divisor. This proved to be the correct idea. We discussed that when this condition held (the notation is (a, b) = 1), the numbers a & b are said to be "relatively prime" to one another. We finished this part of the class by looking at various pairs of numbers and determining if they were relatively prime. Students also offered their own examples. We discussed why this all made sense in terms of addition or multiples of the smaller jar-size: if, say, we had 4 and 9, we could add by 4 to get 4, 8, and then, since we can't get 12 gallons into a 9 gallon jar, we would get 9 + 3. Throwing out the 9, we'd be left with 3. Next, we would get 7, then by the same argument 11 reduced by 9 would leave 2; then 6, then 10 reduced by 9 would leave 1; then 5, and finally 9. This makes every number from 0 to 9. If we try this with 6 and 9, however, we will get into a repeated cycle of 6, 3 and 9. This is called modulus arithmetic, but the term was not introduced in class today.

 We also discussed how this related to the problem we modeled on Tuesday with the surveyor's tape.

The second half of class we began looking at a problem that gave birth to a new area of mathematics in the 1700s thanks to the brilliance of Leonard Euler (see photo above), one of the greatest mathematicians of all time. The problem is generally known as the Konigsberg Bridge Problem or the Seven Bridges of Konigsberg. The city of Konigsberg, located on the Pregel River in what was then Prussia (it is now known as Kaliningrad and is in Russia), had two large islands and two main land masses through which ran the Pregel. A series of seven bridges connected them (see picture below):

City of Konigsberg, Prussia

People were fond of strolling through town crossing the bridges in various order and it became a challenge to devise a route that crossed every bridge exactly once. One could not partially cross a bridge and retrace one's path, then later cross the other part of that bridge, nor was it considered a solution to jump off a bridge into the water (probably not a very healthy move during the colder months). Some people claimed to have succeeded, but could never replicate the feat for witnesses. Eventually, the problem came to the attention of Euler, who was living in the city at that time. Euler's genius led him to abstract the essential elements of the problem so as to represent the land masses as points (or "vertices") and the bridges as lines (or" edges"), and then to analyze the resulting "graph." His analysis of this problem gave birth to a powerful new mathematical subfield, part of combinatorics, called Graph Theory.

Here is one representation of the above map using the ideas of graph theory:

Graph of the Konigsberg Bridge problem

Students are in the process of analyzing this graph and two others. I have asked them to determine if it is possible to trace the above graph, starting at any vertex, finishing at any vertex (not necessarily the starting point), without lifting their pencil from the paper and without retracing any edge (line). If they can do so and finish where they started, this is called an Euler circuit. If they finish at a different vertex than the one at which they began, it is called an Euler path.  If neither is possible, than the solution to the Konigsberg Bridge problem will be that it cannot be done as stated.

Here are the other two graphs I asked them to explore for Monday:

November 14, 2012

Lots of ground covered today. So as to maximize the opportunity for students (and parents) to sink their teeth into the problem we ended with, I'll forego all the things we looked at earlier in the lesson and cut to the chase. I revived a problem some of the students had looked at with Jason. A version of this appeared in the third Die Hard movie (the one with Samuel L. Jackson as a locksmith), in which Bruce Willis has to figure out the answer in order to get another clue towards preventing a public school building from being blown up (it's an elaborate bluff/distraction from plans for a huge robbery): you must fill a jug with exactly 4 gallons of water given only a 3 gallon and a 5 gallon jug and an unlimited supply of water. You don't get any measuring tools or markers: just the two jugs and the water.

This is, by now, a very well-known problem, and yet many people find it extremely challenging to figure out. It turns out that it doesn't matter whether you start by filling the 3-gallon jug or the 5-gallon jug: either approach can lead to a solution.

I reposed that problem today only with a 5-gallon and 7-gallon jug. Further, rather than asking students to make one particular number of gallons, I asked them if it is possible to measure exactly every whole number amount of water from 0 to 12 gallons, inclusive. That is where class ended, with most students well on their way to a solution. I then asked them to consider for tomorrow whether this is possible with any two jugs that hold different whole numbers of gallons; that is, for jugs holding A and B number of gallons (both whole numbers), is it always possible to measure precisely all whole numbers from 0 to (A + B) inclusive. If not, what must be true about A & B for this to be possible?

November 13th, 2012

On Tuesday, November 13th, we returned to a previous problem and then explored it more deeply, eventually doing a physical demonstration that led to some new questions. The original problem, commonly known as the "Handshake Problem," asks students to consider a party with 100 people at which every person shakes hands with every other person one time, and then to determine how many handshakes there are in total.

One of the problem-solving methods students are asked to employ is to simplify problems with "inconvenient" or "unwieldy" numbers by using easier or smaller numbers, trying to discover an underlying pattern or principle, and then applying that to the original situation. In the Handshake Problem, I intentionally make the number of guests large so that simply counting will be tedious and impractical. This is intended to push students to try to model the problem with a more manageable number of guests, such as five. If need be, I ask leading questions until someone realizes that 100 is too large to model. Most students (no matter what age group I do this problem with) initially guess that the answer will be either 100*100 or, after some thought, 100*99, which, while more reasonable, is still much too large. Some students argue, correctly, that the first person has to shake hands with 99 others, the next person with 98 others (having already shaken hands with the first person), and so on until the last person doesn't need to shake hands with anyone, having shaken hands will all the other 99 guests. Thus, we can get the answer by adding the whole numbers from 1 to 99. This is an improvement, but still requires a tedious calculation. So we try to see if there is a quick way to add consecutive whole numbers from, say, 1 to n.

I generally introduce the (possibly apocryphal) story about the young Karl Gauss (generally viewed as one of the greatest mathematicians of all time), who added all the whole numbers from 1 to 100 by arguing that he could write 1 2 3 . . . 98 99 100 and then write directly under them 100 99 98 . . . 3 2 1. Adding the two rows would result in 100 copies of 101. However, he noted, 100*101 would be the sum of the numbers from 1 to 100 TWICE. So the right answer would have to be 50*101 = 5050 (which is correct), and in general the formula here would be[n(n + 1)]/2, which the division by 2 represents adjusting for "double counting").

Looking back at the handshake problem with this analysis suggests the fast way to solve the problem. The first person must shake hands with 99 others. And all 100 people are in the same boat. That is where 100*99 comes from. However, when A shakes hands with B, B is simultaneously shaking hands with A. That is only ONE handshake, but each person counts it. So we have double-counting again. Thus, the correct answer is 100*99/2 or 50*99. The general formula for the handshake problem is [n(n - 1)]/2, similar but not identical to the formula Gauss (and countless others since him) derived.

We then looked at related problems where a new parameter for repetitions - k - is introduced. This would come into play, for example, where we had 10 basketball teams in a league where each team played the others 4 times during the season. The calculation would be (10*9*4)/2 and the general formula would be
[n*(n-1)*k]/2

Finally, I raised the question of whether in these sorts of problem, the second factor would always be n - 1. Would it be possible to have [n*(n - a)*k]/2 for a = 2 or 3 or some other number?

I posed the following: given an octagon, how many diagonals must be drawn to connect all the vertices to those vertices to which they are not already connected?  Students generally realized that in this case, a could not equal 1. Most of them switched their focus to the two vertices adjacent to any given vertex, and decided that the correct equation was (8*6)/2 = 24. However, a careful count of the total diagonals (keeping in mind that the sides of the octagon do not get counted), revealed that the correct total is 20. Where had they gone wrong? They had forgotten that any given vertex does not get a diagonal drawn to itself. Thus, a = 3, not 2, and the correct equation here is (8*5)/2 = 20 and the formula would be [n*(n-3)]/2.

The class then took surveyor's tape to model the problem and to explore an interesting algorithm. First, a group of 5 students formed a rough pentagon. One student wrapped the tape around his left wrist and passed it to the student on his left. This repeated until we had the sides of the pentagon. Then, the first student wrapped his left wrist again and the tape was passed to every 2nd student until it came back to the first student again (this took two circuits around the pentagon). At this point, we saw that there was a pentagram (5-pointed star) inside our figure and that everyone was connected by one diagonal to everyone else except for himself and his adjacent neighbors (see photo)

A complete graph on 5 vertices

Next, a group of seven students followed a similar process, but after the two circuits that had them passing to every second student, we had to make three circuits passing to every third student before every diagonal was completed (see photo)

A complete graph on 7 vertices

Finally, we tried this process with six students. Everyone was surprised to discover that the method didn't work: after one circuit passing to ever second student, they were stuck in a triangle that never released to the other three students!

We ended class with Stanley conjecturing that this method would never work for an even number of vertices. I asked students to consider for tomorrow what numbers would and would not work for this particular method of connecting all the diagonals and sides (edges).

Lessons 11/7 to 11/12/12

Last Wednesday, November 7th, we began an exploration about perfect squares and their sums that is grounded in the "Checkerboard Problem." (Of course, there are many "checkerboard" problems, but this is one of the more commonly-posed examples of the breed). This problem poses the question: how many squares are there on an ordinary 8 x 8 checkerboard (or chess board)? Ask your student about the answer when you think you know. After that, if your child isn't quite clear on how we determined the answer, check out this link with him/her.

The solution leads to a rather natural question: is there a formula for summing the first n consecutive perfect squares: 1 + 4 + 9 + . . . + n^2? This is not an easy formula to derive and I didn't ask the students to do so. Rather, I gave them the formula, which is [n(n+1)(2n + 1)]/6 and we first checked our result for the checkerboard problem against actually doing the sum. We then spent some time building a three dimensional model that serves as a visual proof of the formula (for those familiar with mathematical induction, it's relatively easy to prove the formula by induction, but that is probably too advanced right now for the students, and more importantly, that proof doesn't give any insight into how the formula was arrived at in the first place.

Here are some photos of what the students built from linking cubes:

What the students did was to build six identical "staircases" with 1, 4, and 9 steps. Then, they made two complementary shapes, each constructed from three of the staircases, and finally fit the two large structures together to make a rectangular solid. The dimensions of the solid, as you may be able to discern from the various photographs, are 3 x 4 x 7. This gives a volume of 84 for the solid. Since there are six staircases, we divide 84 by 6 to get 14, which is the sum of 1 + 4 + 9, the first three perfect square numbers. And plugging n = 3 into the formula gives exactly 3(3 + 1)(2*3 + 1) = 3*4*7 = 84. 

We still have more work to do with this formula and will return to it (and some other approaches to "proving" it) later in the term. A couple of students have asked me to leave the materials so they can try building a solid made from staircases with 4 or even 5 levels when they have time outside of math class. 

Welcome to Summers-Knoll Mathematics

Michael Paul Goldenberg

Greetings, Summers-Knoll community members. My name is Michael Paul Goldenberg, and it is my pleasure and privilege to be teaching mathematics this year. I apologize for not being able to introduce myself to you sooner, but I only began at S-K a few weeks ago. This page will serve as my way of providing information to parents and students about what we're doing in mathematics. I will try to give frequent updates about what we are working on, how it's going, what you can have your student working on at home (particularly from Friday to Sunday, as I am at the school on Monday through Thursday). I will offer links to cool and intriguing mathematics articles, books, and resources as I run into them. Most of what I recommend will be free. I hope you'll find many of these things of sufficient interest that you may want to pursue them with your child yourself.

Paul Lockhart

The first resource I want to recommend is an article that first appeared about six years ago and has subsequently been enlarged into a book (one I just finished reading about two weeks ago, though I'd read the article when Stanford mathematician and NPR's "The Math Guy," Keith Devlin, wrote about it in his column, "Devlin's Angle." The article (and the subsequent book) is called, "A Mathematician's Lament,"  and the author is Paul Lockhart, a professional university mathematician who chose to leave research mathematics to teach at St. Ann's, a highly-regarded private school in Brooklyn, NY. I cannot recommend this article/book too highly to you (the article is great, but the book goes further in making the case that what most of us were taught in K-12 has little if anything to do with mathematics, and the sad situation in which most Americans find themselves in relation to the subject is grounded in the fact that they've actually never seen real math, never seen or been asked to do actual mathematics, and instead have been given the wrong-headed notion that the subject comprises little but routine calculation/computation and the rote memorization, practice, and application of arcane definitions, terminology, notation, and algorithms in the service of finding a single numerical answer to problems (or, more accurately, exercises) the solutions to which are already well-known. Further, K-12 math teachers and undergraduate mathematics instructors give students the impression, at least through the completion of the calculus sequence, if students get that far, that the keys to being "good at math" are speed and accuracy. Thus, along the K-14 path, students drop out of mathematics as they realize that they're not speedy calculators and don't see the solution methods to various exercises as instantly as their instructors and their more "mathy" peers. By the end of the second year of college, the number of American students who are likely to pursue more mathematics or mathematics-based courses has dropped so dramatically that it borders on a national "crisis," (though I would argue that the nature of that crisis isn't quite what it's generally made out to be). 

Please try to find the time to read the article or at least peruse it. As I'm not a professional mathematician (I have a masters degree from the University of Michigan in mathematics education), it's gratifying to find working mathematicians with whom I share similar views of what K-12 mathematics should look like and how far short of that most US instruction falls. 

Later today, I will be posting pictures from the problems we worked on starting last Wednesday and concluding yesterday, as well as a summary of what those problems entailed. We turned to something new today that will continue tomorrow, and I will post photos from the activity as soon as I can. I'll try to keep things updated here regularly: every day or every other day if possible. Feel free to contact me if you have questions about any of the problems you see here or other mathematics issues: mikegold@umich.edu

It's been really invigorating and inspiring to work with S-K students and staff. I welcome the opportunity to help craft a mathematics program with them that will serve well the interests and natural curiosity of our students. 

Warm regards,

Michael