I think games and toys, even those for young children, can often be a great source of interesting mathematics.  Recently a friend of mine was helping his sons build a train track using the pieces shown below:

As you can see, this particular track is “incomplete”: one track segment has an end that is not interlocked (in jigsaw-puzzle fashion) with any other piece.  Let’s say that a track is complete if it doesn’t have this problem; that is, every piece used has each of its puzzle-piece “ends” interlocked with some other piece in the track.

My friend wondered whether it was possible to build a complete track, using all of the available pieces shown in the photo?  It turns out that it is not possible… and so the next question is, how to prove it?

This problem has a flavor very similar to the so-called mutilated chessboard, in that (1) it seems difficult at first glance to prove that you can’t do something, no matter how hard you try; and yet (2) thinking about the problem in just the right (but not necessarily obvious) way yields a straightforward proof.

In this case, suppose that we view a complete track as a graph, consisting of vertices (drawn as points) and edges (drawn as line segments connecting pairs of vertices).  Each track piece is a vertex, and an edge between vertices indicates that the corresponding track pieces are interlocked, as shown below, with vertices in blue and edges in green:

If a track is complete, then every possible connection has an edge associated with it.  Let us temporarily suppose that the track shown above is actually complete, that the “three-way switch” piece is actually a four-way switch, and that the extra dashed yellow edge represents the final required connection.

Now, given such a graph representing a complete track, how many edges does it have?  We could just count up the green and yellow line segments, and find that there are 49 edges… but instead, let us examine each vertex in turn, computing its degree , or the number of edges emanating from it.  We will see why this is handy shortly.

Most of the vertices, corresponding to the simple track segments with two ends, have degree 2.  But some of the “switch” track pieces have degree 3, and one of our temporarily-augmented pieces now has degree 4.  If we add up the degrees of all of the vertices, we find that the total in this case is 98… exactly twice the number of edges!

This is no coincidence.  In general, given any undirected graph, the sum of its vertex degrees equals twice the number of edges.  To see why, consider that in the summation, each edge in the graph gets “counted” exactly twice, once for each of its two vertex endpoints.

An immediate corollary is that, in any such graph, the sum of the vertex degrees must be even.  And this leads to the desired result: if we expect to have any chance of using all available track pieces to build a complete track, then the sum of the degrees– i.e., total number of interlock points– of all of the pieces must be even.  But as shown in the original photo above, in addition to the simple track segments with degree 2, there are five pieces with degree 3, yielding an odd total.

 

After a couple of interesting conversations on the subject, I think I should try to clear up some potentially confusing comments I made in my last post about converting binary floating-point values to decimal strings… and back to binary floating point again.

Injection != round-trip identity

“… You need the representation to be one-to-one, so that distinct finite values always produce distinct output.  More precisely, we would like to be able to (1) convert a floating-point value to a string, then (2) convert the string back to floating-point, recovering exactly the original value .”

In the above quote, “more precisely” is a misleading choice of words, since it suggests that these two properties (one-to-one-ness and round-tripping) are equivalent, when they are not.  For a simplest possible example, consider the correctly rounded floating-point conversion from single-bit binary to single-digit decimal.  This conversion is one-to-one: distinct powers of two always map to distinct single-digit multiples of powers of 10.  However, the round-trip conversion, from binary to decimal and back to correctly rounded binary, is not the identity.  It’s an exercise for the reader to verify that the value , used by Matula in Reference (2) below, is a minimal counterexample.

To see why this distinction matters, consider the more general problem of the correctly rounded conversion from -digit base to -digit base … where and are not “variants of a common base” (more on this later).  Then as shown in Reference (1), the resulting function is one-to-one if and only if

However, we want more than the ability to simply invert this one-to-one conversion function: instead, we would like to be able to compose this conversion function with another correctly rounded conversion back in the other direction, and yield the identity.  As shown in Reference (2), this composition yields the identity if and only if the following stronger condition holds:

Fortunately, in the case where and , the single-bit-to-single-digit wrinkle mentioned above (i.e., ) is the only situation where these two conditions are not equivalent, and so in practice when using floats and doubles this distinction is less important.

Variants of a common base

It’s another exercise for the reader to verify that the second inequality above may be solved for a minimal number of decimal digits required for a successful round-trip conversion from -bit binary, to yield the formula from the last post:

However, there is an important detail involved in turning that strict inequality into this ceiling expression, that is left out of many discussions that I see online (at least where an attempt is made to generalize beyond binary-decimal conversions): this only works since is not an integer.  That is, base 2 and base 10 are not “variants [i.e., powers] of a common base,” as discussed in the references below.  For conversions between bases that are powers of some common base, these formulas do not hold in general.  (Consider various conversions between binary and hexadecimal, for example, again as discussed in the references below.)

References:

1. Matula, David W., The Base Conversion Theorem, Proceedings of the American Mathematical Society, 19(3) June 1968, p. 716-723 [PDF]
2. Matula, David W., In-and-Out Conversions, Communications of the ACM, 11(1) January 1968, p. 47-50 [ACM]