Quarter circle train tracks 2

Question

While drawing little railroads based on the rules given in the problem here, a question occured to me: Is it possible to ever get stuck in the construction of such a railroad, i.e. to have no legal piece to add?

Every example I have made not only let's me continue construction, but always leaves enough space for me to finish the loop.

The rules can be summarized as follows:

1. Construct a railroad using pieces of track which are all identical quarter circles.

2. The railroad must not intersect itself.

3. Connect the last piece to the first, making the railroad a loop.

Answer 1

For any connected fragment of track, it is possible to complete it into a loop.

We can consider the grid of squares where each piece of track connects adjacent sides of a square. It should be clear that once the first piece is aligned to this grid, each additional piece must be as well.

If we place one piece of track in a square, there is only one other piece that could possibly go in that square -- the one connecting the two as-yet unused sides.

Instead of individual pieces of track, let us consider, then, placing tiles consisting of two pieces of track that are complementary in this way. (Some of these additional pieces may go unused, but that is okay.)

Doing so gives us a nice property -- the only dead-ends occur between a square that has a tile and a square that is missing a tile.

Now let us construct a loop from our fragment. To do this, use the tiles to construct a big loop that encloses our original fragment. Then fill every empty square inside the big loop with a tile (orientation doesn't matter). I claim that the original fragment is now a loop.

If it wasn't a loop, then it must end in a dead-end. However, the only dead-ends occur on the boundary between tiles and empty squares -- that means they are outside the outer loop since no other squares are empty. Our fragment was inside the outer loop, so it can't be connected to any dead-end (since tracks cannot cross). Therefore, we must have completed the loop as I claimed.

Answer 2

Here is an example with ten pieces. It's not minimal... finding an example with six pieces (which should be minimal) is left as an exercise for the reader.

Answer 3

@mjqxxxx @Nij @Jens (Have first a look at the two "isomorphic" graphics below ; forget the square tiles).

I had misunderstood at first the issue (I thought the tracks were on square cardboards, thinking to a classical game that my children had).

This is a complete rewriting, showing a way to simplify the approach and thus give give the possibility to build a general program (of the type "automaton") to solve any issue of this kind (closing a loop when its two extremities are known) and showing that this program terminates in a finite number of steps.

Consider the two figures below: there is a one-to-one correspondence between the first "world" and the second. And the main thing is that, if the second type of representation is tilted by 45 degrees you get a path with horizontal and vertical line segments. A path-closing looks simpler to describe and achieve with the new "world" than with the "old" one. But, as remarked by @Jens, there is some work still to formalize the idea into a real proof.

Maybe a good way is to describe the issue through a grammar (theory of languages ; it is why I used the term "automata" above) as proposed (with a wider variety of components) in: http://www.perlmonks.org/bare/index.pl?node_id=520671 In another direction see also this about Truchet tiles

in bijection with :