Balloons and some graph theory
Can you twist the above balloon using just one balloon? (Assume you can’t cut or pop the balloon into more than one segment.)
If you can figure out the above, you are solving a problem equivalent to what the mathematician Euler resolved in 1735, laying the foundations of graph theory!
Some background: If you are familiar with graph theory, you may remember this as the “Seven Bridges of Königsberg” problem.
At the time, the city of Königsberg, Prussia had 7 bridges connecting its pieces of land that were separated by branches of the Pregel River. The question posed was whether you could walk through the city and cross all bridges, but cross each bridge exactly one time. Euler broke down this problem abstractly. In the below graph, the edges (lines) represent the bridges and the nodes (dots) represent the land the bridges connect.
If you compare a graph of the seven bridges of Königsberg with a graph of the balloon (I’ve blogged about graphing balloons before), you’ll see that they are the same. And if you think about it a little more, you may see that asking whether you can cross all the bridges exactly once is the same as asking whether you can twist the above balloon using one balloon!
Pretty cool, huh?!
Balloon twisting has a lot to do with graph theory!
Another similar question is asking if there’s any route Pac-Man could take to eat all the pac-dots without traversing any part of the maze more than once (assume Pac-Man can start at any point.) Can he?
(Take some time and try to figure it out now!)
The graph representation of this maze is the same as the graphs above. And the question is basically the same question asked before.
Same question, same answer.
(Don’t read below this if you don’t want to know the solution yet.)
Some graph theory basics: if a node (aka vertex) has an odd number of lines coming from it, it is an odd node. If a node has an even number of lines coming from it, it is an even node. Euler proved that if a graph has exactly two odd nodes, you will be able to cross each edge exactly once (there is a Eulerian path), but you have to start at one of the odd nodes and end at the other odd node. If the graph has ALL even nodes, you can cross each edge exactly once AND end at the same point you started (the graph has a Eulerian path AND Eulerian circuit.)
In the graph above, all four nodes are of odd degree, so this graph does not have a Eulerian path or Eulerian circuit. The answer is: you cannot cross all bridges exactly once. And you cannot twist the balloon with exactly one balloon. (You’ll need two balloon segments.) And, no, Pac-Man cannot eat all the pac-dots without traversing part of the maze more than once.
Now back to balloon twisting – I wonder how I can use the above balloon – heart? head of a mouse or koala bear? base of a spaceship? 🙂
(And for you history buffs, two of the seven bridges still exist in what was Königsberg, today Kaliningrad [Russia]. Two of the bridges were damaged by Allied bombing during WWII, a couple were demolished and replaced with a new highway, and one was rebuilt.)
No comments yet.
No trackbacks yet.
about 4 years ago - No comments
This is called an “orderly tangle” (or also “regular polylink.”) This particular tangle is made up of four triangles, which when woven together in a certain symmetric fashion form a stable structure. You may have seen tangles in the form of puzzles before. My college roommate was really into puzzles and had a bunch of…
about 4 years ago - No comments
Here’s a balloon ball. Sure, you could just inflate a round balloon, but this is cooler. 🙂 In mathematical terms, it’s actually an icosahedron – a polyhedron with 20 triangular sides. It may look complicated, but because of its symmetry and basic units, it’s actually quite easy to put together. I first saw this on…
about 5 years ago - 2 comments
When figuring out balloon designs, it’s optimal to minimize the number of balloons you need and the number of times you break a balloon. This way, you save on the number of balloons you use up, you save time (because breaking balloons and tying knots adds time,) and you save your fingers a little. (Try…