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: