4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice! I'm convinced. $\endgroup$ – Jens Jun 7 '16 at 14:10
0
$\begingroup$

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.

enter image description here

$\endgroup$
  • 2
    $\begingroup$ Sorry, but I don't see how this is a counterexample. The two ends can be connected by 2 quarter circles. $\endgroup$ – Jens Jun 6 '16 at 22:23
  • $\begingroup$ The tracks are not on tiles, they are separate pieces which allow this track to be closed with two additional pieces. $\endgroup$ – Nij Jun 6 '16 at 22:30
  • $\begingroup$ @Nij All right. There was a (common with @mjqxxxx) misunderstanding.... I am going to reorient my answer $\endgroup$ – Jean Marie Jun 6 '16 at 23:07
  • $\begingroup$ @JeanMarie There are trivial ways to make this a counterexample, but they require more of a highway than a railway track, and defeat the idea of the puzzle. Or use tiles as you have, but that's a different story. $\endgroup$ – Nij Jun 6 '16 at 23:13
0
$\begingroup$

@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

enter image description here

in bijection with :

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Sorry, but this has the same problem as the example from @mjqxxxx. The pieces of track are not on tiles. This track can be closed with 4 quarter circles. $\endgroup$ – Jens Jun 6 '16 at 22:55
  • $\begingroup$ @Jens : I have completely re-written my answer... But I am discouraged by the inelegance of the downvote (I don't say at all it's you). $\endgroup$ – Jean Marie Jun 6 '16 at 23:33
  • $\begingroup$ Thank you for your update. I agree about the downvote (which wasn't me, btw). However, regarding your proof, I must admit I don't see it. For example, in your lower figure, it is not immediately apparent that I cannot make a 45 degree upturn in the lower rightmost square. Or, if this is ruled out, that I cannot get stuck anyway. $\endgroup$ – Jens Jun 6 '16 at 23:42
  • $\begingroup$ I agree with you that the connecting rules should be written, probably in a more formal way. I agree that it is more a track (pardon for the pun) of solution than a full-fledged one. Unfortunately, it's very late for me (2 o'clock CET). $\endgroup$ – Jean Marie Jun 6 '16 at 23:58
  • $\begingroup$ @Jens I have done a little update giving an interesting reference. Here is another one puzzling.stackexchange.com/questions/24535/tommys-train-tracks $\endgroup$ – Jean Marie Jun 7 '16 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.