martes, 28 de septiembre de 2010

Reproducir resultados (2)

Para averiguar si un número es estrictamente no palindrómico necesitaremos una función que nos diga si es palindrómico o no en una base dada, y después recorrer todas las bases entre 2 y N-2 para descubrir si hay o no resultados negativos.

Diseñaremos la función ESCAPICUA(n, b), donde n será el número a probar y b la base del sistema de numeración. Esta función nos devolverá un 1 si el número es palindrómico y 0 si no lo es. Usamos 1 y 0 porque son más cómodos que True y False.

Necesitaremos organizar dos fases de cálculo

a) Extracción de las cifras de n en base b y almacenamiento de las mismas en una matriz c
b) Emparejamiento de las cifras de forma simétrica para averiguar si son todas iguales por parejas (caso palindrómico) o bien existe una que no es igual a su simétrica.

Primera fase: extracción de las cifras

Usaremos un algoritmo voraz, en el que n va disminuyendo de valor, con lo que la velocidad se acelera. Dividimos en cada paso n entre b, quedando el cociente como nuevo valor de n y el resto como cifra nueva. Cuando el cociente sea cero, paramos.

Puedes estudiarlo en Basic.En el listado hemos copiado n en m para preservar su valor

' extraer cifras
nopara=true    Esta variable determina si se para o no el proceso
nc=0                    Contador de cifras
while nopara
q=int(m/b):r=m-q*b  Se halla el cociente y el resto de m entre la base
if q=0 then nopara=false  Si el cociente es cero, se para
nc=nc+1:c(nc)=r:m=q   Se incrementa el contador de cifras y se almacena la nueva
wend


Segunda fase: Comparación entre cifras

Una vez almacenadas las cifras, si sólo hay una, se declara el número como palindrómico. En caso contrario, si se detecta una desigualdad entre cifras simétricas, se declara como no palindrómico.

En Basic

esca=1  Admitimos que es capicúa
if nc>1 then  Si hay más de una cifra, analizamos
for q=1 to int(nc/2)
if c(q)<>c(nc-q+1) then esca=0  En caso de desigualdad, no es capicúa
next q
escapicua=esca
end if


Si deseas implementar esta función en tu hoja de cálculo, copia el código completo:

















Public function escapicua(n,b)
dim c(50)
dim m,q,r,nc,esca
dim nopara as boolean

m=n
' extraer cifras
nopara=true
nc=0
while nopara
q=int(m/b):r=m-q*b
if q=0 then nopara=false
nc=nc+1:c(nc)=r:m=q
wend
esca=1
if nc>1 then
for q=1 to int(nc/2)
if c(q)<>c(nc-q+1) then esca=0
next q
escapicua=esca
end if
end function


Con esta función se puede rellenar una columna que actúe sobre las bases comprendidas entre 2 y N-2. Por ejemplo, en la imagen puedes comprobar que el número 19 es estrictamente no palindrómico:


Los primeros números estrictamente no palindrómicos son:

1, 2, 3, 4, 6, 11, 19, 47, 53, 79, 103… (Visto en la Wikipedia)

Hemos aplicado la prueba a 2011 y, efectivamente, no es palindrómico para ninguna base comprendida entre 2 y 2010.

Con ello hemos reproducido un resultado, con la consiguiente diversión e incremento de nuestra confianza en la comunidad matemática.Si te atreves, codifica una función ESTRICTCAP, que decida si un número es estrictamente no palindrómico. Bastará programar en Basic lo que en la imagen hemos efectuado con columnas.

sábado, 25 de septiembre de 2010

Reproducir resultados (1)

Somos muchos en el mundo. Estudiamos en una Facultad de Matemáticas, llevamos años y años enseñándolas, seguimos estudiando distintos temas y leyendo libros de divulgación, entretenimientos o curiosidades, pero nunca hemos publicado un resultado matemático apreciable. Sólo nos queda disfrutar con desarrollos ajenos, resolver placenteramente problemas de más o menos dificultad y… reproducir resultados.

Lo de obtener lo que ya han descubierto otros puede ser formativo y entretenido si lo intentamos con herramientas distintas a las del primero que lo logró. En este blog usamos las hojas de cálculo, lo que nos exige la construcción de tablas en las que se llevan al límite las posibilidades de las funciones que traen implementadas, o bien, que es una tarea más apasionante, implementar algoritmos adecuados mediante macros.

Proponemos una reproducción:

He leído por ahí, en la Wikipedia, Wolfram Mathworld o una página similar, que el número 2011 es estrictamente no palindrómico. Se llaman así los números N que no son palindrómicos (capicúas) para bases comprendidas entre 2 y N-2. No se consideran bases mayores porque todos los números se expresan en ellas como capicúas (se admite que lo son los de una cifra) para bases mayores que N-2. ¿Sabrías razonarlo?

