La herencia de Euclides (4) El teorema chino de los restos

Este teorema lo conocemos todos, pero quizás no hayamos pensado que es la garantía de algún isomorfismo de anillos. Lo iremos viendo.

Se enuncia así:

Si M₁, M₂, M₃…M_n son números enteros primos entre sí dos a dos y B₁, B₂, B₃,…B_n, otros números enteros cualesquiera, existe otro número natural N único que cumple NºB_i (mod M_i) para todo i entre 1 y n.
NºB₁(mod M₁)
NºB₂ (mod M₂)
NºB₃ (mod M₃)
…
NºB_n (mod M_n)

Todas las demás soluciones del sistema son congruentes con N respecto a un módulo H igual al producto de los módulos.

La demostración la puedes consultar en cualquier manual. A nosotros nos va interesar especialmente la unicidad de la solución respecto al módulo H. Su fundamento está en que si dos números son congruentes respecto a módulos primos entre sí, también serán congruentes respecto al producto de los módulos. Así, en este caso, si N₁ y N₂ fueran dos soluciones distintas, serían congruentes respecto a todos los módulos M₁, M₂, M₃…M_n  y por tanto congruentes respecto a H, que es lo que garantiza su unicidad.

La resolución más popular de este sistema de ecuaciones es la que ideó Gauss:

Algoritmo de Gauss

Para calcular el número N se sigue el proceso:

 Llamemos H al producto de todos los módulos M_i y sea M’_i = H/M_i.

 Se buscan unas m_i tales que m_i.M’_iº1 (mod M_i) es decir, sus inversos,  y entonces la solución será:

 donde hemos llamado E_i al producto M_i*m_i

 Se puede demostrar que las demás soluciones son congruentes con N módulo H

Ejemplo

Encontrar un número n tal que al dividirlo entre 10 nos dé de resto 7, y al dividirlo entre 9 obtengamos un resto de 3.

H=9.10 = 90 ; M’₁=9 ; M’₂=10 ; m₁=9 (porque 9*9=81º1 (mod 10) ); m₂=1 (porque 1*10=10º1 (mod 9) ). Así tenemos que E₁=9*9=81 y E₂=10*1=10 y por último:

N=81.7+10.3= 597.  Lo reducimos a módulo 90 y queda 57. En efecto, 57º7 (mod 10) y 57º3 (mod 9)

Para encontrar las demás soluciones bastará con ir sumando H=90: 57, 147, 237, 327,…

Estos coeficientes E_i tienen la ventaja de que sólo dependen de los módulos, por lo que se pueden tener almacenados si se van a usar varias veces. Por ejemplo, si el resto deseado para módulo 10 hubiese sido el 2 y para módulo 9 el 6, la solución hubiera sido N=81.2+10.6=162+60=222º42 (mod 90) y se cumple que el resto de 42 respecto a 10 es 2 y respecto a 9 es 6, como deseábamos.

Ya te habrás imaginado que vendría la hoja de cálculo en nuestro auxilio para librarnos de algunos cálculos si el número de ecuaciones aumenta. En la imagen tienes el desarrollo del ejemplo anterior:

En la región superior escribimos los módulos M_i, los valores de B_i y el número de ecuaciones. En el central se calcula H, las H_i y sus inversos (mediante el algoritmo de Euclides interno que estamos usando en esta serie). Por último, se efectúa la suma de los productos triples y se reduce a módulo H, se escriben varias soluciones y se comprueba la primera.

El caso de dos ecuaciones

Si la solución de este problema es única, podríamos definir una función y(a,b,m,n) tal que a cada par de enteros a y b y dos módulos m y n primos entre sí les asignara la solución N tal que Nºa (mod m)  y  Nºb (mod n). Si los módulos no fueran primos entre sí le podríamos asignar el valor de alarma, por ejemplo el cero.

Por otra parte, para todo entero N existen dos enteros únicos a y b tales que Nºa (mod m)  y  Nºb (mod n). Por tanto, tenemos delante una correspondencia biunívoca entre el conjunto Z_m×Z_n y el conjunto Z_mn (Recuerda que m y n han de ser coprimos).

Esta biyección la hemos representado en la hoja de cálculo que nos sirve de herramienta en esta serie. En una hoja dedicada a la misma puedes consultar las distintas correspondencias. En la imagen tienes la existente entre Z₈×Z₉ y el conjunto Z₇₂.

Pero esta correspondencia es más fuerte, porque constituye un isomomorfismo de anillos para la suma y el producto. En efecto, sabemos que para cada resto N de Z_mn, según el teorema chino, corresponde un resto p en Z_m y otro q en Z_n y que esa correspondencia es biunívoca. Supongamos otro N’ que se corresponda con p’ y q’ respectivamente. Así, si N’ºp’ (mod m) y N’ºq' (mod n), podemos sumar y multiplicar miembro a miembro ambas congruencias y quedará: N+N’ºp+p’ (mod m) y de igual forma N+N’ºq+q’ (mod n). Por tanto, a la suma (p,q)+(p’+q’) en Z_m×Z_n le corresponde la suma N+N’ en Z_mn. Esto nos demuestra que la correspondencia es un homomorfismo para la suma. Igual razonaríamos para el producto.

