1998 AIME Problems/Problem 15

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 $(i,j)$ and $(j,i)$ do not both appear for any $i$ and $j$. Let $D_{40}$ be the set of all dominos whose coordinates are no larger than 40. Find the length of the longest proper sequence of dominos that can be formed using the dominos of $D_{40}.$

Solution

We can draw a comparison between the domino a set of 40 points (labeled 1 through 40) in which every point is connected with every other point. The connections represent the dominoes.

You need to have all even number of segments coming from each point except 0 or 2 which have an odd number of segments coming from the point. (Reasoning for this: Everytime you go to a vertex, you have to leave the vertex, so every vertex reached is equivalent to adding 2 more segments. So the degree of each vertex must be even, with the exception of endpoints) Since there are 39 segments coming from each point it is impossible to touch every segment.

But you can get up to 38 on each segment because you go in to the point then out on a different segment. Counting going out from the starting and ending at the ending point we have:

$\frac{38\cdot 38 + 2\cdot 39}2 = \boxed{761}$

Clarification : To clarify the above solution, every time you move to a new vertex, you take one path in and must leave by another path. Therefore every vertex needs to have an even number of segments leaving it (with the exception of the first and last), because the "in" and "out" segments must make a pair.

See also

1998 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 14
Followed by
Last question
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Invalid username
Login to AoPS