Problem

Source: Saudi Arabia IMO TST Day I Problem 2

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



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