subsucesiones

Tomemos cada término de la sucesión y etiquetémoslo con la longitud de la subsucesión estrictamente creciente que inicia con él. Llamemos rango del término a este número. Si el rango de algún término es al menos n+1 entonces ya acabamos. Nótese que, por construcción, rango n+1 significa que a la derecha de ese término hay n términos en aumento y mayores que él. Es decir, existe una subsucesión estrictamente creciente de n+1 términos que empieza con él.

De otra manera, en caso de que todos los términos tengan rango n o menor, tenemos n rangos (o menos) entre los que se distribuyen los n^2+1 términos. Por el principio de las casillas (pichoneras) tenemos n nidos y n^2+1 pichones. En el peor de los casos, cuando ya hemos distribuido n^2 pichones, vamos a tener cada nido (rango) con n pichones. Pero nos queda uno por acomodar, y éste tiene que acomodarse en alguno de los nidos. Y hemos logrado un nido con n+1 pichones. Es decir, tenemos n+1 términos del mismo rango.

Digamos que esos n+1 términos tienen rango k y están en las posiciones i_0, i_1, …, i_n. Para ver que se trata de uns subsucesión decreciente demostremos que el término en i_0 es mayor que el término en i_1. Porque si el término en i_0 fuese menor que el término en i_1 entonces el i_1 se contaría como uno de los k-1 en crecimiento y a la derecha de i_0. Pero en ese caso i_1 tendría rango k-1 y se logra una contradicción.