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.
Problem
Source: Saudi Arabia IMO TST Day I Problem 2
Tags: analytic geometry, graph theory, combinatorics unsolved, combinatorics
23.07.2014 11:54
24.12.2014 01:28
Is there a solution without graph theory?
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),…,(n−1,n),(n,1), (1,3),(3,5),…,(n−2,n),(n,2),(2,4),…,(n−3,n−1),(n−1,1), (1,4),(4,7),…,(n−2,1),… 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 n−22 dominoes. Constructing the chain is similar.