Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

My Enemy's Enemy


Dec99: Dr. Ecco's Omniheurist Corner

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


He introduced himself only as Henry. "It is our policy, the policy of the government of the United States that is, to eliminate all unnecessary wars on the planet," he said in a pure Connecticut Yankee accent. "On the other hand, we want to avoid expending ourselves in regional conflicts, as we did all too recently in the Balkans.

"Our goal, therefore, is to maintain the peace where it exists and establish it when it doesn't. Such is the role of the global superpower.

"In the difficult island of Aresia, there are 27 ethnicities. All are proud and warlike. They seem to obey the following rules of friendship (which I use interchangeably with alliance in what follows):

1.(nonneutrality) I am either the friend or enemy of everyone else, but not both. If someone is my enemy, then I am his (her/their) enemy.

2.(transitive and reflexive) My friend's friend is my friend and I am my own friend.

3.(expediency) My enemy's enemy is my friend.

"Our first question is: How many different allied groups can there be at any given time?"

Reader: Before reading on, can you decide how many groups of friends there can be? Not their sizes, just how many groups?

Ecco turned to Liane. She began thinking aloud: "Let's see. By 2, friends are transitive. By 1, groups of friends partition the space and friendship is symmetric. By 3, there can be only one or two partitions. If there were three, say A, B, and C, then they would all mutually be enemies, but then A and C would be friends, because they are both enemies of B. So, this cannot happen."

Henry looked at Liane, still an 11-year old kid in her pony tail. "You are a national asset," he said appreciatively. "Is there any limitation on the number that can be in each group?"

"No, all numbers seem to be possible," Liane said. "1 and 26, 2 and 25,..., 27 and 0."

"27 and 0 means all friends, right?" asked Henry. "That is our ultimate goal, though I think it will be tough. These people have been at each other's throats for centuries."

"We have marked the current alliances on the map (see Figure 1). You can see that 2, 8, 9, 15, and 20 are in the Red alliance. All the rest are in the Blue alliance. This is temporarily stable because each group has either the sea or an ally on at least one side. We must avoid having a group surrounded by its enemies, because that would lead almost inevitably to war. (It's lucky that the place is an island. The seaside groups rarely have to worry about being attacked.) Our goal is to make everyone an ally by changing the alliance of one group at a time, while always avoiding the possibility that a group is surrounded by enemy groups. Since changing the alliance of a group is difficult and expensive, we want to do this as few times as possible.

"One of our mathematicians has suggested that achieving our goal at minimum cost should never require forcing a group to change alliances twice. What do you think of that conjecture?"

Ecco and Liane conferred for a while, then they responded.

Reader: What do you think?

"How interesting," said Henry. "Well, with that in mind what is the smallest number of alliance changes we must force in order to achieve our goal? Remember the caveat: Never leave a group surrounded by a hostile alliance on all sides."

Reader: Ecco and Liane were able to do this by changing nine group alliances all together (without leaving a group surrounded by its enemies). Can you do better?

"Nicely done," said Henry. "Some of our analysts think that the difficulty of changing a group's alliance is proportional to the group's population times the ratio of the source alliance's population to the target alliance's population. Here is a list of the populations on Aresia.

1 56727
2 77232
3 105454
4 50660
5 65707
6 24692
7 82943
8 61871
9 17781
10 21708
11 61758
12 50790
13 169466
14 82659
15 95675
16 63247
17 104643
18 144026
19 93559
20 53964
21 78913
22 155511
23 92888
24 90596
25 64713
26 105709
27 101417

Total reds initially: 288,742

Total blues initially: 1,885,567

Total: 2,174,309

For example, if I want to change region 8 from red to blue, the difficulty is 61,871× (288,742/1,885,567). The ratio reflects the fact that changing from the minority alliance to the majority alliance is much easier than vice versa, because citizens like to switch to the richer team. Given this notion of difficulty, which groups should we force to change alliances to guarantee peace (everyone allied) at minimum difficulty.

Reader: What strategy would you propose and what would the difficulty be? Ecco was able to find a strategy having a difficulty of less than 426,000. Remember that at no time should one group be surrounded on all sides by hostile groups.

Henry looked at the solution. "How curious! Groups on the periphery can carry out a much more consistent alliance policy. Maybe you've discovered a new truth of geopolitics."

Last Month's Solution

1. Ecco believes five gourds is the minimum because a gourd can empty at the fastest only once in five minutes. Therefore, a single gourd can only mark five-minute intervals. To mark minutes, therefore, five gourds are needed.

2. Here is the beginning of the procedure. Call the gourds by letters and have one assistant open stops on one or two holes as necessary to meet the times stated:

A: 5 5 5 5 5 5 5 5

B: 5 5 5 5 5 5 11

C: 5 5 5 5 11 11

D: 5 5 11 11 11

E: 11 11 11 11

Once this initial part of the procedure is over, the ceremony can start. Each calabaza is filled when it becomes empty and both holes are left open. So, A will mark 40, 45, 50, 55,... B will mark 41, 46, 51, 56,... and so on up to E, which will mark 44, 49, 54, 59,...

