Question

Hay $10$ personas dispuestas de forma equidistante alrededor de un círculo. Cada persona conoce exactamente a $3$ de las otras $9$ : las $2$ personas que están a su lado, así como la persona directamente al otro lado del círculo. ¿De cuántas maneras pueden las $10$ personas dividirse en $5$ parejas de modo que los dos 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$

Respuesta: C

Conceptos:teoría de grafos análisis por casos

Nivel de dificultad: 1730

Solución:

Etiqueta a las personas del $0$ al $9.$ Los emparejamientos permitidos usan aristas de vecinos $(i, i + 1)$ o aristas de diámetro $(i, i + 5).$ Cuenta los emparejamientos perfectos según el número de aristas de diámetro usadas.

Sin diámetros, las diez personas se emparejan en parejas adyacentes de $2$ maneras (todas las aristas "pares" o todas las "impares"). Con exactamente un diámetro, se elige de $5$ maneras; los dos arcos restantes de cuatro personas cada uno se emparejan de forma única, dando $5.$ Con los cinco diámetros se obtiene $1$ emparejamiento.

Usar exactamente tres diámetros cubre los casos restantes: hay $5$ de esos emparejamientos (dos diámetros nunca pueden usarse sin forzar un arco impar imposible de emparejar). En total, $2+5+5+1=13.$

Por lo tanto, la respuesta correcta es C.

Label the people $0$ through $9.$ Allowed pairings use neighbor edges $(i, i + 1)$ or diameter edges $(i, i + 5).$ Count perfect matchings by the number of diameter edges used.

Using no diameters, the ten people split into adjacent pairs in $2$ ways (all "even" edges or all "odd" edges). Using exactly one diameter, choose it in $5$ ways; the remaining two arcs of four people each pair up uniquely, giving $5.$ Using all five diameters gives $1$ matching.

If at least one diameter is used, following the forced adjacent pairings around the circle shows that the number of diameters must be odd. With exactly three diameters, the four remaining people must be two opposite adjacent pairs. The position of one such opposite pair determines the matching, giving $5$ possibilities. Hence the total is $2+5+5+1=13.$

Thus, the correct answer is C.

2020 AMC 12B Problema 15

Respuesta: C

Nivel de dificultad: 1730

Solución:

El Problema 15 en otros años