Alguien se ha tomado la molestia de ir probando el 2011, imagino que de forma automática, para todas las bases comprendidas entre 2 y 2010.

¿Puedes reproducir ese resultado con hoja de cálculo? 

En la siguiente entrada lo intentaremos

lunes, 20 de septiembre de 2010

Cajas y bolas (1)

(Esta entrada es la aportación de este blog la VI Edición del Carnaval de Matemáticas cuyo anfitrión será el Blog de Sangakoo.)

Con esta cuestión iniciamos una serie de entradas (algo que nos llevará algunos meses) a la que titularemos “Cajas y bolas”, porque usaremos esta metodología para repasar conceptos de Combinatoria.

En una entrada anterior proponíamos averiguar de cuántas formas distintas se pueden colorear de negro cincuenta celdas de un tablero de 10 por 10. La solución que proponíamos era 1008913445455641933334812497256.

El problema propuesto equivale a repartir 50 bolas en 100 cajas, de forma que
  • No puede haber más de una bola por caja. 
  • Se considera que las cajas se distinguen unas de otras, pero que las bolas son indistinguibles.


En la imagen se han repartido 5 bolas en 16 cajas sin que haya ninguna caja con más de una bola. Es fácil ver que el  número total de tales repartos es el número combinatorio C16,5 ya que la operación ha consistido en extraer un subconjunto de 5 elementos en un conjunto de 16, lo que constituye la definición de combinaciones sin repetición.

En el problema que nos ocupa de colorear 50 cuadrados negros en un cuadrado de 100 la solución será  C100,50 = 100!/(50!*50!) = 1008913445455641933334812497256

Este modelo concreto de cajas y bolas (bolas indistinguibles y no más de una bola por caja) tiene otras muchas aplicaciones:

Loterías

En la Lotería Primitiva de España se extraen seis bolas de un total de 49, que es lo mismo que acomodar seis bolas indistinguibles en 49 cajas numeradas. Quizás no hayas entendido la frase anterior. Repásala. Es como si en el sorteo tuviéramos un tablero de 49 números y marcáramos con una X los premios que han salido. Por tanto, el número de posibilidades es el número combinatorio C49,6 = 13983816

Este mismo modelo concreto de cajas y bolas (más adelante veremos otros) nos servirá, pues, en todos los sorteos que se efectúen mediante extracciones y en los que no influya el orden de los resultados.


Permutaciones con repetición

El ejemplo de las 5 bolas alojadas en 16 cajas también se puede interpretar como que los símbolos VACÍA, LLENA se han permutado de todas las formas posibles, tomando 11 veces VACÍA y 5 veces LLENA, luego podemos usar números combinatorios también en este caso de permutaciones de dos elementos con repetición y número de apariciones fijado para cada uno.

En el ejemplo del tablero de 10 por 10, serían permutaciones de 50 cuadros negros y 50 blancos. Según lo que sabemos de Combinatoria, su número sería 100!/(50!*50!), que coincide con la solución propuesta del número combinatorio C100,50.

¿Qué cambiaría si las bolas fueran distinguibles?

martes, 14 de septiembre de 2010

Múltiplos decrecientes

A principios de verano leí una interesante propuesta en el blog
“Mis acertijos” de Rodolfo
http://www.misacertijos.com.ar/2010/06/mi-forma-de-dividir.html
cuya lectura recomiendo.

Lo que se afirma esencialmente en esa entrada es que si un número, por ejemplo 137821, deseamos saber si es divisible por otro, como 283, basta reiterar la siguiente operación: se multiplica el primer número salvo la última cifra por precisamente la última cifra del segundo, y después se procede al revés, el segundo salvo la última multiplicado por la última del primero. Después se restan los resultados:

13782*3–28*1 = 41318

Reiteramos esta forma de calcular, y si llegamos a cero, el primer número es divisible entre el segundo:
4131*3-28*8= 12169; 1216*3-28*9=3396; 339*3-28*6=849; 84*3-28*9=0

Según esto, el terminar en cero es señal de que son divisibles. ¿Por qué funciona esto?

No he encontrado ninguna referencia a este tema, por lo que intentaré un desarrollo propio. Ruego a mis seguidores me corrijan si cometo alguna inexactitud.

Llamaré “producto cruzado” al propuesto por Rodolfo. Si expreso ambos números A y B (los tomaré enteros positivos) en el sistema decimal y separo la última cifra, los podré expresar así:

A=10m+n y B=10p+q, 
donde n y q son las últimas cifras, con lo que el producto cruzado vendrá dado por mq-pn.

Podemos afirmar lo siguiente:

Si A es múltiplo de B, el producto cruzado mq-pn también será múltiplo de B y además menor que A y positivo. Por tanto, reiterando obtendremos una sucesión decreciente de múltiplos de B que llegarán al cero.

Si A es múltiplo de B podremos escribir A = kB siendo k un entero positivo, y plantear este sistema de ecuaciones:

