Contar los racionales: el árbol de Stern-Brocot

  • Categoría de la entrada:Artículos

A estas alturas lo más probable es que ya sepas que los números racionales son contables; es decir, que existen tantos racionales como números naturales. En esencia, esto se traduce en que podemos colocar las todas fracciones en una lista ordenada sin repetirlas, pero no es nada evidente cómo se puede encontrar una forma automática de crear una sucesión así. La mayoría de métodos repiten números racionales en la lista o utilizan fracciones sin reducir, lo que es un engorro. Por eso, hoy vamos a construir una serie de números en la que aparecen todos los números racionales positivos posibles (¡sin repetirse!). Es la magia del árbol de Stern-Brocot.

Esquema para ordenar los números racionales
Una de las maneras habituales de escribir todos los racionales positivos:
muchos están repetidos y muchas fracciones aparecen sin reducir.

El árbol de Stern-Brocot

De todos los enfoques a la construcción de los racionales, el árbol de Stern-Brocot es el más estimulante: es un árbol donde crecen las fracciones. Para construirlo solo hay que seguir dos reglas:

  • Colocar el \frac{1}{1} en la parte alta del árbol.
  • De cada vértice \frac{n}{m} dibujar dos ramas hacia abajo: la hija izquierda, \frac{n}{m+n}, y la hija derecha, \frac{n+m}{m}.

Siguiendo esta receta de forma inductiva, llegamos a un esquema con este aspecto:

Árbol de Stern-Brocot

El primer nivel de árbol solo tiene un elemento: \frac{1}{1}. El segundo nivel tiene dos fracciones: \frac{1}{2} y \frac{2}{1}. Y, así, como se aprecia en la figura, se van añadiendo más niveles al árbol, cada vez más abajo, cada nivel con el doble de fracciones que el anterior. Consideramos que el nivel 1 es el más alto y los están por debajo.

Cada fracción, o vértice, produce dos hijas más en el siguiente nivel, fácilmente reconocibles con las reglas de creación. Es interesante observar que tanto el numerador como el denominador de las hijas se mantiene o aumenta de tamaño. Asimismo, cada fracción (salvo la primera) tiene una madre, que se puede averiguar fácilmente:

