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$

Solución:

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

Observa que los casos de $1$ y $2$ amigos se corresponden con los casos de $4$ y $3$ amigos, ya que elegir quiénes son amigos determina quiénes no lo son.

Caso 1: todos tienen $1$ amigo

Esto significa que las $6$ personas deben dividirse en $3$ pares donde las personas de cada par son amigas.

Hay $5$ opciones para el amigo de la primera persona. Esto deja $4$ personas restantes.

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

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

Caso 2: todos tienen $2$ amigos

Hay dos posibilidades para este caso. Podría haber dos tríos donde todos en un trío son amigos entre sí.

Para esta posibilidad, hay $\binom{6}{3} = 20$ maneras de elegir a las personas del primer trío. Debemos dividir entre $2$ ya que podemos intercambiar los tríos. Esto nos da $20 \div 2 = 10$ configuraciones.

La segunda posibilidad es que las amistades formen un hexágono donde la persona en cada vértice es amiga de las personas adyacentes.

La primera persona puede colocarse en cualquier lugar del hexágono. Hay $\binom{5}{2} = 10$ maneras de elegir a las personas adyacentes a esta persona.

Las $3$ personas restantes pueden colocarse de $3! = 6$ maneras en los lugares restantes. Este caso tiene entonces un número total de $10 + 10 \cdot 6 = 70$ configuraciones.

El número total de disposiciones es entonces $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 if the friends form a hexagon where the person at each vertex is friends with the adjacent people.

The first person can be placed anywhere on the hexagon. There are $\binom{5}{2} = 10$ ways to choose the people adjacent to this person.

The final $3$ people can be placed in $3! = 6$ ways in the remaining spots. This case then has a total number of $10 + 10 \cdot 6 = 70$ configurations.

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

Thus, B is the correct answer.

2012 AMC 10A Problema 23

Solución:

El Problema 23 en otros años