14
$\begingroup$

I bought a Lego Duplo railway for my child and it has different types of parts. There are ordinary ones (straight or curved, with two ends), and there are forks - they have three ends, with one highlighted (1, 2a, 2b). If the train comes at the fork through 2a or 2b, then it leaves from 1. And if it comes at the fork through 2a, then the next time it comes from 1, it will leave from 2a. In order to change the direction of the fork, it is necessary that the train will come on it from 2b.

It is easy to build a railway road in which there are 2 such forks, and when the train starts, each of these forks will switch an infinite number of times. But after buying additional parts (forks and ordinary parts), my son cannot build the road so that all the forks switch. He asked me, but I also failed. Is it true that when starting a train on any road made up of these parts, no more than 2 forks will switch endlessly? 

examples of parts

$\endgroup$
  • 1
    $\begingroup$ Unrelated, but reminds me of: Beaver run based on Truchet tiles. At Museum of Mathematics, Meet 2 Beavers That’ll Never Meet. $\endgroup$ – Joseph O'Rourke Nov 26 at 16:33
  • $\begingroup$ Try making a tetrahedron out of them. Gerhard "We're Talking Space Trains, Right?" Paseman, 2019.11.26. $\endgroup$ – Gerhard Paseman Nov 26 at 17:15
  • 7
    $\begingroup$ Duplo binary counter: youtube.com/… $\endgroup$ – Dan Piponi Nov 26 at 17:47
  • 1
    $\begingroup$ @DanPiponi Amazing. Can one leverage this construction to show that the Duplo train reachability problem is PSPACE-complete? $\endgroup$ – Emil Jeřábek supports Monica Nov 26 at 18:09
  • 1
    $\begingroup$ @DanPiponi this is an interesting design, but still it does not concern this task directly, as it uses other type of details (when entering from 1, you always leave through the same exit 2a). $\endgroup$ – Petr Khalipov Nov 27 at 7:26
6
$\begingroup$

It is not possible to have more than two intersections switch endlessly. After following the train for some time we can assume that the train follows some cyclic sequence of states. Suppose the train visits intersections $1$, $2$, ..., $k$ which are distinct and then returns to $i\leq k$, i.e. this is the first time it visits an intersection twice after visiting $1$. There are two cases: either the train will continue in the loop $i,\ldots,k$, or it will go backwards to $1$ following the same intersections. The first case is clear. So assume the train visits $i, i-1, \ldots, 1$. Let us follow the train until it visits some intersection twice again. By relabeling we can assume that after $1$ it visits $j$. Again two cases, again assume we are in the second case.

If $j<i$ we have $1,2,3,\ldots,k,i,i-1,i-2,\ldots,1,j,j+1,\ldots,i, k, k-1,k-2,\ldots,j,1$ and then the sequence repeats. No other intersections besides $i$, $j$ can ever switch.

If $j>i$ we have $1,2,3,\ldots,k,i,i-1,i-2,\ldots,1,j,j+1,\ldots,k,i,i-1,i-2,\ldots,1,$ and the sequence repeats. This is a contradiction.

So there are only $2$ possibilities for the cyclic behavior of the train. Either it just follows a loop and no intersections switch at all, or it has two disjoint loops joined by a path.

$\endgroup$

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.