Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992); Database Tuning: A Principled Approach (Prentice Hall, 1992); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications Oxford University Press, 1999); and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer Verlag, 1998). He can be contacted at [email protected].
The newly elected mayor was young, clean-shaven, and round-faced. His slight chubbiness could be explained by the many apple pies and pork ribs he had had to eat during his election campaign.
"The good people of Safetown want our fine city to live up to its name," he said. "As a candidate, I promised to make that happen and I intend to keep that promise. The crime rate has gone up and the citizens are demanding that the police cruise through the streets with greater regularity, especially at night. The police, in turn, complain that with all the strange one-way streets, they can't figure out a way to cruise efficiently.
"So they must all drive?" 12-year-old Liane asked.
"Yes, we have fine one-way streets that I intend to give high-quality maintenance to — in fact, I will raise the budget for asphalt laying by 30 percent..." He went on for a few more sentences but I don't recall them.
"In any case," he continued, "police go on their beats by car. We want them to drive down every street as often as possible. It takes about 1 minute to drive down one block."
"Well, let's see," said Liane, looking at the map in Figure 1. "Driving down each block every 16 or 17 minutes would be the greatest possible frequency, I think, given that you have 50 driving blocks. Shall we try for that?"
The mayor nodded and Ecco sat back as Liane started to draw.
Reader: Can you arrange routes for the police so each car goes through its entire beat every 16 or 17 minutes?
The mayor studied Liane's solution. "And such a pretty girl, too," he said as he pumped her hand. "It would be my great pleasure to present you with the key to the city. We could invite the high school marching band for the music and the Friends of the Police to make speeches. If we wait a year, I could use the event to announce my candidacy for Congress."
Eyebrows raised, Liane backed away slowly until she fell into a chair. She picked up her guitar and started to strum, slowly.
"So, I'll be calling you, young lady," the mayor said, pointing his finger at her. "And thank you, my fellow Americans." He left.
"Liane," Ecco said, after giving her a few moments to stare at the door, "suppose the mayor had five police cars. Can you arrange it so that at least one police car drives down any given street at least once every 10 minutes? If not, what frequency can you guarantee?"
I had to leave, so I never heard her answer.
Reader: Would you like to give it a try? Either send me a 10-minute solution or show that none can exist and then show me the best solution you can find. Note that it is not necessary for each car to perform a circuit of 10, just so long as every street is visited every 10 minutes.
Last Month's Solution
The naive way to solve this problem is to try all possible orderings of the B players, evaluate each one, and then determine the best ordering for Foxy. This is quite feasible for 9 players where the number of orderings is 362,880, but less so (even with quite speedy computers) when the number of orderings is about 15 trillion. So, we observe the pattern of 9 and try to extend it.
For 9 players, the following pairing:
A team B team
0 0
1 2
*2 1
3 5
*4 3
*5 4
6 8
*7 6
*8 7
yields 5 wins for B (against A players 2, 4, 5, 7, 8 as indicated by asterisks). The maximum loss for a B is 10 points (for example, A[6] versus B[8]) and the average point spread when a B player loses is 7.)
For 25 players, the following pairing yields 13 victories for B (just enough). The maximum loss for a B is 10 points and the average point spread when a B player loses is 6 1/3. The B wins at 0, 15, 16, and 23, 24 are all by two points.
A team B team
0 0
1 2
*2 1
3 5
*4 3
*5 4
6 8
*7 6
*8 7
9 11
*10 9
*11 10
12 14
*13 12
*14 13
15 15
16 16
17 19
*18 17
*19 18
20 22
*21 20
*22 21
23 23
24 24
Reader Notes on the Tundra Problem
The bad typo in the initial pipe layout of the print version of the Tundra problem (DDJ, February 2001) was due to a bug in my puzzle version control. Please accept my apologies. The web version of the puzzle has the correct initial layout. Fortunately, many brave readers tried to solve the problem anyway (often after sending me an "I am confused..." e-mail). The following clever ones obtained the optimal answer, which is the same as the one published in last month's issue: Dennis Yelle, Pike Enz, Rodney Meyer, Richard Stanford, Chad Harrington, Richard S. Fleischmann, Bruce Moskowitz, Bryan S. McDaniel, Jean-Philippe Langlois, Matthew Cuba, Geoffrey Probert, Randy Von Smith, Andrew Palfreyman, Jimmy Hu, Robert Sparks, Rick Cohan, James Larson, Conrad Schlundt, Phil Staite, Christopher Diggins, David Stevenson, John Trammel, and Paul Wagner.
DDJ
