Olimpiada del Sudeste Asiático 2021 Problema 4

Suponga que hay $n\geq{5}$ puntos diferentes dispuestos arbitrariamente en un círculo, las etiquetas son $1, 2,\dots $ , y $n$ , y la permutación es $S$ . Para una permutación , una 'cadena descendente' se refiere a varios puntos consecutivos en el círculo , y sus etiquetas son una secuencia descendente en el sentido de las agujas del reloj (la longitud de la secuencia es al menos $2$ ) , y la cadena descendente no se puede extender a más larga . El punto con la etiqueta más grande en la cadena se llama el 'punto de inicio del descenso', y los otros puntos en la cadena se llaman el 'punto de no inicio del descenso' . Por ejemplo: hay dos cadenas descendentes $5, 2$ y $4, 1$ en $5, 2, 4, 1, 3$ dispuestos en el sentido de las agujas del reloj, y $5$ y $4$ son sus puntos de inicio de descenso respectivamente, y $2, 1$ es el punto de no inicio del descenso . Considere las siguientes operaciones: en la primera ronda, encuentre todas las cadenas descendentes en la permutación $S$ , elimine todos los puntos de no inicio del descenso , y luego repita la primera ronda de operaciones para la disposición de los puntos restantes, hasta que no se puedan encontrar más cadenas descendentes. Sea $G(S)$ el número de todas las cadenas descendentes que la permutación $S$ ha aparecido en las operaciones, $A(S)$ sea el valor promedio de $G(S)$ de todas las posibles permutaciones de n puntos $S$ . (1) Encuentre $A(5)$ . (2) Para $n\ge{6}$ , pruebe que $\frac{83}{120}n-\frac{1}{2} \le A(S) \le \frac{101}{120}n-\frac{1}{2}.$

29

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados