Can you solve the Trojan War riddle? - Dennis E. Shasha
The Trojan War has been raging for 10 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 10-day truce.
From high up on Olympus, you’ve been waiting for an opportunity to bring this bloody war to its conclusion. When you go to consult the Fates, they advise: should the peace last for a full 10 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 great 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 completely 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?
Pause here to figure it out yourself. Answer in 3. Answer in 2. Answer in 1.
The first insight here is to divide this into two sub-problems. There’s the matter of connecting 4 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 perimeter of the field 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 exactly 6 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 make a swap with their horizontal, vertical, or diagonal Greek neighbors that will break up the Greek connectivity.
Once again, you consult the Fates, who prophesize the following: the meddling Trojan camp is somewhere 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? Answer in 3. Answer in 2. Answer in 1.
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 in place, blocking Greeks from crossing. So we can thwart them by moving either one a column left into this square, and the same principle applies to the bottom arm. Your effort maintains the peace for the final 5 days. But it seems that a certain Greek general noticed what was happening and left the Trojans a parting gift...