3. No n is troublesome. If n is even, then the integer below (n/2) -- call it m -- is odd (=(n/2)-1). It is always possible to build a procedure having m rows (gourds), in which one row has only ms, one row has one n and the rest ms, and so on until there is one row with m-1 ns and no ms. For example:

A: 20 20 20 20 20 20 20 20 -- 160

B: 20 20 20 20 20 20 20 9 9 -- 158

C: 20 20 20 20 20 20 9 9 9 9 -- 156

D: 20 20 20 20 20 9 9 9 9 9 9 -- 154

E: 20 20 20 20 9 9 9 9 9 9 9 9 -- 152

F: 20 20 20 9 9 9 9 9 9 9 9 9 9 9 -- 159

G: 20 20 9 9 9 9 9 9 9 9 9 9 9 9 9 -- 157

H: 20 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 -- 155

I: 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 -- 153

If n is odd, then m is even. A similar strategy works. For example, if n=21 and m=10:

A: 21 21 21 21 21 21 21 21 21 -- 189

B: 21 21 21 21 21 21 21 21 10 10 -- 188

C: 21 21 21 21 21 21 21 10 10 10 10 -- -187

D: 21 21 21 21 21 21 10 10 10 10 10 10 -- -186

E: 21 21 21 21 21 10 10 10 10 10 10 10 10 -- 185

F: 21 21 21 21 10 10 10 10 10 10 10 10 10 10 -- -184

G: 21 21 21 10 10 10 10 10 10 10 10 10 10 10 10 -- 183

H: 21 21 10 10 10 10 10 10 10 10 10 10 10 10 10 10 -- 182

I: 21 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 -- 181

J: 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 -- 180

Solutions to the "Monopoles" Problem

The following clever people all improved on Dr. Ecco's solution for the "Monopoles" problem (DDJ, September 1999): Jon Beal, Rodney and Jialin Meyer, Steve Hammer, Richard Lipp, Greg Smith, Pearl Pauling, Ernst Munter, Paolo Friedli, Dennis Cumro, Jean-Francois Halleux, Burghart Hoffrichter, Steve Kietzman, Gene Wagenbreth, Patrick Schonfeld, Tomas Rokicki, Michael Vielhaber, Tom Dinger, Russ Williams, and C. Mark Yendt, and Onno Waalewijn.

The best solution for four rooms with a single monopole per room was 66 monopoles altogether as shown first by Ernst Munter with the solution:

room 1: 24 26 27 28 29 30 31 32 33 36 37 38 39 41 42 44 45 46 47 48 49

room 2: 9 10 12 13 14 15 17 18 20 54 55 56 57 58 59 60 61 62

room 3: 1 2 4 8 11 16 22 25 40 43 53 66

room 4: 3 5 6 7 19 21 23 34 35 50 51 52 63 64 65

Others who showed that 66 were possible include: Ernst Munter, Paolo Friedli, Steve Kietzman, Gene Wagenbreth, Tomas Rokicki, Paolo Friedli, Michael Vielhaber, and Tom Dinger.

Tom Dinger also proposed a recursive construction, which I closely paraphrase, though it is suboptimal: Take a maximal assignment for n rooms, call it M(n). For n=1, the maximal assignment is room: 1 2. Double all the values of the monopoles in the rooms; this will not cause a violation of the problem constraints for those rooms. This results in n rooms, with the even numbers 2..2×M(n) properly assigned. Now, in the one additional room, place the odd-numbered monopoles 1..(2×M(n)+1). This room also satisfies the constraints, because the sum of any two of the monopole values in that room will be even, but no even numbered monopole is in that room.

Problem 2 required putting at least 52 monopoles plus 52 spares in some number of rooms without putting a monopole and its spare in the same room. The following readers showed that seven rooms (not the obvious eight) were enough: Bart Massey, Paolo Friedli, Tomas Rokicki, Tom Dinger, and Onno Waalewijn. Bart Massey was able to fit 65 monopoles with spares in those rooms. Here was his design:

room 1: 1 3 5 10 14 16 18 20 22 29 31 44 48 50 52 56

room 2: 2 8 12 13 16 27 32 33 38 42 52

room 3: 1 3 5 7 9 11 13 15 17 19 21 23 25 29 35 37 41 43 45 47 49 53 55

room 4: 24 28 30 31 32 33 34 35 36 37 38 39 40 42 44 45 46 48 49 50 51 53

room 5: 4 6 8 9 11 21 23 24 26 39 40 41 56 57 58 59

room 6: 2 6 10 18 19 22 26 27 30 34 43 47 51 54 55 58 59

room 7: 4 7 12 14 15 17 20 25 28 36 46 54 57

In problem 3, spares were allowed to be in the same room as the original monopole, but the monopole constraint (no two monopoles, even those with the same value, added together could equal the third) still held. Nobody gave a correct solution with fewer than five rooms. Tomas Rokicki was able to put 123 monopoles in those five rooms -- an admirable achievement.

DDJ


Copyright © 1999, Dr. Dobb's Journal

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.