Tracing a Figure Without Lifting Your Pencil
Date: 03/09/2001 at 19:57:01 From: Kerri Subject: Tracing a figure without lifting your pencil My students have asked me about whether it is possible to trace a certain figure without retracing or lifting the pencil. I have not studied discrete math in a while, and can't remember how to tell if it can be done. We have tried to do it several times with no luck. The figure is a square with both diagonals drawn in, and half circles on all four sides of the square.
Date: 03/09/2001 at 20:13:14 From: Doctor Schwa Subject: Re: Tracing a figure without lifting your pencil Hi Kerri, This problem was first solved by Euler, and in fact searching the Dr. Math archives at: http://mathforum.org/mathgrepform.html for the words "Euler path" found a few useful links on this topic. The way Euler figured out this type of problem is really clever, though, and I can't resist telling you a bit about it myself. As you walk around on your figure, at each "intersection" you have to come in along one path and leave on another. That is, you use up two of the paths that meet at that intersection each time you visit it. Thus, to have a complete traversal possible, every intersection has to have an even number of paths meeting at it. Oh, wait - at the place where you start, you use up only one path when you leave. And the same is true of the place where you end. So, if you end up where you started, you have to use up an even number of paths at every intersection, but if you start and end at different places, those two intersections will have to have an odd number of paths meeting there, and all the rest of the intersections still have to be even. In graph theory, people call the intersections "vertices," the paths "edges," and the number of paths meeting at an intersection the "degree of the vertex," but they still use the same logic. I hope you can give your students some hints and let them have the joy of discovering this idea for themselves! Have fun. - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.