Solving the Roman Legions Problem
To review the Roman Legions problem as outlined in the June issue of Hopkins Magazine, a region was secured if it already had a pebble (six legions) within its borders. Alternatively, a region was securable if a pebble could reach the region in just one step, and that could occur only if somewhere, within one step of the region, there were one or more places that had two pebbles garrisoned. That is, a pebble could only be "launched" to its destination by another pebble.
The question I asked was what other deployments of four pebbles, besides (2-R, 1-B, 1- AM), exist for this modified network that will protect the entire empire. I also asked whether any of these deployments could do better than (2-R, 1-B, 1-AM) if a second war occured somewhere else on the network. You remember that Constantine's deployment placed two pebbles at Rome and two in Constantinople. This positioning left Britain four steps away from help although all seven other regions either had a pebble at them already or were within one step of assistance. The 8-region Roman Empire is shown in Figure 1.
It turns out that there are a number of deployments of four pebbles that cover all eight regions. Whether or not they would be chosen, however, becomes a matter for discussion. I have listed below six different deployments of four pebbles all of which cover all eight regions either in one step or by initial placement. That is, in each deployment no region is more than one step away from assistance.
The deployments are:
2) 2 pebbles Iberia, 2 pebbles Egypt
3) 2 pebbles Iberia, 2 pebbles Constantinople
4) 2 pebbles Iberia, 2 pebbles Asia Minor
5) 2 pebbles Gaul, 2 pebbles Egypt
6) 2 pebbles Rome, 1 pebble Britain, 1 pebble Asia Minor
This leads to a second measure against which to measure the goodness of a deployment--the maximum number of regions that might be left unprotected if a second war occurs. This is calculated in the following way. Assume one of the six deployments listed above has been chosen. We will be testing that deployment under all possible first war scenarios. One region at a time, assume a first war occurs in a region which presently has no pebbles. Dispatch a pebble to the war from the two-pebble region which is one step away. Now look at the remaining regions which presently have no pebbles. How many of them could not be reached in a single step by remaining resources? Record this number. Repeat this for all possible first war locations and, for each first war location, record the number of regions which cannot be reached in a single step in the event of a second war. Considering all possible first wars, what is the maximum number of regions that can't be reached? Record this number. Repeat this analysis for all six possible initial deployments.
I have tabulated the results:
Options (3) and (5) assume that when a first war can be covered by a pebble from one of two places, the choice of which pebble to deploy will maximize regions protected in a second war. The calculation of the maximum number of regions unprotected in a second war requires you to make the best possible choice of node from which to dispatch a pebble to quell a rebellion or repel an invasion.
Constantine's strategy, although it left Britain unable to be secured in a single step, left only three regions unsecurable in a single step in the event of a second war and just two if you have already written Britain off. Why did Constantine choose the strategy he did? We can guess that he could not abandon Rome and that the only strategy that covered all the regions and included Rome (strategy 6) left four regions uncovered in the event of a second war.
On the other hand, there are six other options not far different in goodness from the strategy Constantine chose. Ken Rosing of Erasmus University and I found these by applying a mathematical model, but you can easily verify their levels of achievement. Remember that in Constantine's strategy, two pebbles were at Rome and two at Constantinople, leaving Britain four steps from help.
A comparable mirror image strategy to Constantine's choice is two pebbles in Rome and two pebbles in Gaul. This strategy covers all but Asia Minor in one step, but leaves Asia Minor four steps from assistance (just as Britain was four steps from aid in Constantine's choice). Another strategy is one pebble in Iberia and one in Asia Minor with two pebbles in Rome. Once again, Britain is lost.
We have found eight second level strategic options so far and there may be more that protect seven of the eight regions. We now compare these second level strategic options. They are second level in the sense that even at the outset one region cannot be reached in one step. They may, however, do well in the event of a second war, as you can see from the table. This table includes all options we have explored so far, although others may be found.
I rather prefer options (8) and (10) to Constantine's solution (7) since of the seven regions covered only one will be uncovered at maximum in the event of the second war.
As you can see, the problem has riches to mine.
GO TO CAN YOU PROTECT THE ROMAN EMPIRE? (April 1997)
GO TO TEST YOUR SOLUTION TO "CAN YOU PROTECT THE ROMAN EMPIRE?" (June 1997)
RETURN TO SEPTEMBER 1997 TABLE OF CONTENTS.