2011 AMC 12A Problema 16

Question

A cada vértice del pentágono convexo

ABCDE

se le debe asignar un color. Hay

6

colores para elegir, y los extremos de cada diagonal deben tener colores diferentes. ¿Cuántas coloraciones diferentes son posibles?

Each vertex of convex pentagon

ABCDE

is to be assigned a color. There are

6

colors to choose from, and the ends of each diagonal must have different colors. How many different colorings are possible?

2520

2880

3120

3250

3750

Respuesta: C

Conceptos:teoría de grafos inclusión-exclusión

Nivel de dificultad: 1820

Pista pequeña:

Las cinco diagonales

AC, CE, EB, BD, DA

forman un único

5

-ciclo entre los vértices

The five diagonals

AC, CE, EB, BD, DA

form a single

5

-cycle among the vertices

Pista grande:

El número de coloraciones propias de un ciclo de longitud

n

con

k

colores es

(k-1)^n + (-1)^n (k-1)

The number of proper colorings of a cycle of length

n

with

k

colors is

(k-1)^n + (-1)^n (k-1)

Solución:

Las diagonales conectan los vértices en el orden

A - C - E - B - D - A,

que es un

5

-ciclo. La condición es exactamente que este ciclo esté coloreado de forma propia.

El número de

k

-coloraciones propias de un ciclo de longitud

n

es

(k-1)^n + (-1)^n (k-1).

Con

n = 5

y

k = 6,

\begin{gathered} 5^5 + (-1)^5 \cdot 5 \\ = 3125 - 5 = 3120. \end{gathered}

Por lo tanto, la respuesta correcta es C.

The diagonals connect the vertices in the order

A - C - E - B - D - A,

which is a

5

-cycle. The condition is exactly that this cycle is properly colored.

The number of proper

k

-colorings of a cycle of length

n

is

(k-1)^n + (-1)^n (k-1).

With

n = 5

and

k = 6,

\begin{gathered} 5^5 + (-1)^5 \cdot 5 \\ = 3125 - 5 = 3120. \end{gathered}

Thus, the correct answer is C.