Por tanto, nuestra función y quedará como un isomorfismo entre anillo Z_m×Z_n y el anillo Z_mm


y(a+a’, b+b’)= y(a, b)+ y(a’, b’)   y  y(a*a’, b*b’)= y(a, b)* y(a’, b’)

Compruébalo en la tabla de más arriba m=8 y n=9:y(4,7)=52, :y(2,4)=58 y si sumamos modularmente, y(6,2)=38, que es congruente con 52+58=110, módulo 72. Si multiplicamos modularmente ocurre lo mismo: y(0,1)=64 y 52*58=3016º64 (mod 72)

Correspondencia entre inversibles

Si el resto p es inversible en Z_m, será porque no tiene factores primos comunes con m. De igual forma, si q es inversible en Z_n, no compartirá factores con n. Si aplicamos la función y(p,q)=N (si suponemos que m y n son coprimos), este resultado N será coprimo con m y con n, pues en caso contrario produciría divisores de cero tanto en Z_m como en Z_n. Por tanto, N es inversible en Z_mn

La correspondencia y(p,q)=N convierte inversibles en inversibles.

Volvemos a la tabla ejemplo: 5 es inversible en Z₈, 4 es inversible en Z₉. Les aplicamos la función y y según la tabla queda y(5,3)=13, que es inversible módulo 72.

La consecuencia de esto queda para otra entrada,

La herencia de Euclides (3) El anillo Zm

Recordábamos en la entrada anterior la formación del anillo Z_m mediante clases de restos hasta formar el conjunto {0, 1, 2, … m-1}. Repasa estas páginas si lo deseas:

http://es.wikipedia.org/wiki/Aritm%C3%A9tica_modular
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm
http://mathworld.wolfram.com/ModularArithmetic.html

A este conjunto Z_m se le puede dotar de la suma y el producto módulo m que lo convierten en un anillo conmutativo con unidad, que es el resto 1. Esto lo tienes en

http://personales.unican.es/ruizvc/algebra/anillos1.pdf
http://en.wikipedia.org/wiki/Ring_(mathematics)
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm#residuales

En realidad, bastaría afirmar que Z_m es el anillo cíclico de m elementos. Busca en la Red ese concepto, que es muy sencillo. Por esta estructura cíclica se pensó en llamarles anillos por primera vez.

En los anillos con unidad son importantes los elementos inversibles. De ellos trataremos aquí.

Un elemento A de Z_m es inversible si existe otro elemento X de Z_m tal que A*Xº1 (mod m) Según vimos en la entrada anterior, esta ecuación tiene solución única siempre que A sea primo con el modulo m. Luego los restos primos con m son inversibles.

Por el contrario, si A y m tienen un divisor común, para que la ecuación tuviese solución debería ser divisor también de 1, lo que es imposible. Si el elemento A tiene divisores comunes con m, entonces A no es inversible.

Llamamos divisor de cero en un anillo a aquel elemento A que multiplicado por cierto elemento no nulo C del anillo, da un producto nulo: A*Cº0. En este caso en el que A tiene factores comunes con m, es un divisor de cero, porque si D=MCD(A,m), tendremos que A=A’*D y m=m’*D. Multiplicando A por m’ (que es no nulo) resulta Am’=A’D*m/D=A’m, que es congruente con cero, luego A*m’º0 (mod m) y por tanto divisor de cero.

Los divisores de cero no son inversibles, porque si A fuera inversible y divisor de cero, se daría una igualdad del tipo A*Cº0 con C distinto de cero, pero multiplicando por el inverso resultaría:
A^-1*A*C=C=A^-1*0 lo que daría C=0 en contra de lo supuesto.

Así que:

 Si el elemento A es primo con el módulo m, entonces es inversible, es decir, que existe algún otro elemento B tal que A*B=B*Aº1. En entradas anteriores vimos cómo encontrarlo mediante el algoritmo extendido de Euclides.

 Si el elemento A no es primo con m, es un divisor de cero, y por tanto no inversible.

Grupo de inversibles

El producto de dos inversibles A y B también lo es, y su inverso es B^-1*A^-1, ya que

 (B^-1*A^-1)*A*BºB^-1*(A^-1*A)*BºB^-1*1*Bº1

Como el 1 es inversible trivialmente y el inverso también, tenemos que los inversibles forman grupo abeliano, llamado grupo de las unidades Z*_m


Como es conocido, la función indicatriz de Euler cuenta los números menores que m y primos con él, por tanto, el cardinal del grupo Z*_m coincide con la indicatriz o función j(x) de Euler.

Si m es primo, todos los elementos son inversibles y Z_m se convierte en un cuerpo, pero yo creo que eso ya lo sabías.

