Skip to content

Solución: números en base Fibinaria

by en 16/02/2014

¡Hola!

Un domingo más, vamos con la respuesta del acertijo de la semana. En él os hablábamos de la “base Fibinaria”, como aquella en la que el valor de cada dígito en lugar de ser una potencia de la base de numeración es uno de los números de Fibonacci. Os dábamos varias parejas de números en base fibinaria y os pedíamos que nos diérais su suma.

Esta semana Gualterio nos dijo que el acertijo lo resolvió hace tiempo y que para no aprovecharse de eso, prefería que la respuesta la dieran otros… ¡y David se animó y nos la dio! Y no sólo eso, sino que además acertó 🙂 Efectivamente, en base fibinaria:

  • 1 + 1 = 10
  • 10 + 10 = 101
  • 100 + 100 = 1001
  • 1000 + 1000 = 10010
  • 10000 + 10100 = 101001

Veamos cómo se llegaba a esas soluciones.

Como hemos dicho, en base fibinaria, los dígitos de nuestros números no tienen como valores potencias de una base determinada, sino los dígitos de la sucesión de Fibonacci que, os recordamos, se calculaba así:

  • Fib(0) = 1
  • Fib(1) = 1
  • Fib(i) = Fib(i-1) + Fib(i-2)

Como ejemplo, el inicio de la sucesión está compuesta por los números:

1, 1, 2, 3, 5, 8, 13, 21, 34, …

En realidad, en base Fibinaria no aparece el número 1 repetido, por lo que el dígito más a la derecha (el menos significativo) vale 1, el siguiente vale 2, el siguiente 3, etcétera. El lunes os poníamos como ejemplo la forma de averiguar el valor real del número 1010 en base Fibinaria:

1×5 + 0×3 + 1×2 + 0×1 = 7

y os contábamos que muchos números se pueden representar de varias formas, como por ejemplo el 10, que es 8+2 (10010) y 5+3+2 (1110). Para ser considerado correcto, un número fibinario no puede tener dos dígitos a 1 seguidos. La representación se la debemos a un belga llamado Zeckendorf, quién demostró que todos los números positivos se pueden representar de este modo.

Las dos primeras preguntas que os hacíamos eran fáciles. En concreto, ¿cuánto es (1+1)fibinario y (10+10)fibinario? Para averiguarlo, podemos fácilmente convertir los sumandos a base decimal, sumar en base decimal, y volver a base fibinaria, pues los números son pequeños y resulta sencillo:

  • (1 + 1)fibinario = uno + uno = dos = (10)fibinario
  • (10 + 10)fibinario = dos + dos = cuatro = (101)fibinario

Pero claro, esto se pone complicado con casos más grandes, por lo que os animábamos a que intentarais resolverlo sin pasar por base 10.

Antes de aprender a sumar en base fibinaria vamos a ver cómo sumamos… en decimal 🙂 De pequeños, nos enseñaron a sumar llevando o con “acarreo” en lo que constituye, seguramente, el primer verdadero algoritmo que aprendemos. Se trata de sumar los dígitos por separado, de derecha a izquierda. Si al sumar obtenemos un número mayor que 10, ponemos como resultado el último dígito y “nos llevamos una”, poniendo un 1 encima de los siguientes dos dígitos.

 
87 
+ 46 
—————–
 
1  
87 
+ 46 
—————–
11  
87 
+ 46 
—————–
33 
11  
87 
+ 46 
—————–
133 

Nada demasiado sorprendente 🙂 El proceso de sumar 1 al dígito siguiente ocurre porque nos quedamos sin dígitos. Al sumar 7+6 en el ejemplo, obtenemos “trece”, y ese número no podemos escribirlo con un único dígito. Debido a eso, ponemos el dígito de menos valor del resultado (el 3) y lo demás lo anotamos para ser sumado en la columna de la izquierda.

Si en lugar de estar en base 10 estamos en base 2, el proceso es exactamente el mismo, salvo que los únicos dígitos que podemos usar son el 0 y el 1. ¡Al sumar en base 2 es mucho más fácil tener acarreos!. Veamos un ejemplo:

 
1011 
+ 1001 
————————
 
1  
1011 
+ 1001 
————————
11  
1011 
+ 1001 
————————
00 
11  
1011 
+ 1001 
————————
100 
1 11  
1011 
+ 1001 
————————
0100 
1 11  
1011 
+ 1001 
————————
10100 

Como os decíamos, la necesidad del acarreo se debe a que no podemos poner números por encima del 1 (en el caso de la base 2). Pero… vamos a suponer (veréis por qué dentro de un momento) que lo permitimos momentáneamente. Es decir, que sumamos cada columna de dígitos por separado, sin preocuparnos de los acarreos, aunque eso suponga utilizar dígitos que están fuera del rango de la representación. En ese caso, el resultado sería:

 
1011 
+ 1001 
————————
2012 

Hemos obtenido el número 2012 “en base 2” que, claramente, es incorrecto. Lo que toca ahora es arreglar el número. Y para eso, tenemos que preocuparnos de los acarreos, algo que no hemos hecho al sumar directamente cada columna. Olvidándonos de los sumandos originales, nos centramos en el resultado y lo vamos recorriendo de derecha a izquierda, para quitar los dígitos que están en 2:

2 0 1 2 El 2 no es válido. Restamos 2 y sumamos 1 al siguiente
2 0 2 0 El 2 no es válido. Restamos 2 y sumamos 1 al siguiente
2 1 0 0 El valor 1 es válido
2 1 0 0 El 2 no es válido. Restamos 2 y sumamos 1 al siguiente
1 0 1 0 0 El 1 es válido y no hay más dígitos. Hemos acabado

