¿Existencia / inexistencia de una secuencia con una subsecuencia creciente más corta y disminuyendo la subsecuencia?

Question

Puede existir cualquier secuencia entera $ a $ de longitud $ n $ con todos los elementos únicos talesque la duración de su subsecuencia cada vez mayor, así como la de su posterior posterior decreciente más larga es menor que $ \ displaystyle \ lfloor \ frac {n} {2} \ rfloor $ ?

En caso afirmativo, luego dé un ejemplo de tal secuencia.De lo contrario, ¿alguien puede presentar una prueba de que no puede existir tal secuencia?

(solo para agregar algo de sustancia, puede ser demostrado que puede existir tales secuencias, dado cualquier valor arbitrario de $ n> 1 $ ?)

Answer 1

La respuesta a la pregunta de la OP es, no, si $ n \ le 7 $ y sí de lo contrario.

---

Para recibir cualquier entero positivo $ r $ y $ s $ , el teorema de Erdős-Szekeres célebre muestra que para cualquier secuencia de distintos números reales con longitud al menos $ (r - 1) (S - 1) + 1 $ contiene una subsecuencia creciente de longitud $ r $ < / span> o una subsecuencia decreciente de longitud $ s $ .

Resulta que ese límite, $ (R-1) (S-1) +1 $ está apretado. Es decir, para cualquier número positivo $ r $ y $ s $ , hay una secuencia de números distintos con longitud $ (R-1) (S-1) $ que no contiene una subsecuencia creciente de longitud $ r $ y no disminuyendo la subsecuencia de longitud $ s $ .

Aquí hay un ejemplo.

$$ \ comience {array} {} & S-1, & S-2, & \ CDOTS, & 2, & 1 \\ & 2 (S-1), & (S-1) + S-2, & \ CDOTS, & (S-1) + 2, & (S-1) + 1 \\ & \ VDOTS & \ VDOTS & \ VDOTS & \ VDOTS & \ VDOTS \\ & (R-2) (S-1), & (R-3) (S-1) + S-2, & \ CDOTS, & (R-3) (S-1) +2, & (R- 3) (S-1) +1 \\ & (R-1) (S-1), & (R-2) (S-1) + S-2, & \ CDOTS, & (R-2) (S-1) +2, & (R- 2) (S-1) +1 \\ \ End {Array} $$

Considere los números anteriores, leyendo de izquierda a derecha y luego de arriba a abajo. En otras palabras, la secuencia es $ s-1 $ hacia abajo a $ 1 $ , seguido de $ 2 (S-1) $ abajo a $ (S-1) +1 $ , etc. y finalmente seguido de < Span Class="Math-contenedor"> $ (R-1) (S-1) $ abajo a $ (R-2) (S-1) +1 $ , todo en el paso de $ 1 $ .

Es fácil ver que no hay una subsecuencia creciente de longitud R y no disminuya la posterior posterior de longitud $ s $ .

Por ejemplo, cuando $ r= s= 5 $ , tenemos $$ 4,3,2,1, \ \, 8,7,6,5, \ \, 12,11,10,9, \ \, 16,15,14,13 $$ que no tiene la subsecuencia creciente de longitud $ 5 $ ni decreciente la subsecuencia de longitud $ 5 $ .

---

Si dejamos que $ r= s $ , la sección anterior lo indica, para cualquier número positivo $ n $ < / span>, existe una secuencia entera de longitud $ n $ con todos los elementos únicos, de modo que la duración de su subsecuencia cada vez mayor, así como la de su menor subsecuencia disminuida más larga está a lo sumo $ \ lceil \ sqrt n \ rceil $ . Y $ \ lceil \ sqrt n \ rceil $ es el límite superior apretado.

desde $$ \ lceil \ sqrt n \ rceil \ ge \ lfloor \ frac n2 \ rfloor \ \ \ texto {para todos} n \ le 7 $$ y $$ \ LCEIL \ SQRT N \ RCEIL \ LT \ LFLOOR \ FRAC N2 \ RFLOOR \ \ \ \ texto {para todos} n \ gt 7, $$ La respuesta a la pregunta de la OP es, no, si $ n \ le 7 $ y sí de lo contrario.

Por ejemplo, para $ n= 8 $ , tenemos secuencia $ 3,2,1,6,5, 4,9,8,7,8 $ .

Answer 2

Aquí hay una construcción directa de tal secuencia para cualquier múltiplo de cuatro. Está formado por cuatro carreras igualmente del tamaño de enteros consecutivos.

Las primeras y terceras carreras están aumentando. Las segundas y cuarta carreras están disminuyendo. Las carreras usan rangos de números de tal manera que $ r_2 . Por ejemplo, con $ 4n= 16 $ ,

$$ 9,10,11,12 | 4,3,2,1 | 5,6,7,8 | 16, 15,14,13 $$

La subsecuencia cada vez mayor es la longitud $ n + 2 $ . Por ejemplo, en lo anterior, donde $ 4n= 16 $ , la subsecuencia cada vez mayor tiene longitud $ 6 $ ( $ 1 | 5, 6, 7, 8 | 16 $ ). Ninguna subsecuencia creciente es más larga:

• No es posible elegir un elemento de ambas carreras crecientes, ya que cualquier elemento en la primera ejecución de creciente descalifica todos ellos de la segunda carrera creciente.
• no es posible seleccionar más de un elemento de la ejecución decreciente

Se aplica un argumento simétrico para las posiciones decrecientes.

Desde $ n + 2 << 2n $ , esto funciona como contraejemplo para cualquier secuencia múltiple de cuatro. Puede almohazar fácilmente con elementos de secuencia adicionales para longitudes que no son múltiples de cuatro.

Me encontré con esta construcción considerando una secuencia que era una "colina" (aumentando, luego disminuyendo), que cumple con su condición perfectamente. Rompiendo esas carreras largas se podría hacer haciendo dos colinas (aumentar, disminuir, aumentar, disminuir), que esta secuencia hace al garantizar la pendiente arriba / abajo de una 'colina' no es continua por la otra.

Answer 3

También hay secuencias cortas que satisfacen su solicitud. Considere, por ejemplo, los primeros 16 términos de la secuencia binaria de Van der Corput. $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ En general, existe una secuencia $ t $ de longitud $ n \ geq1 $ que contiene una subsecuencia cada vez mayor delongitud $ x \ geq 1 $ y una subsecuencia reducida más larga de longitud $ y \ geq 1 $ si ySolo si los números $ x $ , $ y $ y $ n $ satisfacer las condiciones $ x \ cdot y \ geq n $ y $ x + y \ leqN + 1 $ , consulte aquí .Observe que la referencia da una prueba constructiva.

Answer 4

existen tales secuencias.Basta con generar una secuencia aleatoria lo suficientemente grande.Si revisa el libro de Dan Romik, Las sorprendentes matemáticas de las subsecnaciones cada vez mayores , el teorema 1.1 afirma que

$$ \ frac {\ ell_n} {\ sqrt n} \ a 2, $$

donde $ \ ell_n $ es una duración esperada de la subsecuencia creciente en una permutación aleatoria de tamaño $ n $ .Lo mismo para disminuir.Por lo tanto, para lo suficientemente grande, $ n $ debe existir una secuencia con secuencias crecientes y decrecientes de longitudes en la mayoría de $ 5 \ sqrtn $ , de lo contrario:

$$ 2 e [\ ell_n]= e [| DACI_N |+ | INCR_N |] \ GE 5 \ SQRT N, $$

que contradice el teorema.