Define a domino to be an ordered pair of distinct positive integers. A proper sequence of dominoes is a list of distinct dominoes 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_n$ be the set of all dominoes whose coordinates are no larger than $n$. Find the length of the longest proper sequence of dominoes that can be formed using the dominoes of $D_n$.
Problem
Source: Saudi Arabia IMO TST Day I Problem 2
Tags: analytic geometry, graph theory, combinatorics unsolved, combinatorics
professordad
23.07.2014 11:54
Consider a complete graph with $n$ vertices. We basically want to find the length of the longest trail possible. If $n$ is odd, the degree of each vertex is even and an Eulerian trail exists; the length is $\frac{n(n-1)}{2}$. If $n$ is even, we take away edges until the degree of all but two of the vertices to be reduced by 1 so an Eulerian trail for the new graph exists. The new graph has $\frac{n(n-1)}{2}-\frac{n-2}{2}$ edges.
viperstrike
24.12.2014 01:28
Is there a solution without graph theory?
chaotic_iak
24.12.2014 06:06
Just phrase it in a non-graph theoretic way. If $n$ is odd, then there is a sequence using all dominoes; $(1,2), (2,3), \ldots, (n-1,n), (n,1),$ $(1,3), (3,5), \ldots, (n-2,n), (n,2), (2,4), \ldots, (n-3,n-1), (n-1,1),$ $(1,4), (4,7), \ldots, (n-2,1), \ldots$ is the first that comes to mind (the dominoes with difference $1$, then difference $2$, and so on). This might need fixing if $n$ is not prime, but the basic idea is that all dominoes can be used. If $n$ is even, then for each coordinate there are $n-1$ dominoes having that coordinate, which is odd, but only the first and the last number in the chain can appear an odd number of times, thus at least $n-2$ numbers will be wasted, or $\dfrac{n-2}{2}$ dominoes. Constructing the chain is similar.