\mathrm{madre~de~} \frac{a}{b} = \left\{ \begin{array}{ll} \displaystyle \frac{a-b}{b} & \mathrm{si~} a > b \\ \\ \displaystyle\frac{a}{b-a} & \mathrm{si~} a < b \end{array} \right.

La gracia del árbol de fracciones es que produce todas las fracciones positivas que existen, sin repetirlas y en forma ya reducida. ¡Menuda oferta!

Todos y cada uno

No es difícil demostrar cada una de las propiedades de las fracciones del árbol. Vamos allá.

Todas las fracciones del árbol aparecen en su forma reducida.

Es decir, el numerador y el denominador de cada vértice son coprimos. Para el vértice superior, \frac{1}{1}, es cierto.

Ahora bien, supongamos que existen fracciones que aparecen sin reducir en el árbol. De todas ellas, digamos que a/b es la que aparece en el nivel más alto. Si resulta que a/b es una hija izquierda, entonces su madre sería a/(b-a). Pero, en ese caso, esta fracción también estaría sin reducir. ¡Contradicción, pues hemos dicho que estábamos en el nivel más alto con fracciones sin reducir!

Si a/b es una hija derecha, procederá de (a-b)/b, lo que nos lleva a la misma contradicción. Por lo tanto, no puede haber fracciones sin reducir en la lista.

Cada número racional positivo aparece en el árbol.

Empecemos por lo obvio: el número 1 aparece en el árbol.

Ahora bien, supongamos que existen fracciones reducidas que no aparecen en el árbol. De todas ellas, elegimos las que tengan el denominador más pequeño y, de entre estas, elegimos la que tenga el menor numerador: a/b. En este caso, la madre de a/b tampoco debería aparecer en el árbol, porque si está la madre también tiene que estar la hija.

  • Si a>b, entonces su madre (a-b)/b tampoco aparece en el árbol. Pero su madre tiene un numerador más pequeño que la hija, lo cual es contradictorio, pues hemos dicho que a/b tenía el numerador más pequeño posible. ¡Contradicción! Es imposible que a/b exista.
  • Si a<b, entonces su madre a/(b-a) tampoco aparecería en el árbol. Pero la madre tiene el denominador más pequeño que la hija, lo cual vuelve a ser contradictorio.

En resumen, no es posible que existan fracciones positivas que no aparezcan en el árbol.

No se repiten números en el árbol.

Primero, comprobemos que el 1 no se repite en algún rincón del árbol. Si se repitiera, sería hijo de alguna fracción a/b. Pero las hijas de a/b son a/(b+a) y (a+b)/b, y ninguna de ellas puede ser 1 a no ser que a=0 o b=0. Esto es imposible, porque a y b comienzan en 1 y se van haciendo más grandes según se avanza en el árbol.

Para comprobar que el resto de números no se repite, empezamos de la misma forma: supongamos que existen fracciones repetidas en el árbol. De todas ellas, elegimos las que tengan el menor denominador y, de entre estas, elegimos la que tenga el numerador más pequeño: a/b. Si a<b, entonces las dos fracciones a/b tendrían la misma madre, a/(b-a). Pero, entonces, las madres también están repetidas, y se trata de una fracción con un denominador menor que la hija. ¡Contradicción!

La demostración es análoga para a>b. Vamos, que no pueden existir fracciones repetidas.

La lista completa

En vista de estas propiedades, tenemos que todos los números racionales aparecen en el árbol una y solo una vez. Para encontrar todos los racionales solo hay que construir el árbol y leer las fracciones de izquierda a derecha, nivel a nivel:

\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, …

Una observación interesante, una vez colocadas en línea, es que el denominador de cada fracción es el denominador de la siguiente. Los numeradores se van reciclando. No es difícil de justificar: si la pareja de fracciones tiene misma madre, entonces es un resultado directo de la construcción del árbol. Si la pareja de fracciones no tienen la misma madre, entonces se puede retroceder hasta el primer antepasado común y proceder una demostración por inducción. No es tan complicado como parece: la primera fracción debe ser una hija derecha y su madre tiene el mismo denominador. La segunda fracción será una hija izquierda y su madre tendrá el mismo numerador. En ese caso, ascender por el árbol de antepasados no modifica el numerador o el denominador de las hijas, lo que reduce la dificultad de la demostración (pero no el fastidio de leerla).

Puesto que los denominadores no aportan información nueva, podemos prestar atención solo a la sucesión de los numeradores:

\{1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,…\}

Si decimos que estos numeradores son los términos de una sucesión f(n), entonces los valores de f(n)/f(n+1) generan una lista con todos los números racionales sin repetir.

Buscando una fórmula

Como las fracciones se sitúan en un árbol, podemos intentar emparentar cada fracción con sus hijas. No es difícil comprobar que un vértice f(n)/f(n+1) tiene como hijas a f(2n+1)/f(2n+2) y f(2n+2)/f(2n+3). En ese caso, según las reglas de creación de hijos, podemos establecer que la hija izquierda tiene el mismo numerador que la madre, así que:

f(2n+1)=f(n)

Y, además, el denominador de la hija es como la suma del numerador y denominador de la madre, así que:

f(2n+2)=f(n)+f(n+1)

Esta relación de recurrencia, junto con la semilla inicial f(0)=1 es la que determina todos los números racionales. Como es un resultado que merece ser enmarcado, lo enmarco:

Sea una sucesión f:\mathbb{N}\to\mathbb{N} tal que:

\begin{array}{l} ~~~~~~~~~f(0)=1, \\ f(2n+1)=f(n), \\ f(2n+2)=f(n+1)+f(n) \end{array}

Entonces el cociente \frac{f(n)}{f(n+1)} produce todos los números racionales positivos sin repetirlos y en forma reducida.

Más allá de la recurrencia

Aunque la primera vez que conocí este resultado me pareció haber descubierto una perla de las buenas (fue parte de mi inspiración para el vídeo sobre las notas musicales), es cierto que a nadie le gustan las relaciones de recurrencia. Pero es difícil deshacerse de ella.

Se puede dar un sentido más terrenal a f(n) y demostrar que coincide con la cantidad de representaciones hiperbinarias de n. Una representación hiperbinaria de n es una manera de escribir n como suma de potencias de 2, donde cada potencia se puede usar, como mucho, dos veces. Por poner un ejemplo, existen dos representaciones hiperbinarias del número 5, y tres del número 6:

\begin{array}{l} 5 = 1 + 2 +2 = 1 + 4 \\ 6 = 1 + 1 + 2+2=1 + 1+4=2+4 \end{array}

Lo que corresponde a f(5)=2 y f(6)=3.

A partir de la maravillosas notas de Neil Calkin y Herbert S. Wilf.