AUSTRIAN-POLISH 1990 Problem 7

$D_n$ is a set of domino pieces. For each pair of non-negative integers $(a, b)$ with $a \le b \le n$ , there is one domino, denoted $[a, b]$ or $[b, a]$ in $D_n$ . A ring is a sequence of dominoes $[a_1, b_1], [a_2, b_2], ... , [a_k, b_k]$ such that $b_1 = a_2, b_2 = a_3, ... , b_{k-1} = a_k$ and $b_k = a_1$ . Show that if $n$ is even there is a ring which uses all the pieces. Show that for n odd, at least $(n+1)/2$ pieces are not used in any ring. For $n$ odd, how many different sets of $(n+1)/2$ are there, such that the pieces not in the set can form a ring?