Question

Diez sillas están dispuestas en un círculo. Halla el número de subconjuntos de este conjunto de sillas que contienen al menos tres sillas adyacentes.

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs.

Respuesta

Solución:

El conjunto completo de $10$ sillas cumple; cuenta los demás localizando cada racha maximal de al menos tres sillas elegidas adyacentes en su inicio en el sentido de las agujas del reloj. Cualquier subconjunto de este tipo contiene un bloque de cuatro sillas consecutivas que es vacía-elegida-elegida-elegida. Hay $10$ posiciones para este bloque, y las $6$ sillas restantes son libres, lo que da $10 \cdot 2^6 = 640.$

Esto cuenta una vez por cada racha maximal de longitud al menos $3.$ Dos rachas de este tipo requieren al menos $3 + 3$ sillas elegidas más dos huecos, así que tres rachas son imposibles, y los subconjuntos con exactamente dos rachas se cuentan dos veces. Para tener dos rachas, coloca dos bloques disjuntos vacía-elegida-elegida-elegida: $\frac{10 \cdot 3}{2} = 15$ maneras (el segundo bloque cabe en $3$ posiciones entre las $6$ sillas restantes), con las últimas $2$ sillas libres, para $15 \cdot 2^2 = 60$ subconjuntos.

El total es $1 + 640 - 60 = 581.$

The full set of $10$ chairs qualifies; count the others by locating each maximal run of at least three adjacent chosen chairs at its clockwise start. Any such subset contains a block of four consecutive chairs that is empty-chosen-chosen-chosen. There are $10$ positions for this block, and the remaining $6$ chairs are free, giving $10 \cdot 2^6 = 640.$

This counts once for each maximal run of length at least $3.$ Two such runs require at least $3 + 3$ chosen chairs plus two gaps, so three runs are impossible, and subsets with exactly two runs are counted twice. To have two runs, place two disjoint empty-chosen-chosen-chosen blocks: $\frac{10 \cdot 3}{2} = 15$ ways (the second block fits in $3$ positions among the remaining $6$ chairs), with the last $2$ chairs free, for $15 \cdot 2^2 = 60$ subsets.

The total is $1 + 640 - 60 = 581.$

2014 AIME II Problema 9

Solución:

El Problema 9 en otros años