Como véis, ¡¡hemos llegado a la misma respuesta que cuando sumábamos con acarreos desde el principio!! De hecho, este último proceso parece de lo más artificial, ¿quién iba a querer sumar así?

Pues… nosotros, ahora mismo 🙂 Antes de seguir leyendo, te recomendamos que intentes resolver el acertijo por ti mismo. ¡Es mucho más gratificante conseguirlo, aunque sea tras haber leído hasta aquí!

¿Ya? ¿Lo has resuelto? ¡Pues entonces sigamos para ver si has llegado a nuestra misma solución! 🙂

Manualmente resolvimos antes las sumas (fibinarias) de 1+1 y 10+10. Vamos con la siguiente pregunta que os hacíamos (100+100), utilizando lo que hemos aprendido. Para eso, sumamos los dos números, sin preocuparnos del acarreo, aunque eso suponga usar dígitos que están fuera de la representación. En este caso:

 
100 
+ 100 
————————
200 

La respuesta es por tanto 200, que no es un número correcto en base fibinaria, donde sólo se pueden usar los dígitos 0 y 1. Toca, como antes, arreglar el número. El problema es que ahora el acarreo no es tan sencillo. Lo que tenemos es que:

(200)fibinarioErróneo = 2×Fib(2) = 2×3 = 6

Lo hemos terminado poniendo en base 10 para que veamos intuitivamente que tenemos que buscar la forma de representar el 6 en base fibinaria y eso resulta ser (1001)fibinario (en decimal, 5+1). Es decir (200)fibinarioErróneo = (1001)fibinario lo que indica que el acarreo nos ha llevado a sumar uno al siguiente dígito de la izquierda, y también al dígito situado dos posiciones más a la derecha. ¡¡Tenemos acarreo en los dos sentidos!!

Esto podemos demostrarlo matemáticamente con la fórmula de los números de Fibonacci. Sabemos que:

Fib(n) = Fib(n-1) + Fib(n-2)

Si lo que tenemos es 2×Fib(n) (como en nuestro número (200)fibinario):

2×Fib(n) = Fib(n) + Fib(n) = Fib(n) + Fib(n-1) + Fib(n-2) = Fib(n+1) + Fib(n-2)

¡Ahí lo tenéis!

¿Cuál es el proceso entonces? Como con la base dos, sumamos sin preocuparnos de los acarreos, y luego arreglamos el número realizando este curioso acarreo donde sumamos 1 al dígito siguiente y al dígito anterior del anterior. Por tanto:

2 0 0 El 0 es un dígito válido
2 0 0 El 0 es un dígito válido
2 0 0 El 2 no es válido. Restamos 2 y…
1 0 0 1 …sumamos 1 al fibit siguiente y al anterior del anterior
1 0 0 1 El 1 es válido; no hay más dígitos. Hemos terminado.

¡Uau!

Vamos con la siguiente pregunta que os hacíamos. Sumar (1000 + 1000)fibinario. Como antes, empezamos sumando sin preocuparnos de los acarreos y obtenemos (2000)fibinarioErróneo. Y ahora nos toca arreglar el número, que resulta ser similar al anterior:

2 0 0 0 El 0 es un dígito válido
2 0 0 0 El 0 es un dígito válido
2 0 0 0 El 2 no es válido. Restamos 2 y…
1 0 0 1 0 …sumamos 1 al fibit siguiente y al anterior del anterior
1 0 0 1 0 El 1 es válido; no hay más dígitos. Hemos terminado.

Si lo conviertes a decimal, verás que lo que acabamos de decir es que 5+5=10 🙂

Vamos con el último, que es el más difícil, y que guarda una sorpresa. Consistía en sumar (10000 + 10100)fibinario que es (20100)fibinarioErróneo. Veamos la serie de transformaciones:

2 0 1 0 0 El 0 es un dígito válido
2 0 1 0 0 El 0 es un dígito válido
2 0 1 0 0 El 1 es un dígito válido
2 0 1 0 0 El 2 no es válido. Restamos 2 y…
1 0 0 2 0 0 …sumamos 1 al siguiente y al anterior del anterior
1 0 0 2 0 0 El 1 es válido; no hay más dígitos.

En esta ocasión, el acarreo nos ha llevado a sumar 1 a un dígito que ¡ya estaba en 1! Eso hace que el número al que hemos llegado no sea válido y hay que volver a hacer un recorrido completo, otra vez de izquierda a derecha. Si lo hacéis, llegaréis al número final, el (101001)fibinario. Lo que acabamos de decir es que 8+11=19 🙂

¡Hasta aquí la explicación del acertijo de la semana! Esperamos que os haya resultado curiosa esta forma de escribir los números y la necesidad de tener acarreo “hacia atrás”. Si lo habéis entendido y os animáis a programar una solución, como siempre podéis probarla aquí. Pero ¡tened cuidado! Hay que estar atentos cuando el acarreo afecta a los dos primeros dígitos de la derecha porque… al sumar 1 al fibit “anterior del anterior” ¡¡el número se termina y no existe esa posición!! Además, intencionadamente, en ninguna de nuestras preguntas ocurría que aparecieran dos fibits seguidos a 1, algo que no se permite. En ese caso hay que realizar otro tipo de acarreo que tendréis que descubrir vosotros. De modo que todavía os tocará pensar un rato para sacarlo 🙂 Si lo conseguís, ¡contádnoslo!

Anuncios

From → Soluciones

One Comment
  1. Oscar permalink

    Increíble explicación… O.O

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: