Mates

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, 1997). He can be contacted at [email protected].

The tour leader Jimm Cody sighed. "When my father took city folk out on camping expeditions, he assigned people to tents, and they learned to get along," he said. "Now these baby boomers express their preferences for tentmates and make my life hell if I don't please them. My dad was lucky."

"Yeah, yeah," Liane said with her characteristic mockery. "Adults are always talking about the past like it was some great thing. Being forced to get along with some creep doesn't sound fun to me."

"Right," Ecco said, agreeing as usual with his 10-year old niece. "I'm pretty picky about my friends too. So, how do they express those preferences, Mr. Cody?"

"Well, we have this private ballot whereby they write down a score for other people on a scale of -12 to 12, where 0 is neutral," Cody answered. "There haven't been any negative numbers so far."

"Then what do you do?" Liane asked.

"Well, for this trip we have five tents altogether: one two-person tent, two three-person tents, and two four-person tents," Cody said. "Our job is to maximize total happiness. Given an assignment to tents, we reckon the happiness by adding up the scores each person holds for each other person in the same tent."

"I don't get it. Can you add stuff like that?" Liane asked Ecco.

Ecco shrugged.

"It seems to work," Cody said.

"When I tell them this method, them yuppies nod their head with a smile. You'd think they had just heard their VP of marketing tell them their market share or somethin'. Anyway, please understand that this table says how much a person values certain other people. For example, here you see that alan values olivia with a value of 7. If alan is in the same three-person tent as olivia and bob, then alan's happiness is 7+2 or 9, olivia's happiness is 0 since she has no opinion about bob or alan, and bob's happiness is 10. This gives a total of 19 for that tent group." (The following table is also available electronically, see "Resource Center," page 3.)

Person    Friend    Value

alan      olivia    7
alan      bob       2
alan      mike      1
alan      felicia   0
bob       jack      7
bob       olivia    10
bob       dave      0
carol     jack      11
carol     petra     0
carol     kris      2
carol     mike      3
dave      isaac     3
dave      nick      4
dave      felicia   1
dave      hillary   9
emily     dave      7
emily     bob       0
felicia   alan      4
felicia   olivia    10
felicia   isaac     7
felicia   gwenyth   3
felicia   petra     11
gwenyth   hillary   5
gwenyth   felicia   5
gwenyth   larry     1
gwenyth   emily     10
hillary   emily     8
hillary   gwenyth   12
hillary   mike      7
hillary   jack      6
hillary   carol     2
isaac     dave      10
isaac     larry     3
isaac     carol     3
isaac     alan      12
jack      bob       6
jack      nick      10
jack      carol     5
jack      larry     1
jack      olivia    3
kris      gwenyth   5
kris      hillary   5
larry     isaac     8
larry     dave      9
larry     hillary   3
larry     kris      10
mike      felicia   5
mike      jack      9
mike      carol     2
mike      larry     5
nick      bob       4
nick      carol     6
nick      alan      1
nick      isaac     1
olivia    mike      5
olivia    felicia   12
olivia    kris      5
olivia    nick      12
petra     kris      8
petra     emily     4
petra     olivia    11

"Maybe we can use a greedy method," I suggested. "Take people with the greatest mutual preference and put them together."

"Sounds plausible, Professor Scarlet," Ecco said, "but I think it needs some study." Ecco and Liane worked on the problem for awhile.

Then Ecco wrote some names in five lists, stood up and said, "Mr. Cody, I think you can give your yuppies a total happiness of 175 with the following tentmate arrangement."

Reader: Can you achieve a setup in which the total happiness is at least 175?

"Dr. Ecco, you've made my day," Cody said and shook Ecco's hand. He started towards the door, then paused and turned. "Just one thing. Them yuppies, being impatient and all, tend to tire of one another real quick. What if each expressed score goes down by four by the next night, making some of them negative? How do I arrange the tentmates in that case?"

Reader: What if everyone's expressed preferences goes down by four after the first night (possibly making some values in the table negative). What is a setup that can get a happiness of at least 90 after that?

Last Month's Solution

When Solo can take three initially: Solo's hovertanks should occupy 24, 14, and 5. Those hovertanks can then fire upon everything else, preventing the adversary from taking any hills.

When Solo can take two initially: He should occupy 14 and 5. The adversary can then occupy only 10, 13, 20, or 0. If they occupy 0, Solo takes 10 and they can do no more. At which point, Solo can take 4, 6, 11, 12, 15, 21, and 23, giving him 10 in all. Similar reasoning applies if the adversary takes 10, 13, or 20.

Why the giggling and the nap? The basic configuration of the hills appears to be built from two chessboards, one 4×4 and one 3×3. Fire-upon relationships are then constructed like queen moves. This doesn't hold completely, but close enough to lead to solutions.

Reader Notes

Some of DDJ's super-intelligent readers have bested even Dave Weiblen's score for the territory game (April 1998). Kent Donaldson has a solution that gets 66.6 percent with six ships and 73.83 percent with seven ships. Hermann Klier has the current record with 73.86 percent for seven ships:

Ship 1  205 563
Ship 2  376 214
Ship 3  415 901
Ship 4  530 275
Ship 5  581 458
Ship 6  817 743
Ship 7  819 743

Finally, Howard R. Cole of the USU Research Foundation has offered his Differential Evolution code for finding near optimal solutions -- he found 72.4 percent for seven ships. Find his program at http://cc.usu.edu/~edx/territory.html.

Ecco's solutions for Nimmerics (May 1998) were optimal, and several readers came up with the right solutions. Marv Allison has an interesting general variant on the game: There are i piles of stones. Each player can draw up to j counters from up to k(k<i) piles. He solved classic Nim in this context. I look forward to publishing the web page of a solution to expanding Nim in this context.

DDJ