viernes, 20 de marzo de 2009

Aspectos binarios del problema de la entrada anterior

El contenido de la entrada anterior se podría haber visualizado usando el sistema binario de numeración. La idea fundamental es la siguiente: Si un número n se expresa en sistema binario como un conjunto de unos y ceros, multiplicarlo por 2 equivale a añadir un cero a su derecha, o, en términos muy gráficos, "empujarle" sus cifras hacia la izquierda.

Así, si 7=111(2 su doble 14=1110(2 y multiplicado por 4 28=11100(2

En el problema citado, todos los números impares menores o iguales a n son "empujados" hasta convertirse en los números pares existentes entre n+1 y 2n. Como además esa operación equivale a ir multiplicando por 2, ls números primitivos serán los MFI de los resultantes.

Puedes verlo en la siguiente tabla, que contiene los números del 1 al 22 con su correspondiente desarrollo binario (se han suprimido los ceros): Los impares menores o iguales a 11 (1,3,5,7,9 y 11) son desplazados según las celdas de color naranja (que representan potencias de 2), hasta situarlos en las celdas de color verde, lo que los hace iguales a los números situados a su izquierda. Es mejor verlo que seguir la explicación.


1



1
2


1
3


1 1
4

1

5

1
1
6

1 1
7

1 1 1
8
1


9
1

1
10
1
1
11
1
1 1
12
1 1
3
13
1 1
1
14
1 1 1 7
15
1 1 1 1
16 1


1
17 1


1
18 1

1 9
19 1

1 1
20 1
1
5
21 1
1
1
22 1
1 1 11

Estudiando el problema de esta forma quedan claras algunas propiedades que de otra forma pueden pasar desapercibidas:

(a) Entre n+1 y 2n siempre hay una potencia de 2 ¿Por qué?

(b) (Esta ya se comentó en la entrada anterior) Entre n+1 y 2n, dado un impar k menor o igual que n, existe siempre un número y sólo uno de la forma k*2h

Intenta verlas de forma binaria.

No hay comentarios: