Q7 Matemática (Austrian-Polish 1990)

07 | Austrian-Polish | 1990 | Matemática

$D_{n}$ é um conjunto de peças de dominó. Para cada par de inteiros não negativos $(a, b)$ com $a \leq b \leq n$ , há um dominó, denotado $[a, b]$ ou $[b, a]$ em $D_{n}$ . Um anel é uma sequência de dominós $[a_{1}, b_{1}], [a_{2}, b_{2}], ..., [a_{k}, b_{k}]$ tal que $b_{1} = a_{2}, b_{2} = a_{3}, ..., b_{k - 1} = a_{k}$ e $b_{k} = a_{1}$ . Mostre que se $n$ for par existe um anel que usa todas as peças. Mostre que para n ímpares, pelo menos $(n + 1) /2$ peças não são usadas em nenhum anel. Para $n$ ímpar, quantos conjuntos diferentes de $(n + 1) /2$ existem, de modo que as peças que não estão no conjunto possam formar um anel?