La secuencia 7, 2, 4, 1, 4, 8 tiene una longitud posterior creciente cuatro (2, 4, 4, 8) y una posterior decreciente tres (7, 4, 1). También tiene otras subsiguientes monótonas (crecientes o decrecientes), pero ninguna más larga que cuatro.
¿Cuánto tiempo debe durar una secuencia para que se garantice que tiene una longitud de subsecuente monótona k?
Probemos el siguiente teorema usando el principio de encasillamiento.
Teorema : Si colocas $1,2, \cdots , n^2+1$ en una fila en orden aleatorio, luego existe una secuencia monótona (creciente o decreciente) con una longitud igual o superior a $n+1$ .
Prueba : Deje que $a_1,a_2, \cdots ,a_{n^2+1}$ sean los números en una fila. Además, que $inc[i]$ será la longitud de la máxima secuencia creciente de $a_i$ y dejar que $dec[i]$ será la longitud de la máxima secuencia decreciente de $a_i$ .
Entonces, para $i=1,2, \cdots , n^2+1$ consideremos el punto de la red $(inc[i],dec[i])$ . Si alguno de los dos $inc[i]$ o $dec[i]$ es igual o superior a $n+1$ entonces somos felices. Entonces, supongamos que esta situación no ocurre.
Entonces, ya que $n^2+1$ los puntos se establecen en el $n^2$ puntos de $(1,1)$ a $(n,n)$ por el principio de encasillamiento, existe al menos un par de números enteros distintos $i,j$ de tal manera que $$(inc[i],dec[i])=(inc[j],dec[j])$$
Sin embargo, esto nunca sucede. Esto es porque si $i \lt j$ entonces, o bien $a_i \lt a_j$ o $a_i \gt a_j$ se mantiene. Los antiguos arrendamientos $inc[i] \lt inc[j]$ este último conduce $dec[i] \gt dec[j].$ Entonces, ahora sabemos que la suposición lleva a una contradicción.
Por lo tanto, ahora sabemos que o bien $inc[i]$ o $dec[i]$ es igual o superior a $n+1$ . Esto es lo que tenemos que mostrar. Q.E.D.
El término de búsqueda para los antecedentes de la pregunta y las otras respuestas es
Teorema de Erdos-Szekeres (sobre subsecuentes monótonos).
El teorema, con varias pruebas y generalizaciones notables, es que una secuencia de longitudes $mn+1$ tiene una subsecuencia cada vez mayor $m+1$ largo, o una longitud $n+1$ disminuyendo la subsecuente.
A la pregunta indicada,
¿Cuánto tiempo debe durar una secuencia para que se garantice que tiene una duración de subsecuente monótona $k$ ?
la respuesta es que la E-S limitada de $mn+1$ es el mínimo necesario para garantizar $(m+1,n+1)$ . Así que para $(n,n)$ la longitud mínima es $(n-1)^2+1$ y hay secuencias de longitud $(n-1)^2$ sin una subsecuente monotonía de la longitud $n$ . La pregunta anterior sobre eso:
Me gusta la prueba basada en El teorema de Dilworth . Es la sexta prueba en la sección 2 de este delicioso visión general . Un orden parcial finito de al menos $n^2+1$ elementos contiene una cadena o un anti-cadena de longitud $n+1$ . Aplica esto al orden parcial de las coordenadas en los pares $(k, a_k)$ donde $a$ es una secuencia de longitudes al menos $n^2+1$ .
Del Teorema 1 en "Matemáticas Algorítmicas Discretas, 3ª ed.", pp. 403:
"...una secuencia de $N^2+1$ (o más) números distintos tiene necesariamente una consecuencia monótona de por lo menos $N+1$ términos".
De eso, $1+(N-1)^2$ términos tiene necesariamente tal subsecuente de por lo menos $N$ términos, que por supuesto pueden derivarse de la respuesta de las matemáticas.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
