Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
Tommy just got a new train set. It only came with one type of train track piece, a quarter circle, all of which were the same size.
$\hspace{2.5in}$
Prove that, whenever Tommy makes a closed loop out of these pieces, the number of tracks he uses will always be a multiple of four.
For example, this loop uses 40 tracks.
Let's think of each piece not as curved but as an L shape, with two sections at a right angle. Adjacent pieces in the track join in a straight line. If we pair off the touching sections, we see the track is composed of two-unit segments connected at right angles.
Since horizontal and vertical segments alternate, there are an equal number of each. Moreover, in traveling a closed loop, the train must go east for as many segments as it goes west, so the number of horizontal segments is even. Likewise for vertical segments. So, the total number of segments is a multiple of 4.
The number of track pieces equals the number of segments, and so is divisble by 4.
Start at some point in the track and follow it around. Write a new line for each piece. On each line write the direction you're going at the start and then the direction you're going when you leave.
Eg for a loop you'd have
U R
R D
D L
L U
Now with four observations about this list you have your proof.
There are an even number of items in the list. This is because odd items start with U/D and end with R/L, and other way around for even. And, since it's a loop, the end of the last must equal the start of the first.
There's an even number of R's and an even number of L's. This is because the list can be broken into pairs, which are either with two R's or two L's.
The total number of L's must be equal to the total number of R's. Because it's a loop it must go R as much as it goes L.
Every item has either a R or an L. So the total number of items is double an even number or a multiple of 4.
Note you don't even need the UD argument, so if you had a straight track of some length and joined it into a loop with the curved tracks, they'd still be a multiple of 4 number of curved tracks. Or in fact any number of parallel straight tracks thrown in (as long as they are all parallel- you still just count the curved pieces).
A proof:
We will define "area" as the area enclosed by any collection of track pieces, such that this area is smaller than the area on the other side of the track (also known as "the world"). If there are multiple disconnected collections, the total area is the sum of all such smaller areas. If there are concentric loops, each loop counts all area contained within, even if this would lead to double/triple/etc counting some pieces. This area is well defined initially, because we are guaranteed that the tracks form a closed loop that encloses something (and, implied, that this loop is of finite size).
If the area is 0, we are done (since our loop consists of zero pieces of track, and zero is divisible by four).
In order for the track to be closed if it has area greater than zero, it must at some point have two consecutive convex turns - we'll call those turns "right", with turns in the opposite direction "left".
Proof:
If there are no places with two consecutive convex turns, then every convex turn must be bordered on either side by concave turns. This means there are at least as many concave turns as convex turns (note that we can't have an unbounded track with a convex turn at each end to get an extra, since this would not form a closed loop), in which case the total angle of turn in a convex direction (where each piece of track is 90*), must be less than or equal to 0*, since each concave track piece cancels out a convex track piece. But the total angle of turn in a convex direction must be exactly 360* in order to form a closed loop - therefor, we have a contradiction, and our assumption that we had no places with two consecutive convex turns must have been false.
We will now examine what could be on either side of those right turns.
Type 1: Right, Right, Right, Right - this forms a disconnected closed loop, and can be altered by removing the four tracks involved. This shrinks the total area inside the tracks by a finite amount, and does not change whether any other tracks in our collection still form closed loops. This is always safe.
Type 2: Right, Right, Right, Left or Left, Right, Right, Right - note that this cannot have a fourth consecutive Right, since they would be a closed loop per Type 1 and the Left could not connect. As a result, this case can always be restated as Left, Right, Right, Right, Left. However, in this case, we can pick up both the Lefts and rotate them 90*, giving us Right - Right, Right, Right, Right. This alters the collection of tracks by removing four tracks and rotating one. The total area is shrunk by a finite amount without changing whether the tracks are connected in a closed loop. This is always safe.
Type 3: Left, Right, Right, Left - we can turn this from a convex set of track into a concave set of track by rotating all the pieces involved 180* around the center to get Right, Left, Left, Right - in which case, we have shrunk the total area that is inside the track by a finite amount, without changing the number of tracks or whether the tracks form a closed loop. This is not necessarily safe, since it doesn't work for tracks like this one. However, it is safe for all other cases where this rotation would not cause track to overlap.
There always exists at least one safe transformation that shrinks the contained area of our collection of tracks.
Proof:
First note that the three types above are comprehensive - this is easily seen from the fact that they cover all four possibilities for the two pieces of track adjacent to our convex pair - R...R, R...L, L...R, and L...L.
Now assume there exists a finite non-zero closed loop track with no safe transformations as defined above. All type 1 and 2 transformations are safe, so this track must consist exclusively of unsafe type 3's at all places where there are two consecutive convex curves. But note that the interfering curve that makes a type 3 unsafe must either be part of a different connected loop from that type 3 or it must be part of the same loop. If it's part of a different loop, both loops can be picked up and placed at a safe distance apart from each other such that the original type 3 becomes safe. This leaves the number of tracks unchanged, leaves all loops intact, and doesn't alter the total contained area, so it is a safe transformation. We claimed there were no safe transformations, so every type 3 in our loop is being interfered with by another part of that loop. In this case, all the interfering curves must be concave. All such type 3's which are unsafe involve at least the following curves: two convex and four concave. If we attempt to increase the number of convex pieces involved by attaching one to any end, we must then increase the number of concave pieces because either we do not have two consecutive convex pieces or we do, and they form another unsafe and inseparable type 3, which necessitates the accompanying majority of concave pieces. You could overlap two adjacent unsafe type 3's in an attempt to share two concave pieces - but this would result in four convex and six concave, no change in the difference. You could also find some way to connect the two concave pieces on either side with a convex (not directly, obviously, but at some point down the line). This would get you to - at best - the same number of convex curves as concave curves. In conclusion, any loop containing only unsafe and inseparable type 3's cannot have more convex curves than concave, which is a contradiction with it being a closed loop. Thus, our original assumption was faulty, and there is some safe transformation (as defined in our three types) in any non-zero closed loop.
For any finite closed non-zero loop(s), starting with the initial situation and using a safe transformation, we can alter the collection of tracks in such a way that the total area is decreased by a finite amount and they still form closed loop(s). We then find a safe transformation for this new collection and repeat. This allows us to reduce the total area until we reach a contained area of zero.
Proof:
Since we started with finite area and can reduce by finite amounts an arbitrary number of times, we must eventually reach zero or negative area. No safe transformation can cause us to have a negative area, therefor we must reach exactly zero.
Since none of our transformations ever caused us to stop forming a connected loop, we have a loop with zero area, which means we must have zero tracks left. Because we only ever removed tracks four at a time, the number of tracks in our initial closed loop must have been divisible by four.
Let's assume a train travels around the track, and that it starts facing exactly right ($0°$ in a Cartesian coordinate system). After traveling the loop completely the train must be at the starting position again facing right.
Each track changes the direction of the train by $\pm 90°$. To have the same direction at the end the train must have traveled an even number of tracks. The number number of left and right turns is either the same or it differs by $4$.
Knowing that the number of tracks is even, we can split the track in double-pieces. There are 4 possible combinations: $LL$, $RR$, $LR$ and $RL$.
Let's define that a single-piece changes the position of the train by $(\pm 1, \pm 1)$. Then the first and second double-pieces change the position of the train by either $(0, \pm 2)$ or $(\pm 2, 0)$, while at the same time changing its direction by $180°$. The third and fourth double-pieces change the position of the train by $(\pm 2, \pm 2)$, without changing its direction.
Because the first and second double-pieces are the only ones changing the direction of the train, the total number of them in the track must be again even. Otherwise the train wouldn't face the same direction at the end. At the same time the train can have only one of $2$ possible directions at the start and end of each double-piece. This means that all of the first and second double-pieces in the track change either the $X$ or the $Y$ coordinate of the train, but not both.
This also means that the third and fourth double-pieces are the only ones which change the other coordinate of the train. As they change this coordinate always by the same value, their total number must be even as well. Otherwise the train couldn't arrive at the starting position at the end.
This means that the total number of double-pieces is even as well, leading to the result that the number of single-pieces must be a multiple of $4$.
Suppose without loss of generality our starting position is $(0,0)$.
Let $T_1$ be the track piece provided in the question, and suppose the radius of the arc is $1$, so that if $T_1$ were the first piece encountered from our starting position, the next position would be $(1,1)$ if going clockwise and $(-1,-1)$ if going counterclockwise. Similarly, let $T_2$ be its rotation by 90 degrees, $T_3$ its rotation by 180 degrees, and $T_4$ its rotation by 270 degrees.
The total number of track pieces in a loop must be even.
This is easy to see. Travelling through any track piece causes a change of $(\pm 1 \pm 1)$ in our current position; in particular, it alters the parity of each coordinate in our position. Because at the beginning and at the end both our coordinates are even, so too must be even the number of parity changes.
The total number of track pieces in a loop must be a multiple of four.
Since we have shown that the total number of track pieces is even, we can decompose the loop into a series of consecutive pairs of track pieces.
Now, the key observation here is that any possible (as in valid) combination of two consecutive track pieces causes a change of $(\pm 2, 0)$ or $(0, \pm 2)$ in our coordinates. For the beginning and end to be $(0,0)$, there has to be an even number of such changes. In other words, there must be an even number of pairs of consecutive track pieces, so the total number of track pieces must be a multiple of four.
