Subway

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), 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].

Police commissioner Bratt returned. His entourage this time consisted of only two individuals whom he introduced as "my colleagues Kris and Joe."

What a pair! The young woman's snug black dress, silky black hair, black beret, and dark sunglasses set off her bright red lipstick. She tilted her head slightly as a greeting, then sat down lightly on a chair without relaxing her posture. The man wore jeans held up by a toolbelt strung with a flashlight, a measuring tape, and a set of screwdrivers. His fingernails showed stains of machine oil. He sat heavily into an armchair, visibly exhausted. Then he pulled a pad out of his back pocket.

"Joe here is a subway engineer," Bratt explained. "In some ways, he is the subway engineer for our great city in that he makes sure the trains run on time."

"To the extent they do at all," Joe said with a disarming smile.

"Kris is, well, let's say a strategist," Bratt went on.

Liane spoke up, her voice laden with sarcasm: "Versace, aren't they?" she said pointing to Kris's sunglasses.

"That's right, Liane," said Kris turning her head towards the 10-year old. "They also contain directional listening devices. I can pick up conversations at 50 feet on a crowded train or in the bar of a hotel."

Liane staggered backwards a few steps, her eyebrows raised.

Kris followed Liane with her shaded gaze and continued, "You and your uncle helped the commissioner greatly in his drug-fighting efforts. You even helped convince him that I was an honest informant...though he prefers nonmathematical methods of determining honesty."

I could just imagine.

"Now, we need your help to solve a problem of, well, distribution. Will you help us?" Kris asked, still looking at Liane.

"Sure," said the young girl, far from recovering her composure. "Anything you want."

"Absolutely anything," Ecco added with a smile.

"Very well," said Bratt. "Joe, please show the map."

Joe spread out a map for us. "The Midtown stops of the subway resemble a grid and spread from upper Brooklyn to lower Queens and midtown Manhattan," he explained. "I'm abstracting slightly, but topologically, it's a 5×5 grid with a few extra lines. Each line represents a pair of tracks. For concreteness, number the stations from (0;0) in the top left corner to (4;4) in the bottom right, as you see in the figure.

"At each end station (the 25 around the periphery), a train begins at 6 am except that the horizontally moving trains starting at (2,0) and (2,4) begin at 6:20 am. At 6 am, there is a lot of activity in the corners. Three corners have three trains leaving at 6 am each, one horizontally, one vertically, and one diagonally. The northwest corner has four trains leaving at 6 am. Train stations are 10 minutes apart. It takes 10 minutes for a person to switch trains at a station. Trains turn around at the terminus stations in negligible time.

"You notice the diagonal lines and the line I've drawn with dashes. Trains go slightly faster on those lines in order to maintain the 10-minute station-to-station pace. The dashed line between (0;0) and (2;4) hits stops at (0;0), (1;0), (2;0), (3;1), (3;2), and (2;4). It's our best line, by the way. It runs at 30,000 volts higher than the other lines to conserve power and the brake voltage..."

"Thank you, Joe," Bratt interrupted. "Now, Dr. Ecco, let me lay out the scenario. Suppose a nasty person could start at any station he desired and wanted to deposit, well, smelly postcards in as many stations as possible in as short a time as possible..."

Kris took over, "How long would it take that person to drop postcards off at eight stations assuming he started at 6 am?"

"Including the starting station?" Liane asked, forgetting her nervousness now that a puzzle was posed.

"Correct, Liane," Kris replied.

"Well, then he could start at 6 am at station (0,0) and drop a postcard there, then go to (1,0), (2,0), (3,1), (3,2), and (2,4), dropping cards as he went. That takes 50 minutes. Then he could switch to the train that started at (0,4) and went down, but is now on its way back up. After 50 minutes, it's at (3,4). It takes him 10 minutes to switch, so he'd be on it at 60 minutes and would be able to go to (1,4) and (0,4) in the next 20 minutes. That makes seven stations in 80 minutes."

"Nice job, girl," said Joe, smiling with delight. "We've come to the right place."

Kris continued, "Right, except we knew that answer. Here's one we don't know. How long would it take a nasty person to drop postcards off at 13 different stations (12 besides the starting station)? You can start at any station and at any time."

Reader: Liane found a solution that worked in 150 minutes. Give it a try.

This time I thought I saw Kris smile, but it was fleeting. Bratt went on to the next question. "Suppose, the person targeted 19 stations. Can he do that in under 300 minutes?"

"Quite a bit under," said Ecco after a few minutes thought. "Here is how."

Reader: Can you have the nasty person hit 19 stations in 250 minutes or better?

