Triangulating A Triangle Of Coins!

OK, we'll start with some preliminary investigation.

We have two trivial cases for $n$ which satisfy, namely $n=0$ and $n=2$ . The next case which satisfy will take some time (but not too much), and we find $n=9$ satisfies as well, as demonstrated below in a rather symmetrical fashion:

Note that there are more solutions for this, but that is left as a further exercise for the reader.

From this, we observe that if $3|n$ and $n$ satisfies being tiled, we can tile another 2 layers of coins below it, so $n+2$ also satisfies. This is demonstrated below:

Also, if $n$ is odd and $n$ satisfies, we notice we can tile another 3 layers below it, so $n+3$ also satisfies. This is demonstrated below:

Finally, we notice that if $n$ is even and it satisfies, then $n+9$ also satisfies, as demonstrated below:

From this, we can actually determine all solutions are of the form $12k$ , $12k+2$ , $12k+9$ and $12k+11$ . Thus ends our preliminary investigation. We will now start on our proof that these are the only possible solutions.

---

Author's note: This part of the proof is quite difficult (I thought) to find, so try not to get lost too much

Ok, we may firstly consider that $\frac{n(n+1)}{2}$ (number of coins in the triangle) must be divisible by 3, and this seems like a logical thing to do. From this, we gather that $n=3k$ or $n=3k+2$ , but we can't progress further from here. How about we consider a colouring using 3 colours, like below?

As you can see, each colour is used once per triangle. However, having equal number of each colour doesn't seem to restrict the size of $n$ . Also, this pattern seems to have no structure behind it. Still, let's keep at this colouring. What if we instead did a colouring using only 2 colours (and keeping the segments between them)?

Well, this certainly looks cool. Notice that every blue coin is connected to only one adjacent red coin, and not any of the other adjacent red coins? What if we invert this, meaning, the blues coins are now connected to the adjacent red coins it was previously not connected to? We should a get a number of loops and paths between two points on the edge (as demonstrated below):

OK, this looks pretty neat, but these edges are quite annoying. What if we add one coin layer to each edge, and colour in these new coins as well using the same principle as so:

Now, every red and blue coin is connected to two coins of the other colour. We also have a path between two corners and possibly, a number of extra loops. Notice that in the above diagram, we have no loops. Since this is a big example in and of itself, we have reason to believe that this might be a general rule. So, let's see what happens when we consider it having a loop:

There are a few seeds of information you can gather from here. Notice that this loop contains no blue or red coins. This may not necessarily be true for all cases, but if you have a loop with a blue and red coin inside it, the red and blue coins must be part of a smaller loop, so we will have a loop that does satisfy this property.

The triangles inside this loop would correspond to a pair of grey lines and grey coins. Furthermore, all of these interiors must be used. In this loop, there is one more grey coin than grey line, so this is impossible. In fact this will hold for all minimal loops for a simple reason: Loops are made out of hexagons.

Any of these loops can be created by taking a hexagon inside it and increasing the region on the interior 1 hexagon at a time until you achieve the whole interior. For each expansion, you get one more grey coin and one more grey line - this is why you need the loop to be minimal, so you can't gain more than 1 grey segment at a time. So in the end, the grey coin in the hexagon you started with will leave you with one more grey coin than segment.

Thus, we have a Hamiltonian Path!!!

Consider the shortest path between the lower two corners:

The top image refers to if $n=3k$ and the lower image refers to if $n=3k+2$ . Thus, there are $4k$ coins in the upper path and $4k+2$ coins in the lower path.

We can now build up these pathways similarly to how we built up the loops: by connecting hexagons. Every time we connect a hexagon, we add 4 more coins to the path. Thus, in the end, the path is $4x$ coins long if $n=3k$ or the path is $4x+2$ coins long if $n=3k+2$ .

Of these coins, half are red and half are blue, so if $n=3k$ , then there are an even number of blue coins, and if $n=3k+2$ , there are an odd number of blue coins. Thus, the total number of these coins are, likewise, even and odd by parity.

Now, we already know that there $\frac {(n+3)(n+4)}{2}$ coins in this triangle (we added a coin to each side, remember?). We know $\frac {(n+3)(n+4)}{2}$ is even if one of $n+3$ and $n+4$ is divisible by $4$ . Thus, $n=4j$ or $4j+1$ . Otherwise, $\frac{(n+3)(n+4)}{2}$ is odd.

From this, we get that $n$ must be of the form $12k$ , $12k+2$ , $12k+9$ or $12k+11$ . Counting all these solutions under $1000$ gives us an answer of $334$ .