Problem:
Define a domino to be an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which and do not both appear for any and . Let be the set of all dominos whose coordinates are no larger than . Find the length of the longest proper sequence of dominos that can be formed using the dominos of .
Solution:
Let and be the set of dominos that can be formed using integers in . Each in appears in dominos in , hence appears at most times in a proper sequence from . Except possibly for the integers and that begin and end a proper sequence, every integer appears an even number of times in the sequence. Thus, if is even, each integer different from and appears on at most dominos in the sequence, because is even, and and themselves appear on at most dominos each. This gives an upper bound of
dominos in the longest proper sequence in . This bound is in fact attained for every even . It is easy to verify this for , so assume inductively that a sequence of this length has been found for a particular value of . Without loss of generality, assume and , and let denote a four-domino sequence of the form . By appending
to the given proper sequence, a proper sequence of length
is obtained that starts at and ends at . This completes the inductive proof. In particular, the longest proper sequence when is .
A proper sequence can be represented by writing the common coordinates of adjacent ordered pairs once. For example, represent as . Label the vertices of a regular -gon . Each domino is thereby represented by a directed segment from one vertex of the -gon to another, and a proper sequence is represented as a path that retraces no segment. Each time that such a path reaches a non-terminal vertex, it must leave it. Thus, when is even, it is not possible for such a path to trace every segment, for an odd number of segments emanate from each vertex. By removing suitable segments, however, it can be arranged that segments will emanate from of the vertices, and that an odd number of segments will emanate from exactly two of the vertices. In this situation, a path can be found that traces every remaining segment exactly once, starting at one of the two exceptional vertices and finishing at the other. This path will have length , which is when .
Note: When is odd, a proper sequence of length can be found using the dominos of . In this case, the second coordinate of the final domino equals the first coordinate of the first domino. In the language of graph theory, this is an example of an Eulerian circuit.
The problems on this page are the property of the MAA's American Mathematics Competitions