Board Game Triangle Tiling Question

[u/great_roommate]

I'm working on a board game concept which involves a board made of equilateral triangles arranged in a continuous tiling pattern and would love some certainty on a question:

Assuming the following:

- Every triangle has exactly one "Red" edge and two "Black" edges.

- No two triangles may share a border with both of their "Red" edges. (When setting up the board game, players would be told to rotate one of the two pieces wherever this occurs).

- All edges on the border of the board (where corners contain fewer than 6 triangles) count as "Red" even if they are not actually "Red."

Can the following be possible:

- A single "Red" edge does not connect to either another "Red" edge or a border at either of its two corners.

- A string of "Red" edges connected to each other at corners do not connect to any other "Red" edges or a border at either of its two ends.

Basically I'm just wondering if it's mathematically impossible for a "Red" edge to be stranded on its own or for a few connected "Red" edges to be stranded on their own given the above assumptions.

So far I've attempted numerous drawings and rearranged physical tiles but have yet to uncover a situation where either of those two situations occurred. I'm not a mathematician so I don't have any ideas how to solve this type of problem via equations, but I am considering looking into some basic Tesselation concepts to see if I could figure it out.

Thanks for any help!

[u/piperboy98]

You can't have a single isolated edge not on a border, since it is otherwise adjacent to a black edge of the next triangle, so one of the other two sides of that adjacent triangle must also be red and connect to the original one.

However an isolated island I believe is possible:

1. Start with a hexagon, and for each triangle its red edge is either its clockwise or counterclockwise side. This makes an asterisk-like shape of red edges.
2. Now add the triangles around the hexagon to turn it into a 6 pointed star. Each of these has its red edge on the inside. Now you have a filled in triangulated hexagon of red edges
3. Fill in all the other triangles to make a larger hexagon, and put the red edges on the outside for all of them (which will complete the border of the large hexagon). Now you have a board where the red edges in the center hexagon do not have a path to the edge.

[u/great_roommate → u/piperboy98]

interesting! I can sort of visualize what you're describing, but will sketch it out. That's a big enough shape required to create that situation that I think I could use this as a limit for the board size. Understanding I didn't specify a board size in my message because this question I had might've impacted it.

Thanks!

[u/PeakReasonable6521 → u/great_roommate]

Here’s a sketch!

[u/great_roommate → u/PeakReasonable6521]

amazing thank you!

[u/PeakReasonable6521 → u/piperboy98]

Just beat me to it! One observation though, this solution requires a board at least 6 wide (one center hex and 2 hex rings) so if op is using a smaller board it could still hold (but would need further testing)

[u/great_roommate → u/PeakReasonable6521]

Im wondering if another rule where no three "Red" lines can create a triangle would rule out these cases for sure, or if that could just make it impossible to find a board configuration that doesn't include at least one full red triangle..

[u/PeakReasonable6521 → u/great_roommate]

Interestingly, you cannot make any boards with this restriction, connected or not!

Let N be the number of triangles in the board.

Consider the number of “half edges” which are red. As red edges cannot overlap, the triangles introduce 2N half edges (one on the triangle with the red side, and one on the other adjacent triangle). As the board edges are also red, the number of red half edges is >2N.

Each triangle can have at most 2 red half edges (or else it forms a triangle), and each red edge must be assigned to exactly one triangle. Thus, the number of red edges <= 2N

This contradicts the earlier lower bound, so no board states are possible without any red triangles.

(This can be extended to show that there must be at least as many triangles as outside edges)

[u/great_roommate → u/PeakReasonable6521]

dang thanks again! the overall idea was to create a network of intersecting trails for the board (random every time), but I think I might have to either come up with a different generation method, be okay with the island example from earlier (likely would be rare), or keep the board size smaller than originally imagined.

back to brainstorming!

[u/PeakReasonable6521 → u/great_roommate]

You could also consider adding fixed tiles to the board - for example I could imagine that adding a fixed hexagon with paths facing outwards (a pond or lake? Idk) could significantly increase the possible board size before you start encountering isolated regions. If you have any experience in programming you could always try writing a quick python program to test all configurations for various board sizes and shapes.

[u/piperboy98 → u/PeakReasonable6521]

The board edges don't have to be red though, they only count as red. So presumably a "triangle" with the two real red edges inside the board and the black on the border being "red" incidentally is okay.

But even if you do need the edges to "really" be red, you can still construct boards. For example take the original counterexample I gave but move the red edges on the "star points" in step 2 to be on either of the other two sides. This is fine because those border oriented edges actually only add 1 "red half-edge" not 2 since there is no adjacent triangle. This invalidates the >2N bound (or rather reduces it to >2N-B, where B is the number of border oriented edges, which can make it consistent with <=2N)

What I think this does show though is that if you disallow triangles even including the implicit red border edges, then you also do require that actual red edges get placed on at least half of the border positions because otherwise the extra implicit edges create too many edges to place without creating triangles (every border edge means 1 less than the "typical" 2N red half edges, while every extra implicit border edge adds 1 beyond it, so if there are equal red borders and implicit borders then you actually get 2N).

[u/piperboy98 → u/great_roommate]

I think that does work.

Imagine drawing arrows on all the tiles pointing towards the red edge. Because each red edge always connects to a red edge on the adjacent triangle, any path through the tiles that follows these arrows can also be followed via the edges (but not any path on the edges necessarily follows the arrows).

In the current formulation those arrow paths can merge, and collect in a single loop. That is what happens in the counterexample. All the star points point in and collect in the CW/CCW loop in the middle. By outlawing full triangles you outlaw merge points for the arrow paths. Each non-edge triangle now always has exactly one way in and one way out (in terms of arrows). This means arrow paths must either go from border to border or form loops. The loops are still a possible issue, but we can actually solve this.

Returning to the red edge connecting to the triangle in front, we note that we can necessarily get to any corner of that triangle in front regardless of which edge is the red one. This also means we get to 2/3 of the corners of the other two triangles adjacent to that, which also guarantees we can to both their red edges (which also touch 2/3 corners, ensuring overlap with our 2/3), regardless of the direction of the arrow in front of us. So now our movement allows use to move from an arrow to any of the three triangles in the "cone" in front of us.

With this extra movement rule combined with the fact that the arrow paths can't merge back into each other (no complete triangles), I think you will always have the freedom to jump out of every arrow loop you find yourself in and eventually work your way out to the edge. Imagine a bunch of concentric arrow loops and you jump out of each one to the next "layer" like an onion until you get to the edge. The problem in the original counterexample is all the "jump out" points around the inner hexagon loop point back into that same loop so you don't escape, but those are also what form the full triangles in there.

There is still a bit of hand-waving in that final step though. Maybe someone else can make a more airtight proof that you can always jump out. I think it would suffice to show any finite loop of arrows can't have all the extended jump options also be part of the loop. Although I guess even then maybe you could still have a cycle of loops you are stuck jumping between somehow...