Lifting his head up from the notes he was taking, Joe asked, "What is the maximum number of stations that two nasty people can distribute postcards to in 80 minutes?"

"I would say at least 15," said Ecco. "Liane, what do you think?"

Reader: Liane thinks 16 may be more like it. What do you say and how would you do it?

After staring at the sheet of paper in silence for a while, I volunteered a new observation, "Hmm. And five nasty people can make all your subways stink in less than an hour."

Reader: Show how (this one is easy).

After listening to my explanation, Joe went over his notes. Then he turned to Bratt. "Commissioner, we have a big problem. Teams should be ready at every stop."

Last Month's Solution

Liane solved the first problem in 10 reversals.

start: mhtvkllcvvfsclcavawasshrqpchsp

( 7;19;"mhtvkllawavaclcsfvvcsshrqpchsp")

(11;27;"mhtvkllawavhcpqrhsscvvfsclcasp")

(15;21;"mhtvkllawavhcpqvvcsshrfsclcasp")

( 0; 9;"awallkvthmvhcpqvvcsshrfsclcasp")

(14;24;"awallkvthmvhcpcsfrhsscvvqlcasp")

(16;19;"awallkvthmvhcpcsshrfscvvqlcasp")

( 6;19;"awallkfrhsscpchvmhtvscvvqlcasp")

( 3;22;"awavcsvthmvhcpcsshrfkllvqlcasp")

( 5; 8;"awavchtvsmvhcpcsshrfkllvqlcasp")

( 7;19;"awavchtfrhsscpchvmsvkllvqlcasp")

Ecco's solution alternated between reversals and rotations, but worked in eight days.

start: mhtvkllcvvfsclcavawasshrqpchsp

( 9;23;"mhtvkllcvrhssawavaclcsfvqpchsp")

( 3;16;"mhtvvawasshrvcllkaclcsfvqpchsp")

( 8;17;"mhtvvawaakllcvrhssclcsfvqpchsp")

( 9;29;"mhtvvawaakpshcpqvfsclcsshrvcll")

( 4; 6;"mhtvwavaakpshcpqvfsclcsshrvcll")

( 9;22;"mhtvwavaaksclcsfvqpchspshrvcll")

( 3;11;"mhtcskaavawvlcsfvqpchspshrvcll")

( 8;11;"mhtcskaavvwalcsfvqpchspshrvcll")

Reader Notes

Some smart DDJ readers did quite a bit better than Ecco and Liane for the options problem in the "Getting Even" puzzle (September, 1998). The basic framework these readers used was the same as Ecco's: If Fred's initial position is p, have Fred flip until he reaches p+$115,000; p-$115,000; p+$125,000; p-$125,000; and so on up to p+$395,000 and p-$395,000 or until he gets in bounds. There are 60 positions to search for. On average, he will have to explore 30 of them before getting within bounds. By aiming for each target individually, that would require an expected 60 flips. Ecco took advantage of the fact that even when Fred misses a target, he may hit another. The problem was that Ecco's solution failed to take advantage of the fact that one should choose target points carefully so that they have this property.

Using Wesley Perkin's terminology (he was the first to find this), given a target position p that one has reached, see whether p has live neighbors. Two neighbors n1 and n2 of p are live if they are both targets, have not yet been tested, and n1-p=p-n2. In that case, Fred bets p-n2; the result of that bet will lead to a target no matter what. If p has no live neighbors, then choose as the next target some position that does. The algorithm can be further improved if you go for targets whose live neighbors have live neighbors, and so on. The net effect is that you can solve the $5000-spread problem in under 37 flips on average. Using Ecco's original method required over 55 flips and led to big losses more often. (When inbounds meant within $1000, the number of flips declined from 260 to just over 150. The probability of going under $10 million declined from 70 percent to about 30 percent, and the probability of going under $1 billion declined from 4 percent to about 1 percent.)

I've posted Ecco's original solution (even.k) and the solution of these smart readers (evenbetter.k) on the Kx system web site http://www.kx.com/.

Other readers who found similar solutions include Charles Taylor, John Hadreas, and Onno Waalewijn.

Steve Worley volunteered a related problem: You owe $X. You want to get back to owing $0. You flip a fair coin with any positive integer-sized bet. You lose if you exceed a debt of $M...the other guys get fed up and break your legs or something. The question is, with a current debt $X and maximum debt $M, what is the probability you'll be able to get back to $0 with a fair coin? The surprise is that P(X) is the simple linear function 0.5×(1+(M-X)/M). Your strategy is simply to bet $M if you're at a debt of $M, or bet the smaller of $X and ($M-$X).

DDJ