Question

Hay $10$ personas paradas con igual separación alrededor de un círculo. Cada persona conoce exactamente a $3$ de las otras $9$ personas: las $2$ personas paradas junto a ella, así como la persona que está directamente al otro lado del círculo. ¿De cuántas maneras pueden las $10$ personas dividirse en $5$ parejas de modo que los miembros de cada pareja se conozcan?

There are $10$ people standing equally spaced around a circle. Each person knows exactly $3$ of the other $9$ people: the $2$ people standing next to her or him, as well as the person directly across the circle. How many ways are there for the $10$ people to split up into $5$ pairs so that the members of each pair know each other?

$11$

$12$

$13$

$14$

$15$

Solución:

Etiqueta a las personas alrededor del círculo. Cuenta según el número de parejas de personas opuestas.

Sin parejas opuestas, todos deben emparejarse con un vecino a lo largo del ciclo de 10. Hay exactamente $2$ emparejamientos alternos con vecinos.

Con una pareja opuesta, elige esa pareja de $5$ maneras. Las personas restantes forman dos caminos de cuatro vértices, y cada camino tiene un único emparejamiento perfecto por parejas de vecinos, así que esto da $5$ emparejamientos.

Con dos o cuatro parejas opuestas, los caminos restantes para emparejar vecinos tienen longitud impar en algún lugar, así que no es posible ningún emparejamiento perfecto.

Con tres parejas opuestas, las dos parejas opuestas no elegidas deben ser adyacentes entre las cinco posiciones de parejas opuestas; de lo contrario, las personas restantes no pueden emparejarse por parejas de vecinos. Hay $5$ elecciones adyacentes para las dos parejas opuestas no elegidas, así que hay $5$ emparejamientos.

Con las cinco parejas opuestas, hay $1$ emparejamiento. El total es $2+5+5+1=13.$

Por lo tanto, la respuesta correcta es C.

Label the people around the circle. Count by the number of pairs of opposite people.

With no opposite pairs, everyone must be paired with a neighbor around the 10-cycle. There are exactly $2$ alternating neighbor matchings.

With one opposite pair, choose that pair in $5$ ways. The remaining people form two paths of four vertices, and each path has only one perfect matching by neighbor pairs, so this gives $5$ matchings.

With two or four opposite pairs, the remaining neighbor-pairing paths have odd length somewhere, so no perfect matching is possible.

With three opposite pairs, the two opposite pairs not chosen must be adjacent around the five opposite-pair positions; otherwise the remaining people cannot be matched by neighbor pairs. There are $5$ adjacent choices for the two unchosen opposite pairs, so there are $5$ matchings.

With all five opposite pairs, there is $1$ matching. The total is $2+5+5+1=13.$

Thus, the correct answer is C .

2020 AMC 10B Problema 17

Solución:

El Problema 17 en otros años