Monopoles

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

Architect and space station designer Jordan Tyler was back. "You helped us so much with our layout problem for the workspaces in the space station, Dr. Ecco," he explained as he entered, "that we've come to ask for your help in designing the cargo ports."

Ecco acknowledged the praise with a nod, then, sweeping his arms in the direction of his 11-year old niece, he said, "Liane played a significant role as well."

"True enough," Tyler said, smiling at Liane. "I'm glad to find both of you again. Here's our new problem. The cargo we're going to take to space is unlike any that's been taken before: monopoles. They are constructed based on a physical principle that is still secret. I myself know only the effects.

"First, monopole triples of the proper polarities attract each other, much like the north and south sides of a magnet. Until a few decades ago, the very existence of monopoles was considered completely theoretical. It turns out, however, that there are many kinds of monopoles, in fact there are at least 52 of a special kind called "additive monopoles." We know this because Zoranics has manufactured them. (They claim that they are reaching a physical limit at 52, a limit that mathematician and gambler Larry Laing has dubbed the 'card-deck limit.' I personally am skeptical that there is any such limit.) Zoranics has given each kind of monopole a whole number label according to its properties: 1,2,3,4,...52."

"What does the labeling mean, exactly?" Liane asked, admitting the confusion we all felt.

"Good that you ask," Tyler answered with a smile. "Additive monopoles are so named because they exercise an enormous force of attraction if three of them, labeled X, Y, and Z, are in the same area as X+Y=Z. So, for example, the monopoles with labels 2, 5, and 7 will be attracted to one another. But 2, 5, and 6, will exhibit neither attraction nor repulsion. Nor will 2, 3, 4, and 9, because monopole attraction works only in triples. The attraction is so great that such a triple, once formed, is virtually impossible to break apart and is therefore useless to our mission.

"Fortunately, the attractive force of the monopoles can be blocked by a shield of titanium. So, we are going to partition our cargo of monopoles into separate rooms with titanium shields to avoid creating mutually attractive triples. That is, in each room, there must be no monopole triples X, Y, Z such that X+Y=Z.

"On the other hand, you can surely appreciate that we want to minimize the use of this precious and dense metal. Thus, our question: What is the smallest number of rooms you need if you want to send all 52 monopoles but only one instance of each?"

"Wait," Liane interrupted. "I need an example."

"Fair enough," Tyler said. "Suppose you were only allowed two rooms: A and B. Suppose you put the set of monopoles {1,3} in room A, and {2} in room B. Now, you can't put {4} in room A, because 1+3=4, so you have to put {4} in room B. On the other hand, 5 can go into room A, so you would get {1,3,5} in room A and {2,4} in room B. Unfortunately, you are now stuck. You cannot put {6} in either room."

Liane thought about this for a while and then said, "I see. Another strategy would be to put {1,2,4,7} in room A and {3,5,6} in room B. Then you get stuck at 8 rather than 6. Still, we are far from 52. I wonder how many rooms we'll need."

Liane and Ecco worked on this for a while. Liane came up with the first solution.

Reader: Her strategy used only four rooms. If you can match or better that, explain your strategy. Can you get more than 52 in your rooms?

"Thank you," Tyler responded. "Now, I must explain that we are not quite done. The space station directorate wants us to take pairs of each kind of monopole so we have spares. He says the mission is just too important. Further, the spare of each monopole should be in a different room from the original. That way, if any single room becomes damaged, we can collect all necessary monopoles from other rooms. Would we have to double the number of rooms to eight in that case?"

"Let me make sure I understand," Liane said. "With this restriction, if we had three rooms, the best we could do would be some configuration like this:

Room A: 2 3 4

Room B: 1 2 4

Room C: 1 3

Here, 5 could be put in room C, but no other room could accommodate 5. Is that right?"

"Exactly," Tyler said. "It's important that no room contain two monopoles of the same label."

Reader: Ecco and Liane think that eight rooms are required when two additive monopoles with the same label must go into different rooms. Can you do better?

Tyler was clearly unhappy with this answer. "We may be able to convince the directorate that damage to rooms is such a remote possibility that it is okay to put two additive monopoles with the same label in the same room," Tyler said. "How many rooms would you need in that case?"

"Just a minute," Liane said. "Let's do an example again. Suppose a room has monopoles 3,3,4. That is, two 3s and one 4. Now, if I want to put a monopole of 6, can I do that?"

"No," Tyler answered, "because 3+3=6. The rules remain the same. No X+Y=Z, even if X=Y."

How many rooms do you need if spares may go in the same room as the original and there is a full set (52) of spares? Describe your layout. Ecco and Liane were able to make do with just five rooms.

A few months later, Tyler came back. "Zoranics has broken the card-deck barrier," he said happily. "They can now produce the first 59 monopoles (1,2,3,...59). That's the good news. The bad news is that the directorate absolutely insists on putting spares in different rooms.

Reader: Ecco and Liane found a solution requiring nine rooms that could accommodate exactly 59, but no more. Can you do better (meaning that you could accommodate more monopoles in nine rooms or use fewer rooms for 59)? Remember that spares can't go in the same room as originals.

Last Month's Solution

Figure 1 illustrates the solution to last month's challenge regarding space station routes.

Solutions to the "Fitting" Problem

Clever readers found many solutions to the "Fitting" problem (DDJ, June 1999) of Rino Banti, because he forgot to tell Ecco that four rectangles should be included in the 16×16 geometric design. Even then, the solution is not unique. It looks as if the Venetians will have trouble recovering enough marble pieces to create a floor. Among the clever readers were Andrey Jivsov, Martin Brown, Jim Brannan, and Rodney Meyer.

DDJ