Question

Adam, Benin, Chiang, Deshawn, Esther y Fiona tienen cuentas de internet. Algunos, pero no todos, son amigos de internet entre sí, y ninguno de ellos 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 formas 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$

Respuesta: B

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

Nivel de dificultad: 2200

Solución:

Separamos en casos según el número de amigos que tiene cada persona. Este valor va de $1$ a $4$ , pues el grafo no es ni vacío ni completo.

Los casos de $1$ y $2$ amigos corresponden, respectivamente, a los de $4$ y $3$ amigos al tomar el grafo complementario, ya que elegir quiénes son amigos determina quiénes no lo son.

Caso 1: cada persona tiene $1$ amigo

Esto significa que las $6$ personas deben dividirse en $3$ parejas, y los integrantes de cada pareja son amigos.

Hay $5$ opciones para el amigo de la primera persona, lo que deja $4$ personas.

Luego hay $3$ opciones para el amigo de la siguiente persona sin pareja. Las $2$ personas restantes quedan obligadas a ser amigas.

Por tanto, hay $3 \cdot 5 = 15$ posibilidades en este caso.

Caso 2: cada persona tiene $2$ amigos

Hay dos posibilidades. La primera consiste en dos tríos cuyos integrantes son todos amigos entre sí.

Hay $\binom{6}{3} = 20$ formas de elegir el primer trío. Debemos dividir entre $2$ porque se pueden intercambiar los dos tríos, lo que da $20 \div 2 = 10$ configuraciones.

La segunda posibilidad es que las amistades formen un solo ciclo de $6$ vértices.

Cada orden de las seis personas alrededor de un ciclo produce uno de estos grafos. Cada grafo se cuenta $6$ veces por la elección de la persona inicial y $2$ veces por el sentido de recorrido, así que hay $6!/(6\cdot2)=60$ ciclos distintos de $6$ vértices. Junto con los $10$ pares de triángulos, este caso tiene $10+60=70$ configuraciones.

El número total de configuraciones es $2(15 + 70) = 170.$

Por lo tanto, B es la respuesta correcta.

We case on the value of friends that each person has. This value ranges from $1$ to $4$ , since the graph is neither empty nor complete.

Note that the cases for $1$ and $2$ friends correspond with the case for $4$ and $3$ friends, since choosing who are friends determines who are not friends.

Case 1: everyone has $1$ friend

This means that the $6$ people must split up into $3$ pairs where the people in each pair are friends.

There are $5$ choices for the friend for the first person. This leaves $4$ people remaining.

There are then $3$ choices for the friend of the next unpaired person. The remaining $2$ people are then forced to be friends.

Therefore, there are $3 \cdot 5 = 15$ possibilities for this case.

Case 2: everyone has $2$ friends

There are two possibilities for this case. There could be two triples where everyone in a triple is friends with each other.

For this possibility, there are $\binom{6}{3} = 20$ ways to choose the people in the first triple. We have to divide by $2$ since we can swap the pairs. This gives us $20 \div 2 = 10$ configurations.

The second possibility is that the friends form one $6$ -cycle.

Every ordering of the six people around a cycle gives such a graph. Each graph is counted $6$ times by the choice of starting person and $2$ times by the direction of traversal, so there are $6!/(6\cdot2)=60$ distinct $6$ -cycles. Together with the $10$ pairs of triangles, this case has $10+60=70$ configurations.

The total number of arrangements is then $2(15 + 70) = 170.$

Thus, B is the correct answer.

2012 AMC 10A Problema 23

Respuesta: B

Nivel de dificultad: 2200

Solución:

El Problema 23 en otros años