La hoja que estamos usando en esta serie de entradas también nos da el grupo Z*_m de unidades de Z_m. Nos seguimos basando en el algoritmo de Euclides extendido.

Para cada elemento de Z_m se va llamando a la rutina euclides(X,m) (de ahí la ventaja de tenerla implementada como una rutina en Basic), mediante la cual se encuentra el MCD(X,m). Si es igual a 1, se escribe el inverso junto al elemento. En la imagen puedes ver el desarrollo para m=12, y nos da como elementos inversibles 1, 5, 7 y 11.

Contando los inversibles se encuentra la indicatriz de Euler, a la que volveremos próximamente.

Finalmente, a la derecha del esquema se construye el grupo multiplicativo de unidades. Observa que, como era de esperar, todos los productos pertenecen al conjunto {1, 5, 7, 11}

Con esta hoja es fácil comprender el teorema de Euler. Observa, por ejemplo, la fila que corresponde al valor 7:{7, 11, 1, 5} Esto quiere decir que 7*1º7, 7*5º11, 7*7º1 y 7*11º5. Imagina que multiplicamos las cuatro congruencias miembro a miembro:

7*1*7*5*7*7*7*11º7*11*1*5   Simplificamos entre 7*11*1*5  (porque son inversibles, si no, no se podría) y queda

7*7*7*7 º1, es decir 7⁴º1. Pero 4 es la función de Euler de 12 y de ahí la comprobación del teorema:

7 ^j(12) º1 (mod 12)

Esto no es una demostración, pero si repites lo mismo con valores generales p y m con p inversible, es fácil demostrar que p ^j(m) º1 (mod m)

Orden de un elemento

Dado un elemento inversible a, llamaremos orden de ese elemento al mínimo número entero tal que a^rº1.

Según el teorema citado, ese valor existe y puede ser j(m). Si es menor, ha de ser un divisor suyo. En efecto, supongamos que j(m) no fuera múltiplo del orden r. Entonces efectuando la división entera entre ambos quedaría j(m)=qr+s, con s<r. Aplicamos esa potencia al elemento a y obtendríamos
1ºa^j(m) ºa^qr+sºa^qr*a^sº a^s , luego a^sº1 en contra del carácter mínimo de r.

Así que el orden ha de ser un divisor de la función j(m)

Hemos incorporado a la hoja el cálculo del orden de los elementos inversibles, pero sería un buen ejercicio que los comprobaras usando la tabla de multiplicar. En la imagen puedes consultar el orden de los elementos en el caso de m=10. Observa que los cuatro son divisores de la indicatriz j(10)=4

La herencia de Euclides (2) La ecuación Ax=B (mod m)

La ecuación AxºB (mod m)

También aquí remitimos a otras páginas para entender las condiciones de esta ecuación. En primer lugar has de conocer la teoría elemental de las congruencias o Aritmética modular. Si no es así, puedes visitar

http://hojamat.es/parra/modular.pdf
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm
http://mathworld.wolfram.com/ModularArithmetic.html

Dentro de esta teoría uno de los primeros temas importantes es el de la resolución de la ecuación lineal AxºB (mod m)  y lo traemos aquí por su relación con el algoritmo de Euclides. En efecto, la ecuación dada equivale a exigir que Ax y B se diferencien en un múltiplo de m, es decir, que Ax+Cm=B. Si leíste la entrada anterior, esto te recordará la Identidad de Bezout.

¿Qué sabes de la estructura de anillo? La repasaremos en la siguiente entrada de esta serie. Por ahora sólo tienes que recordar que en el Álgebra Elemental la ecuación Ax=B para números reales se resuelve multiplicando por el inverso de A, si es que lo posee (siendo distinto de cero en este caso), con lo que tendremos A^-1Ax=1x=x=A^-1B, que es una solución para x.

