A riddle of ice and fire dragons - Henri Picciotto

It’s your first day in your new job as Center Realm’s official cartographer, and you've already got a big problem. Center Realm is home to three elder dragons: two ice, one fire, and they’ve lived in harmony on the east coast for centuries. But scouts have sighted three fire dragons and five ice dragons flying across the Western Ocean. You’ll only have a few hours to assign them their designated regions before they’ll arrive. Elder dragons are extremely territorial. Each must have its own, officially acknowledged stomping ground. They’ll peacefully roost there unless their region borders another dragon of the same type, in which case the matching dragons will go on a rampage.

However, fire and ice dragons can border each other, and matching regions can touch at corners. You’ll soon have 11 dragons and just 8 regions. Fortunately, you have enough political capital to create 3 new regions, each of which must be completely enclosed spaces. Add more or otherwise mess this up, and you’ll lose your job and your head. Where do you draw lines and place the new dragons? Pause here to figure it out for yourself.

Answer in 3. Answer in 2. Answer in 1. It isn't difficult to create three new regions. What is more challenging is to make sure the result will keep each dragon away from its own kind. For instance, this can be neither ice nor fire, because it borders both. However, create a new region like this, and suddenly there are viable options. Why did that work? Look at the point where these four regions meet. If you go around it, it alternates between fire and ice.

Before the new line was added, that wouldn’t have worked. Nor would 5 or 7 regions. 6 and 8, however, both do. The pattern is that points where lines meet must be surrounded by an even number of regions. As long as that’s true, you can color the map in two colors, by alternating them around those points. In our initial arrangement, there were six such meeting points. So what we want to do is connect those to each other. Each line adds a single new region that touches both meeting points. There are several ways to do this to accommodate all 8 new dragons.

You’ve done such a great job that your boss puts you in a ship and sends you out across the Western Sea to investigate where these new dragons are coming from. There you’re met with a civilization in disarray. Their 17 elder dragons are ravaging the countryside, wiping out the peasants, devastating all the people and their thatch-roofed cottages. And here there aren't just ice and fire dragons, but lightning dragons too. Their people will only allow the creation of two new regions. Where do you create new regions and place all the dragons? Pause here to figure it out for yourself.

Answer in 3. Answer in 2. Answer in 1. Unfortunately, our meeting-point trick won’t suffice now that there are three dragon types, so we need to find another method to identify problem areas. A great way to do so is to experiment: focus on one area and start coloring until we run out of possibilities. Take this section. These 3 regions all border each other, so they need to be different colors. But they also all touch this giant territory, which we now can’t color.

To generalize the issue, when there are 4 regions that all border each other, it's impossible to color them with three colors. The map has two other such areas. So what you need to do is break them up. And once again, the key is drawing lines between points where multiple problematic regions touch. No matter how you do it, you’ll effectively subdivide the giant territory into smaller ones. Now coloring the map becomes a logic puzzle.

So long as you approach it systematically by starting in one area and radiating out, you’ll reach an arrangement that you can fit all your dragons into, shifting the colors as needed. Just assign this region last, because it’ll have two options. You've saved not one, but two continents from certain ruin. Now to see if you can find a giant eagle and hitch a ride back home.