Dennis is a professor of computer science at New York University. His latest books include Dr. Ecco's Cyberpuzzles: 36 Puzzles for Hackers and Other Mathematical Detectives (W.W. Norton, 2002) and Database Tuning: Principles, Experiments, and Troubleshooting Techniques (Morgan Kaufman, 2002). He can be contacted at DrEccoddj.com.
The tabloids made it a cover story. It was unfashionable to build very tall buildings, so Donald Pump wanted to build the largest possible ice rink.
"He wants to buy at least one of our Zamboni ice resurfacers," Ecco's visitor, Tony Zamboni explained. "We want to design a complete solution for him. We have a tradition to live up to."
"A tradition?" Ecco asked.
"Yes," Tony responded. "You have to understand my grandfather's passion for ice. During the 1930s, Frank Zamboni manufactured ice for boxcars full of lettuce. When that business declined, he began building ice rinks in southern California. The climate there is tough on ice and he had to resurface frequently. This meant bringing out a tractor, shaving the surface, removing the shavings, spraying water over the surface, and allowing the water to freeze. During the hour this took, many of his customers would leave. So he invented—and then reinvented many times over the years—an ice resurfacer. These are still called 'Zambonis.' The tradition is that we must continuously improve our machines and the way they are used.
"The basic problem is that when a Zamboni drives, everyone must just sit and wait. It no longer takes an hour, but it may take half an hour. In this new millennium, that seems way too long. So, we want to make it accomplish its job as quickly as possible. The trouble is that the Zamboni doesn't have a very tight turning radius. For this reason, it must sometimes drive over spots it has already resurfaced. The question is how to minimize the time.
"Knowing that you are a mathematician, we have abstracted the problem to the slightly asymmetric shape Pump wants it to be like, as shown in Figure 1: A 4×8 grid of points with the corners cut off plus four more nodes on the top (where the winners stand when there are figure-skating tournaments)—32 points in all.
"The distance between neighboring points is roughly the width of a Zamboni, so your goal is to have the Zamboni drive over every node at least once. At every darkened point (node), the Zamboni can turn 45 degrees from the direction it is moving in."
"So, if the Zamboni has moved from node A to node B as in Figure 2, it can move to node C if the angle formed by the rays AB and BC is 45 degrees," Ecco's niece Liane interjected. "In other words, certain paths are acceptable and others are not."
"Correct," said Tony to the 16-year-old. "Going from a node to a neighboring node takes 30 seconds. What is the smallest number of minutes you need to enter at the bottom (you can choose any bottom-most node), touch every node and then exit by some bottom node? Entering and exiting is from a driveway that is perpendicular to the bottom of the rink, so you can enter and exit at any angle you like."
Liane and her younger brother Tyler were able to find a solution in under 20 minutes.
"That improves our time by a third," the young Zamboni said. "The Donald should be pleased."
Reader: Would you like to see whether you can improve on this time?
After Tony had left, Ecco turned to his niece and nephew. "Nice work," he said. "How much bigger could you make the rink and still do it in the same time? Assume you have to keep the nodes of Pump's rink, but could add some. How many Zambonis would you need to cut the time down to 10 minutes for the Pump rink as it stands?"
I had to leave before I heard the answers.
Reader: Would you like to give these a try?
Check next month's Dr. Ecco installment for the solution.
DDJ
