Dado un libro con $100$ páginas y un $100$ lemas, prueban que hay un lema escrito en la misma página que su índice de

Question

Un libro que consta de 100 páginas y contiene 100 lemas y algunas imágenes. Cada lexema es en más de una página de largo y no puede ser dividida en dos páginas (tiene que caber en una sola página). Los lemas son numeradas de 1 a 100 y se escriben en orden ascendente. Demostrar que debe haber al menos un lema escrito en una página con el mismo número que el lema del número.

Si lexema no 1 está escrito en la página no 1, entonces queda demostrado. Supongamos lema nr 1 está escrito en la página nr k, k>1. A continuación, en al menos una página que debe ser de 2 lemas. Vamos a suponer que siempre en la página de k+i tenemos el lema nr i+1, y así sucesivamente. A continuación, los últimos 100-k-i lemas debe caber en la última página, lo que significa que habrá al menos un lexema (número 100) en la página 100. Pero no sé cómo expresarlo en una más manera matemática!

Alguna ayuda?

Answer 1

Reclamamos más general, que un libro de $n$ páginas y $n$ lemas numeradas $1$ través $n$ tiene al menos un lema en una página que corresponde a su número.

Prueba por inducción sobre $n$: El caso de $n=1$ es obvia. Ahora supongamos que el enunciado es cierto para algunos $n$, y supongamos que tenemos un libro de $n+1$ lemas y $n+1$ páginas. Si lexema $n+1$ se encuentra en una página numerada menos de $n+1$, luego los lemas $1$ través $n$ debe estar en las páginas de $1$ través $n$, y debe haber al menos un lema en una misma página numerada por la hipótesis inductiva. Si no, entonces lexema $n+1$ está en la página $n+1$, y hemos terminado.

Answer 2

Para cada página de $i$ asignar un número $p(i)$ que define el número más alto de lema impreso en todas las páginas a partir de la página 1 hasta la página de $i$ (inclusive). Así que si tenemos los lemas 3, 4 y 5 impreso en la página 12, en la página 13 de tener sólo imágenes: $p(12)=p(13)=5$.

Tenemos la siguiente secuencia:

$$p(1), p(2), \dots, p(100)=100\tag{1}$$

Si $p(1)\ge1$ significa que el lema 1 se imprimirá en la primera página y ya está.

Consideremos un caso al $p(1)=0$ (lo que básicamente significa que la primera página está reservada para sólo imágenes).

La secuencia de números de página $i$ es estrictamente creciente y la secuencia de los valores de $p(i)$ es no decreciente. Ambas secuencias tienen el mismo número de elementos (100) $p(1)<1$ e $p(100)=100$.

Por eso debemos tener un par de páginas consecutivas $i,\space j=i+1$ tal forma que:

$$p(i)<i$$

$$p(j)\ge j$$

Esto básicamente significa que el lema $j$ no está impreso en la página de $i$ o en cualquier otra página antes de que se. En realidad, es impreso en la página $j$ y esto completa la prueba.

Answer 3

Ligero de reformulación de Oldboy del argumento:

Deje $a_i = i - p_i$, donde $p_i$ es el número de la página de lema $i$.

A continuación, $a_1 \leq 0$, $a_{100} \geq 0$, e $a_{i+1}-a_{i} \leq 1$. Por lo tanto $a_i$ debe $0$ para algunos $i$.

Answer 4

Considerar la trayectoria de los puntos de $(L, p(L))$ donde lexema $L$ está en la página $p(L)$. Parcela de que la ruta de acceso en la parrilla de enrejado de puntos de $(x,y)$ para $1 \le x, y \le 100$. La ruta comienza en o por encima de la diagonal en el punto de $(1, p(1))$ y termina en o por debajo de la diagonal en el punto de $(100, p(100))$.

Siguiendo por ese camino, se mueven a la derecha un paso en un momento como el lema conteo aumenta. Usted puede permanecer en el mismo nivel horizontal ya que muchos de los lemas pueden aparecer en una página. Vertical pasos pueden ser más, si las páginas de imágenes intervenir. Desde que se empieza por encima de la diagonal, no se puede cruzar por primera vez en una vertical paso. Ya en el fin de acabar en el otro lado de la diagonal se debe cruzar una vez, que debe ser horizontal paso, por lo que han aterrizado en el camino hacia el otro lado.

(Esto no es exactamente la respuesta a su pregunta, que llama a "expresar [la prueba] en una más manera matemática". Yo podría estar equivocado, pero yo no creo que eso sea posible.)

Answer 5

Aquí está un poco modificada de la prueba por inducción, que espero se haga la inducción paso más obvio.

Deje $P_n$ ser la proposición de que para un libro con $n$ secuencialmente numeradas las páginas y $n$ o más numerados secuencialmente los lemas, al menos un lema es una página con el mismo número que el lema.

Supongamos $P_n$ es cierto para algunos $n=k$, y considerar el caso de la $k+1$ páginas y $k+1$ lemas. Para evitar estar en su propia página numerada, lema $k+1$ tiene que estar en alguna parte en la primera $k$ páginas, y para mantener los lemas en secuencia, ningún otro lema que puede ir en la página de $k+1$.

Por lo tanto, tiene que adaptarse a todas las $k+1$ lemas en la primera $k$ páginas. Por $P_k$, esto pone al menos uno de ellos en su propia página numerada.

Por lo tanto, donde lexema $k+1$ es, al menos, un lema en su propia página numerada.

Claramente esto sigue siendo cierto si añadimos más lemas sin añadir más páginas. Es decir, con $k+1$ páginas y $\ge k+1$ lemas, al menos un lema en su propia página numerada: ie $P_{k+1}$ sostiene. Es decir, si $P_n$ es cierto para $n=k$, también es cierto para $n=k+1$.

Ahora, considere el caso de $1$ página y $\ge 1$ lemas. Claramente lema 1 se encuentra en la página 1, por lo $P_1$ es cierto. Por lo tanto, por inducción, $P_n$ es cierto para todos los $n\ge 1$.

Finalmente, poniendo a $n=100$ demuestra el caso de la pregunta original.