Taylor, a first-year engineering student who has a choice corner room in Hotz Honors Hall, has a very busy day ahead – workout, classes, lunch with friends, a meeting at the Volunteer Action Center, tutoring, an Honors College workshop on study abroad grants and last but certainly not least, a quiet hour of study at the library. She’ll be walking to the following buildings on campus:
+ HPER Building
+ Arkansas Union
+ White Engineering Hall
+ Kimpel Hall
+ Science and Engineering Building
+ Gearhart Hall
+ Old Main
+ Chemistry Building
+ Mullins Library
+ Futrall Hall
+ Hotz Hall
Can you draw her path from Hotz Hall to all of the buildings above, then back to Hotz, without visiting any other building more than once?
Bonus
Is it possible to draw Taylor’s path along every sidewalk pictured exactly once, without lifting your pencil or crossing any lines?
Note: Map is not strictly tethered to tiresome reality.
View Solution | Illustration: Leigh Caruthers Prassel
No, you cannot.
To visit all of the buildings exactly once (except for Hotz), any trip around campus has to alternate between sites colored blue and yellow (Taylor’s path must go to buildings colored blue, yellow, blue etc.). But there are more yellow sites than blue, so any trip that goes through every yellow will have to repeat a blue.
Or more simply…
Since ∃V1, V2 s.t. V = V1⎣⎦V2 ∧ |V1| ≠ |V2| ∧ ∀e ∈ E, e = (v1, v2),
v1 ∈ V1, v2 ∈ V2, ∀f : {1, . . . , |V|} → V s.t. for each 1 ＜ i ＜ |V| – 1,
(f(i), f(i + 1)) ∈ E and (f(|V|), f(1)) ∈ E, f cannot be a surjection.
This problem relates to the Icosian game invented in 1856 by Irish mathematician William Rowan Hamilton. The object of the game is to find a path along the edges of a regular dodecahedron (polyhedron with 12 pentagonal faces) so that each vertex is visited a single time, and the ending point is the same as the starting point. “Hamiltonian circuits are widely studied,” said our puzzle master, Chaim Goodman-Strauss, professor of mathematics. “They are in a class of problems, called NP-complete. Proving that the general case really is as hard as everyone thinks would be proving the famous P≠NP conjecture, winning the $1,000,000 Clay Millennial prize.”
Bonus: The answer remains “no,” because if you enter a building, you have to exit as well, and some buildings, such as Kimpel, have an odd number of doors. This problem relates to the Eulerian circuit, first discussed by Swiss mathematician Leonhard Euler while solving the Seven Bridges of Königsberg problem in 1736.
For an interactive primer on graph theory visit the D3 Graph Theory web site (mrpandey.github.io); Introduction to Graph Theory by Richard J. Trudeau also provides a good overview on the topic.
Hamilton & Euler Images: Alamy