Hay un problema que me mato! pero no podía solucionarlo:
Tenemos una bruja de árbol gráfico que su estructura es lo que está en la imagen. Prueba que hay no hay paramnesia números en cada línea.
Respuesta
¿Demasiados anuncios?
En primer lugar, vamos a empezar con una evidente lema: cada número en la línea $i$ es mayor que $i$.
Supongamos que por la vía de la contradicción que la línea $i$ es la primera línea, donde un número entero $n$ aparece dos veces. Una $n$ debe provenir de la escuadra y el otro debe venir de la adición de $1$, porque si ambos fueron producidos a partir del mismo método, a continuación, $i - 1$ sería una anterior línea donde ocurre este fenómeno.
Digamos que $n$ $j$th plaza, donde la $1$ es la primera en la secuencia de cuadrados. (En otras palabras, $ j = \sqrt{n}$.) A continuación, el $j-1$th cuadrado es $n - (2j - 1)$.
Considere la posibilidad de la $n$ que proviene de la adición de $1$. La forma más rápida (que requiera el mínimo número de líneas) de manera de hacer que el $n$ es comenzar con la $j-1$th plaza y agregar $1$ cada línea hasta llegar a $n$. Por lo tanto el $j-1$th plaza apareció, al menos, $(2j - 1)$ líneas antes de la línea de $i$.
Ahora, considere el $n$ que proviene de cuadrar. A continuación, en la línea$i-1$,$\sqrt{n} = j$. Por lo $j$ se produce en el $i-1$th línea, pero sabemos que $i - 1 \geq (2j - 2)$ porque hemos identificado un número que debe producirse $(2j - 1)$ líneas antes de la línea de $i$. Desde $ j < (2j - 2)$, esto se contradice con nuestro lema.
