MathDB
sequences of dominoes

Source: Austrian - Polish 1990 APMC

May 7, 2020
combinatorics

Problem Statement

DnD_n is a set of domino pieces. For each pair of non-negative integers (a,b)(a, b) with a≤b≤na \le b \le n, there is one domino, denoted [a,b][a, b] or [b,a][b, a] in DnD_n. A ring is a sequence of dominoes [a1,b1],[a2,b2],...,[ak,bk][a_1, b_1], [a_2, b_2], ... , [a_k, b_k] such that b1=a2,b2=a3,...,bk−1=akb_1 = a_2, b_2 = a_3, ... , b_{k-1} = a_k and bk=a1b_k = a_1. Show that if nn is even there is a ring which uses all the pieces. Show that for n odd, at least (n+1)/2(n+1)/2 pieces are not used in any ring. For nn odd, how many different sets of (n+1)/2(n+1)/2 are there, such that the pieces not in the set can form a ring?
Back to ProblemsView on AoPS