Question

La figura de abajo muestra un anillo formado por seis secciones pequeñas que vas a pintar en una pared. Tienes cuatro colores de pintura disponibles y pintarás cada una de las seis secciones de un color sólido. Halla el número de maneras en que puedes elegir pintar las secciones si no se pueden pintar dos secciones adyacentes del mismo color.

The figure below shows a ring made of six small sections which you are to paint on a wall. You have four paint colors available and will paint each of the six sections a solid color. Find the number of ways you can choose to paint the sections if no two adjacent sections can be painted with the same color.

Respuesta

Solución:

Sea $P_n$ el número de coloraciones válidas de un anillo de $n$ secciones. Cortar un anillo entre dos secciones adyacentes muestra que las coloraciones del anillo corresponden exactamente a filas de $n$ secciones con colores adyacentes distintos y los dos colores de los extremos distintos. Una fila de $n$ secciones con colores adyacentes distintos puede pintarse de $4 \cdot 3^{n-1}$ maneras, y las filas cuyos colores de los extremos coinciden corresponden, al fusionar las dos secciones extremas en una, a coloraciones de anillo de $n - 1$ secciones. Por tanto $P_n + P_{n-1} = 4 \cdot 3^{n-1}.$

Tres secciones mutuamente adyacentes dan $P_3 = 4 \cdot 3 \cdot 2 = 24,$ así que $P_4 = 108 - 24 = 84,$ luego $P_5 = 324 - 84 = 240,$ y finalmente $P_6 = 972 - 240 = 732.$

Let $P_n$ be the number of valid paintings of a ring of $n$ sections. Cutting a ring open between two adjacent sections shows that ring paintings correspond exactly to rows of $n$ sections with adjacent colors different and the two end colors different. A row of $n$ sections with adjacent colors different can be painted in $4 \cdot 3^{n-1}$ ways, and the rows whose end colors match correspond, by merging the two end sections into one, to ring paintings of $n - 1$ sections. Hence $P_n + P_{n-1} = 4 \cdot 3^{n-1}.$

Three mutually adjacent sections give $P_3 = 4 \cdot 3 \cdot 2 = 24,$ so $P_4 = 108 - 24 = 84,$ then $P_5 = 324 - 84 = 240,$ and finally $P_6 = 972 - 240 = 732.$

2016 AIME II Problema 12

Solución:

El Problema 12 en otros años