2012 AMC 12A Problema 19

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

Respuesta: B

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

Nivel de dificultad: 2090

Pista pequeña:

Modela las amistades como un grafo de

6

vértices donde todos tienen el mismo grado

n,

con

1 \le n \le 4

Model the friendships as a graph on

6

vertices where everyone has the same degree

n,

with

1 \le n \le 4

Pista grande:

Los casos

n = 1

y

n = 4

son complementarios entre sí, al igual que

n = 2

y

n = 3;

cuenta por separado los dos tipos de grafos

2

-regulares

The cases

n = 1

and

n = 4

are complements of each other, as are

n = 2

and

n = 3;

count the two

2

-regular graph types separately

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

Respuesta: B

Nivel de dificultad: 2090

Pista pequeña:

Pista grande:

Solución:

El Problema 19 en otros años