My Enemy's Enemy

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

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