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.

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?