Y en forma matricial

Podemos despejar10 y 1 mediante la matriz inversa, y quedará:



Lo que nos lleva a estos valores:


10=B(qk-n)/(mq-pn)  y  1=B(-pk+m)/(mq-np) 

y de esta última obtenemos lo que nos interesa:

mq-np=B(m-pk), es decir, que el producto cruzado es múltiplo de B

Nos queda ver que A es mayor que mq-np y que éste es positivo o cero.

A>=10m>mq>mq-np, luego los múltiplos son decrecientes. Además, mq-np es siempre positivo o cero ¿de qué depende esto? No es difícil de razonar. Inténtalo.

Por tanto, en algún momento llegarán al cero, ya que por la forma de calcular todos son positivos.

Espero no haber cometido ningún error u olvido. En caso contrario ruego a los lectores me avisen y publico una actualización.


Ideas para ampliar y reflexionar

(a) ¿Se mantendrá la propiedad estudiada en bases distintas de 10? Puedes efectuar pruebas con nuestra calculadora en cualquier base (http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#calcubase). Si la respuesta es afirmativa, ¿cómo afecta a este proceso el uso de base 100 o 1000?

(b) No todos los pares de números múltiplo-divisor llegan al valor cero con el mismo número de pasos. Dependerá de la cifras de arrastre, como hemos visto en párrafos anteriores. ¿Podrías concretar más?

(c) ¿Qué obtendríamos con el algoritmo propuesto si A no es múltiplo de B pero ambos lo son de un tercer número C?

martes, 7 de septiembre de 2010

Unas vueltas alrededor de la anterior entrada (Ampliación)

En la anterior entrada proponíamos la construcción de un simulador para el problema planteado sobre los cincuenta cuadrados negros y los cincuenta blancos (Ver propuesta).

Por si no lo has intentado te ofrecemos dos versiones (Excel y OpenOffice.org) en la dirección

http://hojamat.es/blog/lineafront.zip


Si entras en el editor de Basic podrás analizar los algoritmos empleados. Son muy instructivos.

Nosotros hemos programado una serie de 500 simulaciones, lo que nos ha dado una estimación de 91,096 para la media de líneas frontera y 6,128 para la desviación estándar, así como que sólo son ligeramente probables los resultados centrales y altamente improbables los extremos. De hecho, no han aparecido números de líneas frontera inferiores a 66 o superiores a 111.

Si lo deseas, pon tu hoja de cálculo a "echar humo" para afinar los resultados.

Aquí tienes algunas frecuencias centrales que hemos obtenido:

90    32    6,40%
91    25    5,00%
92    34    6,80%
93    35    7,00%
94    29    5,80%
95    25    5,00%
96    17    3,40%
97    19    3,80%
98    16    3,20%
99    16    3,20%

¿Cómo saber su probabilidad? Confieso que ese problema me desborda. Si alguien especialista en Combinatoria pasa distraídamente por el blog, y así lo desea, nos podría ayudar en la siguiente cuestión:

Dado un número concreto de líneas frontera, ¿se puede calcular el número de formas distintas de pintar cincuenta cuadrados negros capaces de producir ese número de fronteras?

Ahí lo dejo, y ¿quién sabe?

sábado, 4 de septiembre de 2010

Unas vueltas alrededor de la anterior entrada

Proponíamos hace unos días este problema:

Se tiene un tablero cuadriculado de 10 por 10 casillas. La mitad de sus casillas se pintan de blanco, y la otra mitad de negro. Un lado común a dos casillas en el tablero se llama lado frontera si estas dos casillas tienen colores diferentes. Determinar el mínimo y el máximo número de lados frontera que puede haber en el tablero (OMCC).

La solución al mismo es que el mínimo vale 10, y se da cuando un rectángulo de 10 por 5 se pinta de negro y su complementario de blanco. El máximo, 180,  se alcanza si todos los cuadrados blancos y negros están alternados como en el juego del ajedrez.

Unas cuestiones se nos ocurren:

a) ¿Son posibles soluciones del problema todos los números comprendidos entre 10 y 180, o existe algún valor que nunca se produce?

b) ¿De cuántas formas se pueden elegir los cincuenta cuadrados que se pintan de negro?
La solución es 1008913445455641933334812497256. En la siguiente entrada la explicareremos

c) ¿Se podría organizar alguna simulación con ordenador? Se plantearían dos problemas:

c1) Si rellenamos aleatoriamente cincuenta cuadrados con color negro, habrá que tomar nota de los que ya poseen ese color antes de elegir el siguiente (que deberá ser blanco)

c2) Deberemos diseñar un procedimiento que recorra todos los bordes interiores de los cuadrados del tablero y lleve la cuenta de los que unen cuadrados de color diferente.

C3) Se podría completar con la estimación de la media

Estúdialo, que seguiremos dando pistas.