Deje que para todos los enteros $i=1,2,\ldots,2^{n-1}$ser dado enteros $f(i)$ tal que $$1\le f(i)\le i.$$
Se puede mostrar que existen $a_{1},a_{2},\ldots,a_{n}$ tales $1=a_{1}<a_{2}<\cdots<a_{n}\le 2^{n-1}$, y $$f(a_{1})\le f(a_{2})\le \cdots\le f(a_{n})$$
Yo considero que este por unas horas, y yo no puedo hacer este trabajo.
Considere la posibilidad de su función de $f$ y construir un árbol de vértices $\{(1,f(1)),(2,f(2), \ldots, (2^{n-1},f(2^{n-1})\}$ como sigue :
La profundidad de un vértice es su distancia desde el nodo raíz.
Es fácil comprobar que :
Por inducción, usted puede encontrar que no pueden ser más de $2^k$ vértices de la profundidad de $k$ (debido a que, por inducción, el primer vértice con la profundidad $k$ $(i,f(i))$ $i\le2^k$ y, por tanto,$f(i)\le2^k$).
De manera que el árbol de $2^{n+1}-1$ vértices tiene al menos la altura de la $n$, y un árbol de $2^{n+1}$ vértices tiene al menos la altura de la $n+1$. Esto demuestra su propiedad.
Ahora, usted puede también encontrar el $f$ con el menor aumento de la larga :
1,2,1,4,3,2,1,8,7,6,5,4,3,2,1,16 y así sucesivamente...
He añadido las sugerencias de Ewan Delannoy y miracle173, gracias a ellos !
Esto es básicamente equivalente a la respuesta por Xoff, pero formulado de una forma un poco diferente.
La proposición. Por $n>0$, cualquier secuencia finita $a_1,a_2,\ldots,a_l$ de enteros con $1\leq a_i\leq i$ todos los $i$ que no contiene débilmente el aumento de las subsecuencias de longitud $n$, tiene una longitud de $l<2^{n-1}$.
Prueba por inducción sobre $n$; en el caso de $n=1$ es evidente, ya que sólo la secuencia vacía no tiene débilmente el aumento de secuencias de longitud$~1$. Ahora vamos a $n>1$ y dejar una secuencia de satisfacción de la hipótesis de ser dado. Definir $g:\{1,2,\ldots,l\}\to\{1,\ldots,n-1\}$ mediante el establecimiento $g(i)$ a la longitud de los más creciente larga que termina con $a_i$. Podemos suponer que el rango de $g$ es el conjunto total $\{1,\ldots,n-1\}$ (es, ciertamente, un intervalo inicial, y si $n-1$ no está en el intervalo, entonces la hipótesis de inducción nos da inmediatamente nuestro resultado), por lo que podemos establecer$m(k)=\min\{\, i\mid g(i)=k\,\}$$k=1,2,\ldots,n-1$. Ahora, una vez que se establece que (1) para cada$~k$ la larga de los $a_i$ $g(i)=k$ es estrictamente decreciente, y por lo tanto de longitud como máximo el valor de $a_{m(k)}$ de su plazo inicial, y (2) $a_{m(k)}\leq 2^{k-1}$, el resultado va a seguir, porque las secuencias de (1) forman una partición de $a_1,a_2,\ldots,a_l$ y, por tanto,$l\leq a_{m(1)}+\cdots+a_{m(n-1)}\leq 2^0+2^1+\cdots+2^{n-2}<2^{n-1}$. Pero (1) es directa a partir de la definición: si $i<j$$g(i)=g(j)=k$$a_i\leq a_j$, se podría extender a un máximo de larga de duración $k$ terminando en $a_i$$a_j$, contradiciendo $g(j)=k$. Y desde $a_1,a_2,\ldots,a_{m(k)-1}$ no tiene débilmente el aumento de las subsecuencias de longitud$~k$, el punto (2) se sigue de $a_{m(k)}\leq m(k)\leq 2^{k-1}$, el ex de la desigualdad de la celebración por hipótesis, y el segundo por la hipótesis de inducción. QED
Por supuesto, la declaración de la pregunta es el contrapositivo de nuestra propuesta.
Se puede agregar que $l=2^{n-1}-1$ se alcanza solo si es estrictamente decreciente secuencias de (1) disminución por unidad de pasos y la desigualdad de (2) es una igualdad; esto ocurre sólo por la secuencia $$ (a_1,a_2,\ldots,a_{2^{n-1}-1}) =(1,~~2,1,~~4,3,2,1,~~\puntos,~~2^i,2^i-1,\ldots,2,1,~~\ldots, ~~2^{n-2},\ldots,1) $$ definido por $a_i=2^{n_i}-i$ donde $n_i=\lceil \lg(i+1)\rceil$, por lo que el $2^{n_i}$ es la primera potencia de dos estrictamente superior a$~i$.
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.
