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

Pista pequeña:

Cuenta los emparejamientos perfectos usando aristas que son pares adyacentes (vecinos) o diámetros (opuestos).

Count perfect matchings using edges that are either adjacent (neighbor) pairs or diameters (across)

Pista grande:

Organiza según cuántos pares diámetro se usan; solo pueden ocurrir $0, 1, 3,$ o $5$ de ellos.

Organize by how many diameter pairs are used; only $0, 1, 3,$ or $5$ of them can occur

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.

Si se usa al menos un diámetro, seguir los emparejamientos adyacentes forzados alrededor del círculo muestra que el número de diámetros debe ser impar. Con exactamente tres diámetros, las cuatro personas restantes deben formar dos pares adyacentes opuestos. La posición de uno de esos pares determina el emparejamiento, dando $5$ posibilidades. 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

Pista pequeña:

Pista grande:

Solución:

El Problema 15 en otros años