Demostrando que el árbol de Calkin-Wilf enumera los racionales.

Question

El Calkin-Wilf árbol es un infinito de grafo no dirigido (árbol), que se construye como sigue: partiendo desde la raíz a las $\frac{1}{1}$, cada nodo $\frac{a}{b}$ tiene dos hijos:

• a la izquierda niño $\frac{a}{a+b}$
• derecho del niño a $\frac{a+b}{b}$

Este árbol tiene la propiedad de que cada racional aparece en exactamente una vez, en términos mínimos. Estoy interesado en maneras de comprender intuitivamente este hecho.

La mayoría de lo que sé sobre este tema proviene de este maravilloso blog, que da una prueba de [*] de los de arriba en el enlace. Él señala que cada niño de forma exclusiva define un padre, y que cada padre de familia tiene un menor numerador o menor denominador de su hijo. Por lo tanto, si a partir de cualquier fracción $\frac{p}{q}$ en términos mínimos, usted siempre puede trazar una ruta de regreso a $\frac{1}{1}$, el de la raíz.

Esta es realmente una gran prueba, pero se siente un poco "hacia atrás" para mí, en que visualizamos a caminar el árbol de abajo hacia arriba. ¿Alguien sabe de pruebas alternas de este hecho? No necesito rigor, sólo la intuición.

Pensamientos:

Claramente, todos los niños deben tener un mayor numerador o denominador que ninguno de sus antepasados, por lo que no pueden ser repeticiones de un antepasado. (También necesitamos "mínima expresión" para esto, pero que sigue por un argumento separado-ver la nota de pie de página).

Así que sólo estoy preocupado por los "primos". Quizás hay alguna propiedad que toda la izquierda hijos de un nodo de acciones, de las cuales el derecho de los niños no? Que podría resolver el problema, creo.

_{*Mi resumen sólo cubre la parte de su argumento de que resulta "cada racional aparece en exactamente una vez." "En términos mínimos" implica que el Algoritmo de Euclides, y se trata en el próximo post.}

Answer 1

Vamos a utilizar una codificación binaria para nuestro camino desde la parte superior del árbol a una en particular fracción. Valoramos la posición de partida y de cada movimiento para el derecho como $\color{red}1$, mientras que un movimiento a la izquierda es $\color{blue}0$. (Esto lleva a la familiares representación binaria de la Calkin-Wilf de la secuencia.)

Ahora, si nos movemos a la derecha, pasamos de $\frac ab$ a $\frac{a+b}b=\frac ab+1$. Si realizamos $n$ pasos consecutivos para la a la derecha, pasamos de $\frac ab$$\frac ab+\color{red}n$, es decir, que efectivamente agregar $n$. Si nos movemos a la izquierda, pasamos de $\frac ab$ $\frac un{a+b}$, which is the same as $\frac1{1+\frac ba}$. $$ n pasos para la a la izquierda significa pasar de$\frac ab$$\frac1{\color{blue}n+\frac ba}$.

Ahora, esperemos que esto ya suena una campana: esto conducirá a continuación las fracciones. Vamos a tomar como ejemplo la $\frac 37$ que, como un continuo fracción, se ve así: $$ 0 + \frac1{2+\frac13} = [0;2,3] $$ Podemos ver esta representación, lectura hacia atrás, como un medio para navegar por el árbol de la parte superior. Para llegar a $3$, se necesitan tres $\color{red}1$s. (El primero es el punto de partida $\frac11$, los otros dos son para ir desde allí a $\frac11+\color{red}2$.) Para ir de $3$ a $\frac1{\color{blue}2+\frac13}$, se necesitan dos $\color{blue}0$s. En ese punto, ya estás hecho; el último cero significa que usted no necesita tomar ninguna más "$\color{red}1$ vueltas".

He aquí otro ejemplo. $\frac{19}{11}$ es $$ 1 + \frac1{1+\frac1{2+\frac1{1+\frac12}}} = [1;1,2,1,2] $$ La lectura de $[1;1,2,1,2]$ hacia atrás se traduce en dos $\color{red}1$s ($\frac{\color{red}2}1$), uno $\color{blue}0$ ($\frac1{\color{blue}1+\frac12}=\frac23$), dos $\color{red}1$s ($\frac23 + \color{rojo}2=\frac83$), one $\color{blue}0$ ($\frac1{\color{blue}1+\frac38}=\frac8{11}$), y finalmente una $\color{red}1$ ($\frac8{11}+\color{red}1=\frac{19}{11}$).

Así que, para llegar a cualquier número racional, calcular la continuación de su fracción y léase al revés que voy a dar una forma de navegar por las Calkin-Wilf árbol y encontrar el número, con lo que la re-creación de la serie, paso por paso, a partir de la continuación de la fracción. Esto también demuestra que cada positivo número racional que realmente ocurre en el árbol.

Hay una pega, que es que, obviamente, debe comenzar con $\color{red}1$s y termina con $\color{red}1$s (posiblemente, como en el primer ejemplo, con cero $\color{red}1$s). Lo que significa que la continuación de la fracción necesita consta de un extraño número de piezas. Esto no es un problema, sino más bien una buena cosa. Hay exactamente dos continuaron fracción representaciones para cada número racional, y exactamente uno de ellos es el que necesitamos. (Para ejemplo, $\frac38$ puede ser escrito como $[0;2,1,2]$, lo que no funciona, pero también como $[0;2,1,1,1]$, que es lo que necesitamos.) Esto demuestra la singularidad en el Calkin-Wilf árbol.