lunes, 27 de febrero de 2012

Terrones de azúcar

Idea para el aula

Ayer compré un envase de terrones de azúcar y me llamó la atención la información que daba sobre el contenido: 126 terrones.





Después de pensar un poco creí estar en disposición de adivinar las dimensiones de cada terrón. Medí el envase y resultó tener las dimensiones 8,8, 11,2 y 5,5 respectivamente, de forma aproximada. En contra de lo que creía, aún tenía dudas después de la medida, pero me acordé de que los terrones tienen una cara casi cuadrada.

¿Cuál fue mi solución?

Este tipo de actividad es la que yo habría desarrollado en un taller de Matemáticas si estuviera en activo, pero ahora sólo puedo proponerlo. Creo que daría lugar a una interesante discusión en grupo.

lunes, 20 de febrero de 2012

El primorial


(Con esta entrada participamos en el Carnaval de MatemáticasEdición 3.1 cuyo anfitrión es  Scientia potentia est)




La palabra primorial se suele usar con tres significados distintos:

(1) Un número es primorial si es igual al producto de los k primeros números primos. Por ejemplo, 210=2*3*5*7. Los primeros primoriales son

1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230, 200560490130, 7420738134810, 304250263527210, 13082761331670030,…
(https://oeis.org/A002110)

(2) Llamaremos primorial de un número N y lo representaremos por N# al producto de todos los números primos menores o iguales que él. Los primeros valores de esta función son (están incluidos n=0 y n=1)

1, 1, 2, 6, 6, 30, 30, 210, 210, 210, 210, 2310, 2310, 30030, 30030, 30030, 30030, 510510, 510510, 9699690, 9699690, 9699690, 9699690, 223092870, 223092870,… 
(https://oeis.org/A034386)

(3) Llamaremos primo primorial o primo de Euclides al que tiene la forma p#+1, siendo p primo. Esta definición recuerda que son estos los números usados por Euclides en su demostración de la infinitud del conjunto de primos. Los primeros son

2, 3, 7, 31, 211, 2311, 30031, 510511, 9699691, 223092871, 6469693231, 200560490131, 7420738134811, 304250263527211,...
(https://oeis.org/A006862)

También se suelen llamar primos primoriales a los de la forma p#-1

Como ves, tenemos donde elegir. Nos quedaremos con las dos primeras. Es fácil programar en el Basic de las hojas de cálculo la función primorial de N si posees la función ESPRIMO, ya explicada en este blog. (Puedes buscarla en el Apéndice de http://hojamat.es/publicaciones/hojanum1.pdf)
Su código podría ser

Public Function primorial(n)
Dim k, p
p = 1
For k = 1 To n
If esprimo(k) Then p = p * k
Next k
primorial = p
End Function

No es el más eficiente, pero para explicaciones vale. Con él se puede formar la tabla de la función


Como era de esperar, su crecimiento es notable. A partir de la tabla se puede construir el gráfico




















Se ha usado una escala logarítmica para ver mejor su estructura escalonada.

¿Dónde tienen lugar los saltos?¿Por qué unos tramos son de dos, otros de cuatro o de cinco? Preguntas con respuesta sencilla que te puedes plantear.

Algunas propiedades

Todos los números primoriales están libres de cuadrados y cada uno de ellos posee más factores primos distintos que los números menores que él. Ambas propiedades son triviales. La segunda se puede expresar de otra forma:

La función omega de un número primorial tiene mayor valor que las correspondientes a los números que le preceden.

Recuerda que la función omega cuenta los factores primos distintos de un número natural. No hay que cavilar mucho para entenderlo. Esta definición nos proporciona otra idea fácil:

Para un valor dado k de la función omega, el primorial k# es el número más pequeño con ese valor de omega.

El primorial y el factorial

La forma de crecer el primorial nos recuerda a la del factorial. ¿Cuál es mayor? Evidentemente, el factorial. ¿Qué números forman el cociente n!/n#?

Pues a ese cociente entenderás que le podamos llamar el “compositorial de n”. Reflexiona sobre el porqué de ese nombre. ¿Lo has encontrado?, pues demuestra esto:

Dos primoriales consecutivos se corresponden con el mismo compositorial.

Tienes los compositoriales en http://oeis.org/A036691 y la función compositorial de un número en http://oeis.org/A049614

Descomposición factorial de un compositorial

Este es un buen momento para recordar la fórmula de Polignac
(Ver http://hojaynumeros.blogspot.com/2009/02/formula-de-polignac.html)


Si descompones cualquier factorial mediante esa fórmula, bastará restarle una unidad a cada factor primo para que resulte la descomposición factorial del compositorial. No es tan complicado como parece.

Lo vemos con un ejemplo: Descomponer en factores primos el compositorial de 18.

Puedes abrir la hoja de cálculo polignac.xls o polignac.ods desde la dirección
http://hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm
Con ella descubrimos que 18! Se descompone tal como se ve en la imagen:


Restamos una unidad a cada exponente y nos resultará comp(18)=215*37*52*7=12541132800

Si visitas http://oeis.org/A049614 podrás comprobar este resultado.

En realidad, el primorial de N es el radical de su factorial. Parece un trabalenguas, pero es que se llama radical de un número al mayor divisor libre de cuadrados que tenga, lo que nos lleva a que el radical es el producto de los factores primos elevados todos a la unidad. Eso es lo que significa el primorial respecto al factorial. Por cierto, es una función multiplicativa, pero esto se alarga y es mejor dejarlo.

domingo, 12 de febrero de 2012

Suma de los elementos de todos los subconjuntos

Tomemos el conjunto formado por los n primeros números naturales {1, 2, 3, …, n}. Imagina que formamos todos los subconjuntos posibles y que en cada uno sumamos los elementos, acumulando después todas las sumas en un total general ¿Cuánto valdrá esa suma S(n) de todos los elementos de todos los subconjuntos? Al conjunto vacío le asignamos suma 0.

Te damos un ejemplo:

S(4)=80, porque tendríamos que sumar (escribimos entre paréntesis la suma parcial de cada subconjunto) lo siguiente: (0)+(1)+(2)+(3)+(4)+(1+2)+(1+3)+(1+4)+(2+3)+(2+4)+(3+4)+(1+2+3)+(1+2+4)+(1+3+4)+(2+3+4)+(1+2+3+4)=10+3+4+5+5+6+7+6+7+8+9+10=27+26+27=80

Los primeros resultados para la función S son S(1)=1; S(2)=6; S(3)=24; S(4)=80; S(5)= 240; S(6)=672, formando la sucesión 1, 6, 24, 80, 240, 672, 1792, 4608, 11520, 28160, 67584, 159744...

Intentemos justificar estos resultados

Podemos encontrar una definición por recurrencia. Que S(1)=1 y S(2)=6 es fácil de justificar. A partir de ahí razonamos de una forma muy común en Combinatoria: Sea Sn-1 la suma de los subconjuntos de {1, 2, 3, …, n-1}. Para formar la suma Sn deberemos añadir el elemento n a los subconjuntos.

Entonces estos serán de dos formas:

(a) Subconjuntos que no contienen al elemento n. Su suma será la misma Sn-1

(b) Subconjuntos que contienen al elemento n. Estarán formados por los subconjuntos de 1, 2, 3, …, n-1} a los que añadimos a cada uno el elemento nuevo n. El número de tales subconjuntos equivale a 2n-1. Como cada uno se ha incrementado en el elemento n, la suma se habrá incrementado en n*2n-1. Luego será Sn-1+ n*2n-1.

Si reunimos las sumas (a) y (b) nos resulta la fórmula de recurrencia:

       Sn=2Sn-1+ n*2n-1

En efecto: S(3)=2*6+3*4=12+12=24;  S(4)=2*24+4*8=48+32=80; S(5)=2*80+5*16=160+80=240.

Es fácil programarlo en hoja de cálculo. Sólo incluimos una tabla creada así sin dar más detalles:

S(n)      2n-1    n
1           1         1
6           2         2
24         4         3
80         8         4
240      16        5
672      32        6
1792    64        7
4608  128        8

Generalmente nos sentimos más a gusto con una fórmula algebraica. Ahí va:

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

S(1)=1*2*(1/2)=1; S(2)=2*3*1=6; S(3)=3*4*2=24; S(4)=4*5*4=80…

Se puede demostrar por inducción. Vemos que se cumple para los primeros casos, luego podemos suponer que se cumple para n-1, es decir, que Sn-1=(n-1)*n*2n-3.

Aplicamos la fórmula de recurrencia presentada más arriba y nos queda:

Sn=2*(n-1)*n*2n-3+n*2n-1=(n2-n)* 2n-2+2*n*2n-2=(n2-n+2n)* 2n-2=n(n+1)2n-2  lo que completa la demostración.

Otra demostración

La suma T=1+2+3+4+…+n equivale al número triangular n(n+1)/2. Esta suma se repite en S(n) varias veces. Por ejemplo, la suma de todos los elementos unitarios es T. También vale T la suma de elementos del conjunto total. Veamos los demás conjuntos:

Clasifiquemos los subconjuntos por su número de elementos.  El número de los que tienen r elementos es Cn,r. Por razones de simetría, los elementos 1,2,3,…n se repiten en total, para un mismo r, igual número de veces, luego la suma de los elementos de estos subconjuntos es múltiplo de T.

Cada elemento se repite en los conjuntos de r elementos tantas veces como indique Cn-1,r-1, luego la suma de todos equivaldrá a Cn-1,r-1*T. Si sumamos todos nos dará:

T*Cn-1,0+T* Cn-1,1+ T* Cn-1,2+ T* Cn-1,3+…+ T* Cn-1,n-1 = T*2n-1 = n(n+1)/2*2n-1 = n(n+1)*2n-2 , que es la fórmula propuesta.

¿Se te escapó algún detalle? Repasa, repasa…

Quienes acostumbráis a visitar OEIS habréis descubierto que estas sumas forman la secuencia http://oeis.org/A001788.  Si la estudiáis  podréis descubrir la gran cantidad de interpretaciones que tiene.

martes, 7 de febrero de 2012

Simulación para vagos (o que no sabemos lo suficiente)

El otro día, buscando temas por ahí, me topé con la secuencia http://oeis.org/A051293

1, 2, 5, 8, 15, 26, 45, 76, 135, 238, 425, 768, 1399, 2570, 4761, 8856, 16567, 31138…

que representa el número de subconjuntos de {1,2,3,...,n} cuya media aritmética es entera.

Por ejemplo, en el caso de 4, los subconjuntos con media entera son {1}, {2},{3},{4},{1,3},{2,4},{1,2,3} y {2,3,4}, en total 8.

Me pareció un tema interesante e intenté abordarlo usando congruencias y después particiones, pero la cosa se complicó y me sentí vago. Quien tenga más disposición que yo puede seguir con ello. Además, el autor de esta secuencia en OEIS se vio obligado a conjeturar cosas. Malo.

¿Y si lo simulara? 

Yo nunca lo había intentado con conjuntos de este tipo y quizás podría reproducir la secuencia, al menos con algún pequeño error. Me puse a ello:

(a) Simulación de subconjuntos

Se puede usar la técnica de tirar una moneda: recorremos los elementos de {1,2,3,...,n} y para cada uno de ellos tiramos una moneda. Si sale cara, lo incluimos en el subconjunto, y si sale cruz, no lo incluimos. En los lenguajes de programación disponemos de la función ALEATORIO(), que en Basic es RND. Así que el algoritmo de formación de un subconjunto de {1,2,3,...,n} podría ser similar a este esquema:

Randomize
For i=1 to n
If rnd(1)>1/2 then … se incluye en el subconjunto
Next i

Para quienes no lo sepan, randomize hace que cada vez que usemos el algoritmo se forme una secuencia distinta de números aleatorios (en realidad, seudoaleatorios)

(b) Identificación de las medias aritméticas enteras

Como en nuestro caso nos interesa la media en cada subconjunto, las sentencias presentadas en Basic se podrían concretar en el sentido de que para cada subconjunto tomemos nota del número de elementos y de su suma, para luego dividir y hallar la media.

Podemos definir la variable n para recoger el número de elementos y la variable s para formar la suma. En ese caso las sentencias anteriores se podían modificar así:

Randomize
n=0:s=0
For i=1 to n
If rnd(1)>1/2 then n=n+1:s=s+i
Next i
media=s/n

De esta forma obtendríamos la media de los elementos de cada subconjunto.

Ahora sólo nos quedaría comprobar si la media es entera.  Esta prueba consistirá en ver si media=INT(media). Podemos generar muchos  conjuntos aleatorios, por ejemplo 10000 y contar aquellos en los que la media es entera. En caso afirmativo incrementamos un contador.

Por último, lo que marque el contador lo convertimos en proporción dividiendo entre 10000 y multiplicamos después  por 2n para que cuente subconjuntos. Después presentamos resultados. Aquí tienes un listado aproximado en Basic de Excel:

Randomize
a = 0  Contador de exitos
Input n  o cualquier otra forma de capturar n


For i = 1 To 10000


ActiveWorkbook.Sheets(1).Cells(3, 3).Value = i  esto sólo sirve para saber por dónde va la simulación
c = 0 cuenta elementos del conjunto aleatorio
s = 0 suma elementos del conjunto aleatorio
b = 1 / 2 es la media, que la declaramos al principio no entera.


For k = 1 To n se genera el conjunto aleatorio
m = Rnd(1)
If m < 1 / 2 Then c = c + 1: s = s + k: b = s / c
Next k


If b = Int(b) Then si es entero se incrementa el contador
a = a + 1
ActiveWorkbook.Sheets(1).Cells(fila, 6).Value = a / i * 2 ^ n  Valor adaptado a 2^n
End If


Next i

Los resultados obtenidos han sido bastante acertados. Transcribimos los correspondientes a una sola pasada del algoritmo:

N S(N) Simulación Errores relativos
3 5 5,0576 0,01152
4 8 8,031209363 0,00390117
5 15 14,8704 -0,00864
6 26 25,5872 -0,015876923
7 45 44,6464 -0,007857778
8 76      76,34683468 0,004563614
9 135 133,9707708 -0,00762392
10 238 236,032 -0,008268908

Como era de esperar, al aumentar N se presentan desviaciones mayores. Los errores relativos son más estables.

Pues hemos hecho el vago, pero con diversión.