Question

Define una ficha de dominó como un par ordenado de enteros positivos distintos. Una secuencia propia de fichas de dominó es una lista de fichas distintas en la que la primera coordenada de cada par después del primero es igual a la segunda coordenada del par inmediatamente anterior, y en la que $(i, j)$ y $(j, i)$ no aparecen ambos para ningún $i$ ni $j$ . Sea $D_{40}$ el conjunto de todas las fichas cuyas coordenadas no superan $40$ . Halla la longitud de la secuencia propia de fichas más larga que se puede formar usando las fichas de $D_{40}$ .

Define a domino to be an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos 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 $D_{40}$ be the set of all dominos whose coordinates are no larger than $40.$ Find the length of the longest proper sequence of dominos that can be formed using the dominos of $D_{40}.$

Respuesta

Solución:

Una ficha de dominó $(i, j)$ es una arista orientada del grafo completo sobre los vértices $1, \ldots, 40$ , y la regla de que $(i, j)$ y $(j, i)$ no pueden aparecer ambos significa que cada una de las $\binom{40}{2} = 780$ aristas está disponible a lo sumo una vez. Una secuencia propia es exactamente una traza: un recorrido que no repite ninguna arista. En cualquier traza, todo vértice distinto de los dos extremos se entra y se sale el mismo número de veces, así que tiene grado par en el conjunto de aristas usadas.

En el grafo completo, todo vértice tiene grado impar $39$ , así que al menos $38$ vértices deben tener grado impar en el conjunto de aristas sin usar, y un grafo con $38$ vértices de grado impar tiene al menos $\frac{38}{2} = 19$ aristas. Por lo tanto, a lo sumo se pueden usar $780 - 19 = 761$ fichas de dominó.

Recíprocamente, aparta las $19$ aristas disjuntas $(3,4)$ , $(5,6)$ , $\ldots$ , $(39,40)$ . El grafo restante es conexo y solo los vértices $1$ y $2$ tienen grado impar, así que tiene un camino euleriano que recorre las $761$ aristas restantes; orientando cada arista en la dirección del recorrido se obtiene una secuencia propia de longitud $761$ .

A domino $(i, j)$ is an oriented edge of the complete graph on vertices $1, \ldots, 40,$ and the rule that $(i, j)$ and $(j, i)$ cannot both appear means each of the $\binom{40}{2} = 780$ edges is available at most once. A proper sequence is exactly a trail: a walk that repeats no edge. In any trail, every vertex other than the two endpoints is entered and left equally often, so it has even degree in the set of edges used.

In the complete graph every vertex has odd degree $39,$ so at least $38$ vertices must have odd degree in the set of unused edges, and a graph with $38$ odd-degree vertices has at least $\frac{38}{2} = 19$ edges. Hence at most $780 - 19 = 761$ dominos can be used.

Conversely, set aside the $19$ disjoint edges $(3,4),$ $(5,6),$ $\ldots,$ $(39,40).$ The remaining graph is connected and only vertices $1$ and $2$ have odd degree, so it has an Euler trail traversing all $761$ remaining edges; orienting each edge in the direction of travel gives a proper sequence of length $761.$

1998 AIME Problema 15

Solución:

El Problema 15 en otros años