alquimiayciencias: Sorpresa sumando potencias de 2

Les voy a plantear un sencillo ejercicio:

Vamos a intentar expresar los números naturales como suma de potencias

de 2 de exponente natural (o cero, hecho que especifico para evitar

problemas, ya que parece que no nos ponemos de acuerdo

sobre si es un número natural o no).

Tenemos, por ejemplo, que $3=2^1+2^0=2+1$ , y también que

$3=2^0+2^0+2^0=1+1+1$ .

Esta segunda forma de expresar 3como suma de potencias de 2

es algo repetitiva, ¿verdad?

De hecho, si analizamos todas las formas de expresar así un número natural más grande tendremos muchas más repeticiones:

sumas de varios unos, sumas de varios doses, sumas de varios cuatros…

Para evitar ser tan repetitivos en este sentido solamente vamos a permitir que cada potencia de 2 aparezca dos veces como mucho.

Por ello, para el 3 la segunda manera escrita antes no nos serviría.

El objetivo de este ejercicio es encontrar todas las posibles maneras

de expresar cada número natural como suma de potencias de 2

con la condición de que cada potencia de 2 aparezca a lo sumo dos veces.

Por ejemplo, por lo comentado antes el 3 puede expresarse como suma

de potencias de 2 de una manera únicamente.

Si llamamos $S(n)$ al número de maneras de expresar $n$ como suma

de potencias de 2 con la condición anterior, tendríamos entonces

que $S(3)=1$ .

Probemos con otro, el 10 por ejemplo.

Tenemos que:

$10=8+2=8+1+1=4+4+2=4+4+1+1=4+2+2+1+1$

por lo que $S(10)=5$ .

Bien, después de introducir la mecánica del ejercicio,
vamos a ver qué obtenemos.

El 1 se puede escribir así de una forma nada más, el 2 de dos formas,
el 3 de una forma…

Resumiendo, si colocamos en fila los valores de $S(n)$ , para $n \ge 1$ ,
definiendo $S(0)$ como 1, obtenemos la siguiente lista:

${1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1, \ldots }$

Una lista cualquiera de número naturales…

¿Alguna propiedad interesante escondida en ella?

Pues sí.

De hecho muy interesante.

Tomemos los cocientes de cada dos términos consecutivos de esta sucesión.

Obtendríamos la siguiente secuencia de fracciones:

${\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}, \ldots }$

Esta lista de números racionales tiene varias propiedades:

Por construcción, el denominador de cada fracción es el numerador de la siguiente.
Al ser cada elemento de la sucesión $S(n)$ primo relativo con $S(n+1)$ , todas las fracciones que aparecen en esta nueva lista lo hacen en su forma reducida.
Y lo que es más sorprendente, todo número racional positivo aparece una y solamente una vez en esta sucesión.

Esto sí que es sorprendente, ¿no?

Repito: todo número racional positivo aparece una y solamente una vez en esta sucesión.

¿Cuál es la consecuencia más directa de este hecho?

Muy sencillo: el cardinal de $\mathbb{Q}$ es el mismo que el cardinal de $\mathbb{N}$ ,

o lo que es lo mismo, hay tantas fracciones como números naturales, hecho que no deja de ser poco intuitivo por muy conocido que sea.

Se estarán preguntado si todo esto tiene demostración, ¿verdad?

Pues sí, la tiene, y la vamos a ver ahora mismo.

Pero antes vamos a colocar las fracciones de forma distinta a la anterior, concretamente en forma de árbol, de la siguiente manera:

Esta colocación de las fracciones anteriores se denomina árbol de Calkin-Wilf, cuyo nombre proviene de los matemáticos Neil Calkin y Herbert Wilf, sus descubridores:

Vamos a demostrar lo que hemos comentado anteriormente, pero partiendo de las fracciones colocadas en el árbol de Calkin-Wilf.

Como se puede ver, el comienzo del árbol es la fracción $\frac{1}{1}$ .

El resto del árbol se formaría de la siguiente manera:

Cada fracción $\frac{i}{j}$ del árbol tiene dos hijos, el de la izquierda, que es $\frac{i}{i+j}$ (menor que 1), y el de la derecha, que es $\frac{i+j}{j}$ (mayor que 1).

Demostremos ahora todo lo comentado anteriormente:

El numerador y el denominador de cada fracción son primos relativos

Es evidente que la primera fracción del árbol cumple esta propiedad.
Supongamos que existe alguna fracción del árbol para la que esto no es cierto.
De entre todas las que no cumplen esta propiedad, tomemos la que aparece más arriba en este árbol, digamos $\frac{a}{b}$ .
Es decir, a y b tienen factores comunes.
Esta fracción será hija de la fracción que tiene justo en el nivel anterior. Si es la de la izquierda, entonces proviene de la fracción $\frac{a}{b-a}$ , que entonces también cumpliría que su numerador y su denominador tienen factores comunes, hecho que contradice que $\frac{a}{b}$ era la fracción con esa característica que aparecía más arriba en el árbol.
Si es la de la derecha proviene de la fracción $\frac{a-b}{b}$ ,
con lo que llegamos a la misma contradicción.
Por tanto, todas las fracciones que aparecen en el árbol lo hacen
en su forma reducida.
Todo número racional positivo aparece en algún vértice

El número racional 1 aparece (es el comienzo del árbol).
Supongamos que hay números racionales (se suponen expresados en forma reducida a partir de ahora) que no aparecen en ningún vértice.

Tomemos $\frac{a}{b}$ el que tenga menor denominador de entre todos ellos, y si hubiera varias tomamos la que tenga menor numerador.

Si $a > b$ , la fracción $\frac{a-b}{b}$ tampoco aparecería en el árbol (ya que si lo hiciera entonces también aparecería $\frac{a}{b}$ ), pero $\frac{a-b}{b}$ tiene numerador menor que $\frac{a}{b}$ , teniendo ambas el mismo denominador, hecho que contradice la suposición inicial.

De forma análoga se llega a una contradicción con $a < b$ .
Ningún número racional aparece más de una vez

El número racional 1 ocurre solamente en la posición inicial del árbol,
ya que si apareciera más adelante sería el hijo de alguna otra fracción, hecho que es imposible por la forma en la que se construyen los hijos de cada fracción.
Supongamos entonces que hay fracciones (reducidas)
que aparecen más de una vez en el árbol.
Tomemos la que tiene menor denominador, y si hay varias la que tiene menor numerador de todas ellas, digamos $\frac{a}{b}$ .
Si $a < b$ , entonces $\frac{a}{b}$ es el hijo de la izquierda de al menos dos números racionales distintos (ya que al menos aparece dos veces en el árbol), siendo ambos la fracción $\frac{a}{b-a}$ , hecho que contradice que $\frac{a}{b}$ era la fracción de menor denominador entre las que aparecen más de una vez.
De forma parecida se demuestra para $a > b$ .

Por tanto, como hemos dicho antes, tenemos aquí una demostración de que el cardinal de $\mathbb{Q}$ es el mismo que el cardinal de $\mathbb{N}$ , esto es, $\aleph _0$ .