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].
The sunglasses, beach shirt unbuttoned to expose his well-fed belly, and golf tan should have given him away. Joe Rouge was a movie producer. He had bought into his first movie after making a killing in fast-food real estate.
"You gotta see it to believe it, Doc" he said to Ecco, waving his unlit cigar around for emphasis. "These expensive actors just sit around most of the time at these movie sites. They're not rehearsin', they're sitting watching a scene get set up that they're not even in. Now, I'm no mathematician, but I got to thinkin': Can't we move them around so they don't waste so much time and so I don't gotta pay them? I asked my nephew Gary here to help me out, but he seems to think that only you can solve the problem right. This movie is costing me a bundle. If you can reduce the expenses even by a million, I'll pay you handsomely."
Gary -- pale, stick thin, his narrow shoulders hunched forward slightly -- stood up and spoke in a soft voice. "Here is how it works. Actors in our studio are paid by the day. The three stars -- Patt, Casta, and Scolaro -- are paid exceptionally well, several hundred thousand dollars a day, in fact. Each of the 19 scenes requires its own cast and setting up a scene and shooting all its takes takes a long time. So, we figure five scenes a day. We are filming in one location (a cushion-rich mansion, if you get my drift) fortunately, so the scenes can be ordered any way you want."
"The crew will be on scene all the time and at the same expense?" Liane asked.
Gary seemed startled at the sound of the 11 year-old girl, but answered, "Yes, the crew cost and equipment rental is constant but very high, about $10,000 per hour, in fact."
Gary paused, as if unsure of what to do next. Rouge tapped his cigar impatiently on the edge of a chair. Liane spoke up, "Gary, could you tell us the current order and composition of the scenes and then the daily rates of the actors?"
"Yes, of course," Gary replied, reaching into his suitcase. "Here are the actors in each scene, one line per scene, listed in the order of the script:
Hacket
Patt Hacket Brown Murphy
McDougal Scolaro Mercer Brown
Casta Mercer
Mercer Anderson Patt McDougal Spring
Thompson McDougal Anderson Scolaro Spring
Casta Patt
Mercer Murphy
Casta McDougal Mercer Scolaro Thompson
Casta McDougal Scolaro Patt
Patt
Hacket Thompson McDougal Murphy Brown
Hacket Murphy Casta Patt
Anderson Scolaro
Thompson Murphy McDougal Patt
Scolaro McDougal Casta Mercer
Scolaro Patt Brown
Scolaro McDougal Hacket Thompson
Casta
"Here are the daily rates of each actor:
Patt: 264810
Casta: 250430
Scolaro: 303100
Murphy: 40850
Brown: 75620
Hacket: 93810
Anderson: 87700
McDougal: 57880
Mercer: 74230
Spring: 33030
Thompson: 95930
"This gives the following total expense (excluding the crew): $4,975,360. With the crew, the expense is over $5 million." Gary paused, then looked over his shoulder at Mr. Rouge, who was distracted from these technical details. "This is a very B movie, please understand," Gary whispered. "$5 million is really too much."
Ecco studied the figures while munching on an oatmeal cookie. "Mr. Rouge, we'll have to study this for a day," he said. "Could you come back tomorrow?"
"Really?" Rouge asked, thinking he detected a note of reluctance on the part of Ecco. "Doc, whatever you save me from the $5 million, I'll pay you 10 percent of that amount." He looked at Ecco, searching for some sign of greed.
"That's fine," said Ecco, with a friendly grin. "Until tomorrow then."
We came in the next day and Rouge barely greeted us. "What did you find out Doc?"
"Tell him, Liane," Ecco said.
"Well, Mr. Rouge," she said, presenting a piece of paper to the producer, "We can save you over $1,450,000 dollars with the following organization."
Reader: Can you do as well or better? If so, how would you order the scenes?
"That's great, Doc," said Mr. Rouge. "How much did I say I'd pay you?"
Last Month's Solution
In 1 and 2, the conjecture is wrong. It is better to force two changes of alliance sometimes; for instance, change 13, 21 to red, then change 2, 8, 9, 15, 20, 13, 21 to blue. That gives only nine changes. There are many other possibilities.
In 3, Ecco's solution was to convert 9, 10, 6 to red (from smallest populations to greatest since later conversions have less of a ratio multiplier) and then to convert 2, 8, 20, 15, 9, 10, 6 to blue. The second set of conversions are best done from most populous to least since the blue alliance costs less and less to convert to as it gathers groups.
Reader Notes on the "Inheritance Puzzle"
The following readers matched Ecco and Liane's solutions to the "Inheritance Puzzle" (DDJ, October 1999): Greg Smith, Onno Waalewijn, Tom Dinger, Patrick R. Schonfeld, and ALan E. Dragoo. Their answers included good arguments for why Ecco and Liane's solutions are probably the best possible.
Richard W. Lipp noted "...what I find most intriguing is that it is more complex than initially apparent. I have not had a lot of time to address this one, but the time I have spent has produced spectacular failures." He then went on to describe heuristics that stubbornly refused to work. It's tough to be an heir.
DDJ
