AoPS - Problem

Source: Saudi Arabia IMO TST Day I Problem 2

Tags: analytic geometry, graph theory, combinatorics unsolved, combinatorics

TheMaskedMagician

22.07.2014 21:52

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$ .

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.