# The Trojan War Riddle

On Olympus, you’ve been waiting for an opportunity to bring the bloody Trojan War to its conclusion. The two sides have agreed to a brief truce, and when you consult the Fates, they advise: should the peace last for 10 days, all will end soon. But if the truce is broken, there will be 10 more devastating years of war. Can you help the Greeks and Trojans keep the peace? Dennis Shasha shows how.

### Transcript:

The Trojan War has been raging for ten years, with neither Greeks nor Trojans prevailing. Gods and humans alike are desperate for a break, so when a divine omen races across the sky, the two sides agree to a ten-day truce.

From high up on Olympus, you’ve been waiting for an opportunity to bring this bloody war to its conclusion. When you consult the Fates, they advise: should the peace last for a full ten days, all will end soon. However, if the truce is broken, the ensuing battle will lead to 10 more devastating years of war.

The Fates’ loom has shown them the exact conditions that will keep the truce intact. The excellent Trojan plain can be viewed as a grid of Greek and Trojan encampments. If they’re organized in such a way that any Greek can reach any other Greek camp without having to pass through a Trojan camp, and likewise for Trojans, plus neither side surrounds the other, peace will prevail. Anyone can move to a horizontally or vertically adjacent camp, but never diagonally.

The problem is, they’re currently arranged like this.

Tonight, you can use your powers to swap up to six pairs of camps that are horizontally, vertically, or diagonally adjacent. No camp can be moved more than once.

Which swaps do you make to keep the peace?

The first insight here is to divide this into two sub-problems. There’s the matter of connecting four clumps of Greeks without putting holes in the Trojan line. And then there’s dealing with the thorny center space.

Let’s consider the Greeks first. To connect any Greek clumps, you’ll have to mess with the nice, straight Trojan lines. If you try to do that anywhere in the center of these arms, you’ll create new isolated clusters of Trojans. So the only option is to go to the field’s perimeter and move some Trojans diagonally, say here, here, and here.

Now for the center. There’s no way to connect the Trojan arms without swapping a Trojan in. But continuing to shift that arm of Trojans inward would require moving the same Greek camp multiple times. However, you could shift the whole Trojan arm up and to the right, closing this gap. There are several solutions with slight variants, but as long as you perform this maneuver on the short arm of Trojans, you can achieve peace in precisely six moves.

You make the swaps, and all is well until the fifth night. One of your rival gods wants to see the bloodshed continue and has taken advantage of a forgotten prophecy. He’s convinced one Trojan camp to swap with their horizontal, vertical, or diagonal Greek neighbors to break up the Greek connectivity. Once again, you consult the Fates, who prophesize the following: the meddling Trojan camp is within four grid spaces of the perimeter of the battlefield. They won’t go through with a swap if it only breaks up Trojan connectivity. And finally, you can make at most two swaps with the same rules as before to thwart them.

Which swaps do you make to block the troublesome Trojan camp?

You won’t be able to identify the scheming camp precisely, but there’s a lot you can do to at least narrow down the options. They have to be somewhere in this area. And they have to be able to block Greek camps from each other in a single swap. That doesn’t leave many options; the only possible blockages are at the end of these two arms, where a Trojan camp could plug a hole without opening a new one. So they must be in one of these four camps.

Let’s look at the right arm first. There’s a threat here because this column has two Trojan camps. If one moves to the right, the other will still be blocking Greeks from crossing. So we can thwart them by moving either one column left into this square. And the same principle applies to the bottom arm.

Your effort maintains the peace for the final five days. But it seems that a particular Greek general noticed what was happening and left the Trojans a parting gift…

### Ali Kaya

This is Ali. Bespectacled and mustachioed father, math blogger, and soccer player. I also do consult for global math and science startups.