The Monster Garden

Question

You are the praetor of Tri, a small triangular-shaped nation bordered on the northwest by the Kingdom of Sauria, on the northeast by the Sultanate of Avia, and on the south by the Republic of Cryosta, as shown below.

                                 

Tri is divided into 25 small triangular provinces as shown, each of which has a bustling peasant town at its center. There are also 21 empty monster dens in Tri, which are located at its three outermost corners and at 18 points where the provinces converge (shown as red dots).

In an attempt to boost your flagging economy, you've accepted an enormous sum of gold from your neighbour nations to import 21 of their unwanted monsters, which you plan on placing into your 21 dens (1 monster per den).

The three types of monsters you can import are:

1. fire-breating dragons
2. man-eating gryphons
3. giant trampleodons

You can import as many of each monster as you want, but your neighbour nations have placed some restrictions on where certain monsters can be placed:

• Sauria can only deal with reptilian-type monsters, hence no gryphons may be placed in any of the dens on the border with Sauria
• Avia's terrestrial gardens are laid waste by trampleodons, hence they refuse to allow any trampleodons to be placed in dens on the border with Avia
• Cryosta's buildings are mostly constructed of thatch glued together with paraffin and animal fat, hence no fire-breathing dragons may be placed in dens on their border

Additionally, while the citizens of any one province in Tri can raise arms to defend against one or two types of monster, defending against three types of monsters would overwhelm them. Hence you've resolved that no province may have monsters of all three types in the three monster dens adjacent to it.

Because of these rules, you know that a dragon must go in the northernmost den, a trampleodon must go in the southwesternmost den, and a gryphon must go in the southeasternmost den, but it's up to you to assign monsters to the remaining 18 dens.

Can you meet the demands? Are you up to the challenge?

Respondents are politely encouraged to place answers (i.e. spoilers) in spoiler blocks, so as not to spoil the fun for other puzzlers. :)

Answer 1

This is just Sperner's Lemma.

Sperner's Lemma is a mathematical theorem that says that no arrangement can satisfy the criteria in the question. More exactly, it says that if you:
- Divide up a triangle into smaller triangles (in any way!).
- Colour the points of the diagram with three colours.
- Arrange your colouring such that each colour is "banned" from one of the sides of the big triangle.
Then one of your small triangles has to have different colours at each of its three corners.

Replace the colours with creatures and you've solved the puzzle!

I'll prove Sperner's Lemma below. The proof looks quite long, but that's only because I'm trying hard to explain every step in detail. For the short version look at the top of page two here (which is where I got this proof from in the first place).

One brilliant thing about the proof of Sperner's Lemma is that it takes a sneaky approach to proving that there is at least one "rainbow" triangle. It simply proves that there are an odd number of them! Zero is an even number, so an odd number means at least one!

The proof goes like this: Suppose our colours are red, green and blue (for dragons, trampleodons, and gryphons). Let $R$ be the number of rainbow triangles. We want to show $R$ is odd. Pick two of the colours, say red and green. Let $Q$ be the number of triangles whose corners are coloured red-red-green or green-green-red. Let $X$ be the number of red-green edges, but only counting the ones on the outside border of the whole diagram. Let $Y$ be the remaining number of red-green edges, on the inside of the diagram.

Notice that every triangle with a red-green edge is either one of the ones we counted in $R$ or one of the ones we counted in $Q$ (depending on the colour of its remaining corner). Each triangle counted in R has one red-green edge, since it's corners are red, green and blue. Each triangle counted in Q has two red-green edges (the two edges touching the green corner if the triangle is red-red-green, or the two edges touching the red corner if the triangle is green-green-red). If we add up all these edges we will have counted each edge in X once, but each edge in Y twice because edges on the inside of the diagram have one triangle on either side of them.

So we've proved the equation $R+2Q=X+2Y$.

Now lets think about the number $X$, which is the number of red-green edges on the outside of the diagram. Red points are banned from one side of the big triangle, and green points are banned from another, so red-green edges can only appear along one of the sides. This is the side where blue is banned, so it has only red and green points along it. It has a red point at one end (where it meets the side where green is banned) and a green point at the other (where it meets the side where red is banned). Start at the red end and work your way along towards the green end. The colour of the points must change from red to green and back again an odd number of times in order to end up with a different colour to what it started on. Each change gives us a red-green edge. So $X$ is odd.

Since $X$ is odd and $2Q$ and $2Y$ are even (they divide by two), our equation $R+2Q=X+2Y$ means that $R$ must be odd. So there are an odd number of rainbow triangles and therefore at least one! Q.E.D.

Bonus fact: Sperner's Lemma can be extended to higher dimensions. So if you have a tetrahedron divided up into small tetrahedra, and you colour in each of the points with one of four colours so that each of the colours is banned from one of the triangular faces of your large tetrahedron, then somewhere you have to have a tetrahedon with all four colours at its corners.

Answer 2

At first I tried coloring the dots on the map. I made trampleodons blue, gryphons yellow, and dragons red. This allowed me to color dots with two possibilities as green, orange, or purple, and with three as gray. I worked through the map a few times and kept coming up with the same solution, that you always met a situation in which the three areas had to come together.

I was fairly certain of the solution, but I decided to write a Python script to actually check each possible outcome (2,985,984 of them) and found that my original idea was correct, there is no solution.

It would be solvable without the edge conditions, but those prevent us from creating a solid wall of color to separate the other two.

Answer 3

I don't think it's possible. The most any one species can fill is up to the not-like neighbor (e.g. trampleodon and Avian). And then, to fill that remaining side, at some point one of the two species will have to switch over (either dragon to griphon, or vice-versa) at which point you'll have a triple species province
If you have each species fill out the 5 closest dens, which as no combination of the 3 middle to prevent the triple-kill.
Finally, if you were to try to go in a spiral (tramples along sauria, dragons along avian, gryphons along cryosta) the middle province would get triple-teamed again.

Long and short, since you can't get use a monster to cut off contact between the other two, you will always have an intersection of the three monsters.