Summers-Knoll Mathematics
Thursday, May 16, 2013
Tuesday, January 29, 2013
January 2013 thus far
James Grime |
A lot of things going on in math. We spent a good part of January looking at positional mathematics and various bases, from the standard base 10 (decimal) mathematics to important other bases for computer science: base 2 (binary), base 8 (octal), and base 16 (hexadecimal). Students had a chance to gain a better appreciation of how decimal mathematics works, why positional systems have huge advantages over non-positional systems like Roman numerals (doing arithmetic, even addition, in such systems is excruciatingly slow and painful), and why there is no such thing as THE best base or natural base that we're obligated to use.
Part of this latter issue came up when we watched a video by English mathematician James Grime on dozenal (base 12) mathematics.
Before we left bases, we talked about what such exotic beasts as negative and fractional (rational) bases might look like. As one student said, "My mind is blown." And as I said, "I like having my mind blown every once in a while." I'm confident that there was no permanent loss of minds, and that this exploration is already paying dividends.
Starting last week, we changed gears, though only slightly. We began working on a number of problems that emerge from investigating something called "Number Bracelets." Take a look at the basic rules of the game and some elementary questions associated with it here.
We have moved further to start thinking about what happens when you play this game with the same rules but with moduli other than 10. Please take a look at this page.
Today (Tuesday, 1/29/13), we backtracked a bit to look more closely at the definition of modulus arithmetic ideas related to it (in particular, congruences). We began by looking at clock arithmetic, where our friend base 12 makes another appearance, unsurprisingly. Clock math is one of those places where a powerful idea in mathematics is introduced in an elementary context and then (generally) left to lie fallow for most students forever. Only if they take a course in, say, abstract algebra as college junior or senior mathematics majors does this arise again, only in a more formal (and often forbidding) context.
One problem we looked at today from the perspective of modulus arithmetic and congruences appeared (in slightly different form) on an SAT math section in the late 1970s: A machine creates colored banners in a certain order - red, blue, green, yellow, purple, orange, red, blue, green, yellow, purple, orange, etc. If this pattern is repeated indefinitely, what color with the 379th banner be?
Stuck? Ask your child to give you a hint.
After that one, we looked that the following: without using a calculator or actually computing the value of 37^15 (37 raised to the 15th power), figure out what the units (ones) digit will be.
See if you can figure this out by hand. It is utterly unnecessary to know what 37^15 equals. Using modulus arithmetic, it is trivially easy to figure this out by hand with almost no calculations (and certainly nothing difficult or advanced). Again, if you get stuck, speak with your student.
Tomorrow we will return to the number bracelets game to explore some deep questions about how things work when we play the game using various other moduli, from 1 on up. And perhaps we'll explore later a question raised this morning by Jianmarco about the possibility of fractional moduli. :^)
Thursday, January 3, 2013
Sunday, December 23, 2012
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.
Wednesday, December 19, 2012
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!
Tuesday, December 11, 2012
December 11, 2012 - Art Gallery Problem => Math Works!
Tuesday, December 4, 2012
Catching Up
An "art gallery" |
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.
Subscribe to:
Posts (Atom)