Question

Adam, Benin, Chiang, Deshawn, Esther y Fiona tienen cuentas de internet. Algunos de ellos, pero no todos, son amigos de internet entre sí, y ninguno tiene un amigo de internet fuera de este grupo. Cada uno de ellos tiene el mismo número de amigos de internet. ¿De cuántas maneras diferentes puede ocurrir esto?

Adam, Benin, Chiang, Deshawn, Esther, and Fiona have internet accounts. Some, but not all, of them are internet friends with each other, and none of them has an internet friend outside this group. Each of them has the same number of internet friends. In how many different ways can this happen?

$60$

$170$

$290$

$320$

$660$

Solución:

Modela a las personas como vértices de un grafo, con aristas para las amistades. Todos tienen el mismo grado $n$ con $1 \le n \le 4.$ Los casos $n$ y $6 - 1 - n$ son grafos complementarios, así que $n = 1$ se empareja con $n = 4$ y $n = 2$ con $n = 3.$

Para $n = 1$ el grafo es un emparejamiento perfecto: $5 \cdot 3 = 15$ maneras. Por lo tanto $n = 4$ también da $15.$

Para $n = 2$ el grafo es una unión de ciclos: o bien dos triángulos $\left(\binom{5}{2} = 10\right)$ o bien un hexágono $\left(\dfrac{6!}{12} = 60\right),$ sumando $70.$ Por lo tanto $n = 3$ también da $70.$

El total es $15 + 15 + 70 + 70 = 170.$

Por lo tanto, la respuesta correcta es B.

Model people as vertices of a graph, with edges for friendships. Everyone has the same degree $n$ with $1 \le n \le 4.$ The cases $n$ and $6 - 1 - n$ are complementary graphs, so $n = 1$ pairs with $n = 4$ and $n = 2$ with $n = 3.$

For $n = 1$ the graph is a perfect matching: $5 \cdot 3 = 15$ ways. Thus $n = 4$ also gives $15.$

For $n = 2$ the graph is a union of cycles: either two triangles $\left(\binom{5}{2} = 10\right)$ or one hexagon $\left(\dfrac{6!}{12} = 60\right),$ totaling $70.$ Thus $n = 3$ also gives $70.$

The total is $15 + 15 + 70 + 70 = 170.$

Thus, the correct answer is B.

2012 AMC 12A Problema 19

Solución:

El Problema 19 en otros años