By Wednesday, we’ve reached the very middle of the Math CAMP week. So far, the CAMPers have explored a wide range of math puzzles and games, as well as having learned about binary (writing numbers in Base 2, as strings of 0’s and 1’s). This morning, we had a special guest lecture by math professor Charles Doran, which taught us the mathematics behind the Towers of Hanoi.
- What is a Graph? – We opened with a discussion of the Konigsberg Bridge problem (see images below): Is it possible to take a walk through town, crossing over each bridge exactly once? By shrinking down each landmass to a point (vertex), because we don’t care about shape or size, and by making each bridge a line (edge) connecting two vertices, we can determine whether or not there exists a path through every edge, with no repeats. This object is what we call a graph. But what if we want to find a path that goes through each vertex exactly once?
- Hamiltonian Paths – That last problem is what an Irish mathematician named William Rowan Hamilton (not to be confused with founding father Alexander Hamilton!) wanted to find the answer to. The CAMPers were treated to a brief sample of an A Capella Science Hamilton parody video (William Rowan Hamilton (Science YouTuber Collab) | A Capella Science – YouTube) before taking a look at a set of graphs Qn (n = 1, 2, 3, …): Q1 consisting of 2 vertices connected by 1 edge (drawn as a line segment), Q2 having 4 vertices connected by 4 edges (drawn as a square), Q3 being drawn as a cube in 3-space.
- Naming Vertices – So now we have a good set of graphs to work with, but is there a way to find a Hamiltonian Path (one that passes through each vertex once) without paying any attention to the edges, since the vertices are the only thing we care about? Using coordinates to name the vertices (0 and 1 on Q1, x- and y- coordinates on Q2, and x-, y-, and z-coordinates on Q3), we can see that the pairs of vertices connected by one edge are those that use one bit-flip (a switch from 0 to 1, or vice-versa), and paths are a sequence of vertices such that every pair is connected by 1 edge. So, a path that goes through all the vertices is really a sequence of vertices whose x-y-z coordinates only change by one bit-flip each time.
- Gray Codes – We tried to write the sequence of vertices on the cube as numbers 1-7 in Base 10, converted into binary (Base 2), but we soon realized that there were too many steps involving more than one bit-flip, which doesn’t make a path. To fix this, we were given two recipes for the conversion binary numbers to the Gray Code system, which gives us a perfect Hamiltonian Path (exactly one bit-flip to take us from each vertex to the next).
- Baguenaudier Puzzle – One of the best things about Gray Codes is that they can help us solve math puzzles – from Baguenaudier (“time-waster”) rings (The Chinese Rings Puzzle (wolframcloud.com)) to, you guessed it, the Towers of Hanoi.
- Towers of Hanoi – Many of our CAMPers have already solved the six-ring version of the Towers of Hanoi, but with Gray Codes we can figure out the solution to the n-ring version of the puzzle – no matter how many rings there are, the Gray Codes never fail. All we have to do is interpret each bit-flip as a transfer of one ring to a different tower (and since there are n towers, our Gray Code numbers will have n places). However, the fun’s not over yet – How can we use Gray Codes to solve the puzzle when someone hands us a partially completed Tower of Hanoi? This was one of the several new questions that we were left with at the end of the lecture.
After the lecture, CAMPers went off to Math class, where those in the COS group continued working with the Cantor Set, starting off by brainstorming a list of deceptively simple questions – Is 1/4 in the Cantor Set? What about 3/4? Is 0.9999… the same thing as 1?. Then they started using algebra to convert numbers in different bases (e.g., 0.2020202020…, which is in Base 4) into fractions in simplest form.
The SINE group continued to explore the properties of the Sierpinski Triangle, this time working to find its dimension (at first glance, it looks 2-dimensional… but is it, really?), beginning by finding the scaling factor.
In CS class, the SEC group built off of what they had learned about binary and Gray Code numbers in the guest lecture, continuing to break down place value in Base 10, which led them to a convenient way of converting binary numbers back to decimal (Base 10) – multiply the 0 or 1 in each place with powers of the base (in this case, 2) which indicate the place value of the digit (e.g., 110 = (1 x 2^2) + (1 x 2^1) + (0 x 2^0) = (1 x 4) + (1 x 2) + (0) = 4 + 2 + 0 = 6, and you’ll get the same number in Base 10).
After having lunch at Kline Dining Commons, CAMPers chose between playing Conway’s Game of Life, taking a hike to the Parliament of Reality, and the decoration of another mysterious wire sculpture – this one, tucked behind the Chapel of Holy Innocents, is even more abandoned than the one we decorated on Day 2, complete with just-as-intricate cobwebs stretching between the metal rods. (This elective also included a very intense sponge race.)
Once the electives were over, CAMPers in SEC went to Art class – where they continued making paper cubes.
In the last half hour of CAMP, the groups reconvened in the Auditorium (RKC) for more math activities – Rubik’s Cubes, Hex, an M. C. Escher memory game, and (naturally) the Towers of Hanoi.
Day 3 started off with puzzles, segued into the binary system, explored irregular objects with unusual dimensions, and ended with more puzzles. We’re eager to find out what math will await us on Thursday morning!
Photo Credit: Sonita Alizada (images 21-25, featured image), Kateri Doran (images 1-8, 10-20, 26-35), screenshot by Kateri Doran (image 9).