En los anillos en general no todo elemento posee un inverso, es decir, otro elemento que multiplicado por él lo convierta en la unidad (si esa unidad existe – ver http://es.wikipedia.org/wiki/Anillo_unitario).
En el caso de las congruencias, el anillo Z_m de las clases de restos módulo m está formado por las clases  {0,1,2,3,…m-1} a las que llamaremos restos, y en ellos existen algunos  que pueden no tener inverso. Por ejemplo, si m=9 los elementos de Z₉ son los restos {0,1,2,3,…8} y si elegimos el 6, ningún múltiplo de 6 produce un 1 como resto módulo 9. Veamos (haz tú los cálculos mentalmente para practicar):

6*1º6 (mod 9);   6*2º3 (mod 9); 6*3º0 (mod 9); 6*4º6 (mod 9); 6*5º3 (mod 9); 6*6º0 (mod 9); 6*7º6 (mod 9); 6*8º3 (mod 9)

Nunca resulta un producto congruente con 1, luego el 6 carece de inverso.

Si repasas la teoría del anillo Z_m (lo haremos también en la siguiente entrada) descubrirás que los elementos inversibles son los números primos con m. Como estamos hablando del conjunto de restos {0,1,2,3,…m-1}, el número de inversibles coincidirá con la indicatriz de Euler, como también veremos más adelante. Ya ves, todo se relaciona.

En la resolución de A*xºB (mod m) se presentan estos tipos:

1. Si A es primo con m, existe una sola solución x º A^-1*B (mod m), por ser A inversible.

2. Si MCD(A,m)=d, con d mayor que 1, para que exista solución ha de ser B múltiplo de d. En ese caso se simplifican los tres números A, B y m con lo que se pasa al primer caso. Se puede encontrar una primera solución º A^-1*B (mod m) y existirán en total d soluciones, que vienen dadas por la fórmula x_r = x₀+r*m/d (ver las páginas recomendadas)

En la segunda hoja de la herramienta que estamos usando (Euclides.ods o Euclides.xlsx en
http://hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm) se sigue este procedimiento. Escribimos los tres datos A,B y m. Sin usar macros, la hoja determina si tiene solución o no y si en caso de tenerla es única o múltiple. Si existe, simplifica los datos.

En la imagen se intenta resolver 6Xº4 (mod 10), que tomaremos como ejemplo. La hoja detecta que existen varias soluciones y simplifica 6, 4, 10 a 3, 2 y 5.

El truco está en las celdas I9, I10 y J10. Investiga y aprenderás.

Abajo figura la resolución, que se basa en la rutina Euclides(X,Y) ya explicada en la entrada anterior y en ella se dan estos pasos:

- Se calculan las reducidas y se toma el penúltimo denominador DEN(5)=2, que es un buen candidato a inverso de A (ver la identidad de Bezout en la entrada anterior).

- Se comprueba el último producto cruzado NUM(6)*DEN(5)-DEN(6)*NUM(5)=3*2-1*5=1 y como vale 1, DEN(5)=2 es el inverso por ser 3*2º1 (mod 5. Si el producto cruzado hubiera valido -1 deberíamos haber cambiado de signo.

- Según hemos explicado, la solución será igual a INV(A)*B=2*2=4. En efecto, 6*4º4 (mod 10)

- El MCD(6,4)=2, luego existirán dos soluciones a la ecuación (hablamos en Z₁₀, porque en Z existirían infinitas). Según la teoría, bastará ir sumando el cociente 10/2=5 a las soluciones, lo que nos da (lo ves en la imagen) las soluciones 4 y 9.

Caso homogéneo

Si B es cero, esta ecuación queda como A*x º 0 (mod m) por lo que además de la solución trivial x=0 existirán otras si M.C.D(A,m)>1, y entonces A se confirmará como divisor de cero. Por ejemplo, resuelve con la hoja 6*x º 0 (mod 9) y obtendrás las soluciones 0, 3 y 6, ya que M.C.D(6,9)=3>1. Sin embargo, resuelve 6*x º 0 (mod 7) y sólo obtendrás x=0, ya que en este caso 6 es inversible.

Te proponemos una demostración o comprobación, según te atrevas.

Las diferencias existentes entre las soluciones de la ecuación A*x º B (mod m) son soluciones de la homogénea A*x º 0 (mod m). Inversamente: dada una solución de A*xºB (mod m), si le vamos sumando por separado las soluciones de la homogénea, resulta el conjunto de todas las soluciones de A*x º B (mod m

Nuestro único objetivo ha sido el que veas la relación de la resolución de esta ecuación con el algoritmo de Euclides y que recorras toda la resolución efectuada por la hoja para comprender mejor los detalles de la misma. Cualquier otro aspecto lo podrás ver en las páginas recomendadas, aunque tampoco se puede decir mucho más.

La herencia de Euclides (1) El algoritmo

Hoy iniciamos una serie de entradas dedicadas al algoritmo extendido de Euclides y sus aplicaciones. La orientación será práctica y elemental, y se basará en una hoja de cálculo que abarca todas las técnicas que se explican en la serie. Quien desee profundizar deberá visitar las páginas recomendadas.

No vamos aquí a explicar el algoritmo de Euclides. Mucho mejor lo desarrollan estas páginas y documentos:

http://es.wikipedia.org/wiki/Algoritmo_de_Euclides

http://mathworld.wolfram.com/EuclideanAlgorithm.html

http://hojamat.es/parra/divisibilidad.pdf

Así que supondremos que nuestros lectores conocen el algoritmo y poseen alguna noción de su variante extendida, que viene a reducirse al desarrollo en fracciones continuas y del cálculo de convergentes o reducidas. También se puede interpretar como el recorrido inverso del algoritmo hasta llegar a la Identidad de Bezout. Si no te suena esto mucho puedes profundizar en las páginas anteriormente citadas y en estas:

http://hojaynumeros.blogspot.com/2009/09/fracciones-continuas-1-definicion.html

http://hojaynumeros.blogspot.com/2009/10/fracciones-continuas-2-reducidas.html

y mejor todavía http://www.hojamat.es/parra/fraccioncont.pdf


El algoritmo extendido supone tres fases de calculo:

(1) El algoritmo para el cálculo del MCD. Lo recordamos en esta imagen:

(2) Se despejan los restos a partir de las identidades de la división entera:

(3) Sustituimos r₁ en la fórmula de r₂, con lo que éste dependerá sólo de D y d. Proseguimos sustituyendo r₂ en r₃, éste en r₄ y así hasta llegar al MCD que dependerá entonces sólo de D y d y habremos obtenido la identidad de Bezout: MCD=m*D+n*d

Este proceso puede complicarse algebraicamente, por lo que se sustituye por cálculos más automáticos, como el algoritmo de las reducidas, que explicamos en

http://hojaynumeros.blogspot.com/2009/10/fracciones-continuas-2-reducidas.html

Aquí nuestro objetivo es recorrer con una hoja de cálculo la técnica del algoritmo de Euclides extendido y su aplicación a la resolución de ecuaciones lineales en Z_n, del teorema chino, los elementos inversibles de ese anillo Z_n y su aplicación a las propiedades de la indicatriz de Euler. Todo un programa de trabajo que nos ocupará algunas entradas.

Rutinas y funciones

Para este estudio hemos confeccionado una hoja de cálculo en la que todo el algoritmo extendido se puede expresar mediante funciones. Así, el segundo cociente puede escribirse, según veremos, como COC(2), una convergente en el desarrollo mediante fracciones continuas como NUM(4) y DEN(4), y así con otras.

Esto se ha concebido así porque existen varios cálculos que usan el algoritmo extendido, y es preferible, en lugar de usar varias celdas cada vez, efectuar una llamada a la rutina Euclides(x;y) que nos devuelve los resultados en forma de función.

Para entenderlo es mejor estudiar la primera hoja de la herramienta que hemos confeccionado (Euclides.ods o Euclides.xlsx) y que puedes descargar en esta dirección

http://hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm

Se observa que en la parte superior se desarrolla el algoritmo de Euclides sin uso de macros. El M.C.D(3210,6540) se obtiene por las clásicas divisiones enteras en  las que los restos pasan a ser  divisores. Aprenderás mucho de hoja de cálculo si la analizas.

La segunda parte se activa con un botón. Esto significa que hay una macro detrás. En efecto, es la subrutina Euclides(X;Y), donde X e Y son los números a los que se les calcula el M.C.D. Estas son explicaciones sobre la programación de la hoja, pero puedes prescindir de ellas. Toma esto como una herramienta que sistematiza los cálculos. Lo importante es que según ves en la imagen, aparecen todos los datos en forma de función.

COC: Son los cocientes que aparecen en el algoritmo aplicado a 3210 y 6540 (ver imagen), 0, 2, 26, 1, 3. Estos serían también los cocientes de la fracción continua que desarrolla 3210/6540. Así que esta hoja te permite efectuar esos desarrollos. Puedes comprobar los ejemplos que da Rafael Parra en su documento para entender esto mejor.

Reducidas: También las reducidas de la fracción las tienes en la parte derecha en forma de funciones. Las rotuladas como NUM son los numeradores y DEN los denominadores.

Por curiosidad, efectúa productos cruzados entre ellos y verás que siempre obtienes +1 o -1. Por ejemplo, 26*55-53*27=-1. Esto se puede demostrar que es así. Consulta las páginas recomendadas. El más interesante es el que se forma con las dos últimas: 27*218-55*107=1, por varias razones:

• La última reducida coincide con la fracción primitiva simplificada 3210/6540=218/107, luego esta hoja también te sirve para simplificar fracciones dividiéndolas entre el M.C.D. del numerador y el denominador, que por cierto en la hoja no se llega a efectuar esa división nunca. El algoritmo extendido simplifica los datos originales sin dividir.
• La igualdad 27*218-55*107=1 multiplicada por el MCD 30 y quizás con un cambio de signo (que no es el caso en este ejemplo) se convierte en la Identidad de Bezout, que la tienes también reflejada en la hoja: El MCD 30 expresado como combinación lineal entera de 3210 y 6540: ( -55)* 3210+( 27)* 6540= 30. Además, 30 es el mínimo número entero positivo que satisface una relación lineal de este tipo. Siempre me ha encantado esta propiedad, que algunos autores toman como definición del MCD. Y como señalábamos más arriba, sin usar el concepto de divisor.
• Adelantando el contenido de la siguiente hoja, la igualdad 27*218-55*107=1 permite reconocer 27 como el inverso de 218 en el anillo Z₁₀₇, pero esto es correr mucho por ahora. Lo abordaremos en otra entrada.

Con esta hoja no se pretende sustituir el cálculo manual. En este blog siempre insistiremos en su necesidad. Sólo se pretendía el poder resumir en una sola página todas las consecuencias inmediatas del algoritmo de Euclides extendido.

En otra entrada posterior lo aplicaremos a la resolución de la ecuación lineal en congruencias. Puedes ir consultando la teoría mientras tanto.

Este cromo lo tengo repe (2)

 (Esta es nuestra segunda entrada con la que participamos en la edición 3.1415 del Carnaval de Matemáticas coordinado en esta ocasión por el blog Gaussianos)


Simulación de una colección de cromos


En la entrada anterior realizamos una aproximación a las distribuciones que surgen en las colecciones de cromos. En esta otra intentaremos acercarnos algo más al problema mediante una simulación cromo a cromo. Seguiremos pensando en términos de sobres completos, pero simularemos la aparición de cada cromo individualmente.


Una de las ventajas que tiene la hoja de cálculo es que toda ella es una matriz  de datos, con lo que nos ahorramos dimensionar variables tipo array, ya que las tenemos delante de nuestra vista. Para simular una colección de cromos, lo primero que confeccionaremos es una lista de ellos numerados del 1 al total de la colección. Posteriormente figurarán junto a ellos el total de repetidos que nos han salido.

En la imagen se ha elegido la columna A para la lista de cromos y la B para sus frecuencias de aparición.


Una vez preparada la lista, procederemos a simular la apertura de un sobre. No cansaremos a los lectores con códigos, pero sí señalaremos que los pasos de simulación necesarios son:

•  Se simula la aparición de cada cromo nuevo. Suponemos que no hay malicia en la distribuidora y que todos van saliendo de forma equiprobable.
•  Una vez tengamos el sobre simulado, desecharemos aquellos conjuntos en los que hay cromos repetidos, porque parece ser que esto no suele ocurrir.
•  Admitida la composición del sobre, recorreremos la lista de los cromos que ya tenemos. Si su frecuencia es cero, los consideramos nuevos y se incorporan a la lista de los que tenemos y en caso contrario se consideran repetidos. En ambos casos se incrementa la frecuencia.

Este proceso va bastante rápido, y se puede observar la composición de cada sobre nuevo y la evolución de la lista.

Como observarás en la imagen, se pueden crear contadores para ver los cromos que vamos teniendo, los que nos faltan y los repetidos. También, aunque después no lo hemos visto muy interesante, la máxima frecuencia de repetición que se observa en la simulación. En la imagen vemos que un cromo al menos ha aparecido 9 veces.


En la dirección hojamat.es/blog/cromos.xlsm  tienes la hoja de Excel que contiene esta simulación. En la parte superior se puede realizar el estudio por medias de la entrada anterior y en la inferior, además de simular la compra de X cromos, es posible planificar una serie de simulaciones para equilibrar los resultados. Si la descargas, recuerda que los datos para la simulación son los de la parte superior.


Aquí nos limitaremos a presentar los resultados.


¿Confirma la simulación los resultados aproximados del estudio por medias?
Pues en gran parte sí. En la siguiente tabla comparamos los datos obtenidos por medias binomiales en la entrada anterior y los procedentes de series de 50 simulaciones cada una.

Sobre	Total	Sobres en cada compra
5	250	10
Sobres	Medias	Simulación	Diferencia
0	0	0	0
10	45	45,74	0,74
20	82	83,64	1,64
30	112	114,52	2,52
40	137	137,96	0,96
50	157	159,16	2,16
60	174	176,78	2,78
70	187	190,56	3,56
80	198	201,82	3,82
90	207	208,96	1,96
100	214	216,38	2,38
110	220	223,22	3,22
120	225	227,82	2,82
130	229	232,22	3,22
140	232	235,26	3,26
150	235	238,18	3,18
160	237	239,82	2,82
170	239	242,38	3,38
180	241	243,54	2,54

Las diferencias son muy pequeñas, nunca superiores a 4 cromos, lo que da validez a la aproximación por medias, teniendo en cuenta que tampoco la simulación tiene carácter exacto (aquí todo es azar). También aquí son bastante aproximadas las funciones exponenciales que creamos para explicar la evolución de la colección.


Hay un punto interesante: La esperanza de obtener cromos nuevos en cada sobre es ligeramente superior a la que nos daría la fórmula E=mp de la media binomial con probabilidad constante. Esto es debido a que cada cromo que aparece, si no lo tenemos, disminuye la probabilidad del siguiente y aumenta la de obtener el siguiente repetido. Si nos sale repetido, no altera las probabilidades, porque lo guardamos en otra parte. 


Hemos usado este hecho para estudiar todos los casos que se pueden dar en la apertura de un sobre de 4 cromos en una colección de 200 si ya tenemos 72. Si lees la tabla es natural que te “marees”, porque no es fácil seguir cada caso, pero al final resulta que la media bien calculada es un 1,3% superior a la obtenida sin cambiar las probabilidades:

De este orden son las diferencias entre las dos tablas que hemos confeccionado, por lo que una valida a la otra.
¿Se atreve alguien a sacar una fórmula algebraica que resuma esta tabla? Yo no, pero parece que alguien ha obtenido algo similar.


Resumen de hechos notables


Destacamos algunos hechos observados con ambos métodos (media binomial y simulación) y dejamos que los lectores intenten justificarlos con los medios que les hemos propuesto.


(1) Si compras el mínimo de sobres de una colección (cociente entre el TOTAL y el SOBRE) sólo conseguirás completar un 63% de la misma (en realidad, unas décimas más, entre 63,2% y 63,8% aproximadamente según los casos. Cerca del valor de 1-1/e ¿por qué?)


(2) El momento de compra en el que se igualan el número de cromos que tienes con los que te faltan (mitad de la colección) es cuando has adquirido el 69% de los cromos. (cerca del valor de 100*LN(2) ¿de dónde sale esa estimación?). Los papás se han gastado un 19% más de lo previsto. A partir de ahora saldrán más repetidos que nuevos.


(3) Un momento crítico ocurre cuando al abrir sobres nuevos hay una gran posibilidad de que todos sus cromos estén ya repetidos. Esto se dará cuando la esperanza E en un sobre no llegue a la unidad. Una fórmula aproximada para encontrar ese punto crítico es 

Por ejemplo, en una colección de 240 cromos que vienen en sobres de 6, cuando lleves comprados 71 sobres comenzarán los problemas.


(4) Por último, una fórmula medio empírica para relacionar el porcentaje de la colección P que deseas alcanzar y los sobres comprados:

  

Si la aplicas, no te asustes, y piensa en ir cambiando cromos.


Estos cálculos los hemos comprobado con la simulación y en realidad son algo más favorables, por ese 1,3% de diferencia que existía entre calcular por medias y simular.


Esperemos que con estas ideas iniciales alguien quiera llegar más lejos. Es un buen tema de investigación.

Este cromo lo tengo repe (1)

 (Con esta entrada participamos en la edición 3.1415 del Carnaval de Matemáticas coordinado en esta ocasión por el blog  Gaussianos. Al final de la semana publicaremos la continuación)

Mi nieta y sus amigas ya tienen edad para coleccionar cromos. Así que las hemos visto repetidamente pasar del entusiasmo de los primeros días -“No lo tengo, no lo tengo, este tampoco”-, a las medias desilusiones de los últimos –“Repe, otro repe, este lo tengo, pero no pasa nada, me pondré a cambiar…, o lo regalo”-. Al final, los padres se van al Rastro o piden a las distribuidoras los cromos que faltan. Siempre ha sido así, al menos desde que éramos niños los que ahora somos abuelos.

Este proceso de evolución de la esperanza en obtener un nuevo cromo ha interesado a especialistas y divulgadores, especialmente al explicar las simulaciones. Recuerdo con mucha nostalgia un artículo de Ricardo Aguado, Agustín Blanco y Ricardo Zamarreño, compañeros en los tiempos heroicos (años 80) de introducción de los ordenadores en la enseñanza.

http://www.doredin.mec.es/documentos/00820073007308.pdf

Ellos simularon la evolución de la colección de cromo en cromo, y con una ampliación para el caso de dos coleccionistas que intercambian.

He visto también alguna simulación sobre cromos con MINITAB, pero ninguna con hoja de cálculo. Quien siga este blog sabrá ya que eso es motivo suficiente para que se emprenda en él otra nueva tarea.

Aquí estudiaremos la evolución de sobre en sobre, que es como verdaderamente se compran los cromos y consideraremos una sola colección sin intercambio con otras.

Primera aproximación

Si se tienen ya K cromos y la colección consta de N, la probabilidad de que obtengas h cromos nuevos en un sobre que trae m es, en primera aproximación, de tipo binomial. En efecto, se trata de obtener h éxitos en m intentos dentro de una variable dicotómica (REPE-NO REPE). Pero de esta forma hemos hecho una pequeña trampa, que es suponer que la probabilidad permanece constante mientras sacas cromos del sobre, y eso no es así, pues cualquier cromo no repetido altera la situación, pero ya hemos advertido que es una aproximación para abrir camino. Después pasaremos a una simulación exacta.

Con esta idea, si la probabilidad de que no tengamos un cromo que saquemos del sobre es p=(N-K)/N, la esperanza matemática de obtener m cromos nuevos será, según la teoría de las distribuciones binomiales, E=mp. En cada sobre esperamos obtener E cromos.

(ver http://hojamat.es/estadistica/tema6/teoria/teoria6.pdf)

En esa idea nos basaremos para construir con la hoja de cálculo un modelo aproximado: para cada sobre hallaremos las probabilidades de que salga repetido o no, calculamos E y vamos acumulando. El gran problema de este estudio es que cada cromo nuevo que incorporemos a la colección hace variar la probabilidad p, por lo que tendremos que ir calculando de sobre en sobre. De ahí la utilidad de una hoja de cálculo, aunque, al ser las operaciones bastante simples, se puede usar una calculadora.

Una forma de abordar el tema es construyendo una función de cuatro variables:

Public Function paso_med(total, tengo, sobre, compra)
Dim i, salen
For i = 1 To compra
salen = sobre * (total - tengo) / total
tengo = tengo + salen
Next i
paso_med = Int(tengo)
End Function

Los parámetros son TOTAL, que es el número de cromos de la colección completa, TENGO, los que ya tengo, SOBRE, los que vienen en cada sobre y COMPRA, los sobres que compro. Para llegar al resultado (insistimos, aproximado y estimativo), se recorren los sobres uno a uno, se le estima la media de no repetidos (variable SALEN) y se acumula a los que tengo. Todo el cálculo se recoge en el resultado PASO_MED.

Con esta función puedes construir una tabla de evolución de la colección. Parte de un inicio, que puede ser de 0 cromos, y vas usando de forma recurrente la función anterior hacia abajo, saltando cada vez el número de sobres que desees. Así lo hemos hecho en esta tabla, contando también los cromos comprados y los que salen repetidos:

Sobre	Total	Sobres en cada compra
5	250	10
Sobres	Salen	Compro	Repes	Faltan
0	0	0	0	250
10	45	50	5	205
20	82	100	18	168
30	112	150	38	138
40	137	200	63	113
50	157	250	93	93
60	174	300	126	76
70	187	350	163	63
80	198	400	202	52
90	207	450	243	43
100	214	500	286	36
110	220	550	330	30
120	225	600	375	25
130	229	650	421	21
140	232	700	468	18
150	235	750	515	15
160	237	800	563	13
170	239	850	611	11
180	241	900	659	9

Si consideramos terminada una colección cuando faltan por tener menos de 10 cromos (en ese momento suele aparecer la decisión paterna de comprar los que quedan), según este ejemplo, que no anda muy descaminado, hay que comprar unos 180 sobres en lugar de los 50 que en este caso constituirían el número mínimo, es decir un 360%. Si quisiéramos aproximarnos al último cromo sería necesario comprar más del 500%

De todas las columnas nos fijaremos en primer lugar en la última

Evolución de los cromos que faltan por tener

Si representamos gráficamente el número de cromos que van faltando en  cada compra, obtenemos una gráfica de siguiente tipo

No constituye ninguna sorpresa. Sabemos que el incremento (negativo) del número de los que nos faltan va decreciendo alarmantemente con cada compra. Tampoco nos asombrará el que se ajuste bien a una función exponencial, ya que la probabilidad de disminuir el número de cromos que nos faltan es aproximadamente proporcional a dicho número, en virtud de la probabilidad p=(N-K)/N.

Hemos ido cambiando los parámetros TOTAL y SOBRE, comprobando que una función del tipo

donde X es el número de sobres comprados, se ajusta bastante bien al proceso, como puedes observar en el siguiente ajuste realizado con un total de 200 cromos cuando entran 4 en cada sobre.

Acumulación de repetidos

Si tienes el dato de los que te faltan, también sabes los repetidos que te han salido. Su fórmula aproximada sería:

Te dejamos que razones este resultado. La gráfica de los repes tiene como asíntota y=SOBRE.X-TOTAL. Es fácil de ver: los cromos que ya tengo se acercan poco a poco al TOTAL y SOBRE.X representa los que ya he comprado, luego es lógico que los repetidos se acerquen a su diferencia.

¿Y si quisiéramos llegar a los últimos cromos?

Sin cambiar ni comprar podríamos llegar a un proceso infinito de compra. Por eso, lo lógico es detenerse cuando ya faltan diez o doce cromos y acudir a la compra directa.

Hemos introducido la función inversa (también aproximada), por la que sabiendo los cromos que ya tengo y los que quiero, te devuelve el número de sobres que necesitas comprar por término medio.

Su código es

Public Function compra_med(total, tengo, sobre, quiero)
Dim i, salen, t
i = 1
t = 0
While tengo < quiero
salen = sobre * (total - tengo) / total
tengo = tengo + salen
i = i + 1
Wend
compra_med = i
End Function

Con ella se llega a resultados muy interesantes. En la siguiente tabla se recogen los sobres de cinco cromos que se tendrían que comprar en una colección de 250, partiendo de cero, para llegar a 240, 245 o incluso 249 (con 250 podría llegar a un bucle sin salida). En teoría, si no salieran repetidos, serían 50 sobres, pero en la realidad, observa…

Colección de 250 cromos en sobres de 5
Paro de comprar en	Sobres que he de comprar	Porcentaje respecto al mínimo
240	161	322%
245	195	390%
247	220	440%
248	240	480%
249	275	550%

Al último resultado ya llegaron los autores citados arriba: necesitas comprar más de cinco veces el número mínimo de sobres necesario. También llama la atención que para que sólo te falten 10 debas comprar el 322%. Es todo un aviso a los papás.

¿Qué exactitud tendrá todo esto? Pues en la siguiente entrada efectuaremos una simulación cromo a cromo y realizaremos series para ver si se confirman estos resultados.