Las parrillas

Problema de El País
http://sociedad.elpais.com/sociedad/2014/07/29/videos/1406656175_265355.html

La solución
http://sociedad.elpais.com/sociedad/2014/08/05/videos/1407248470_547635.html

Lo que se plantea a continuación es en el caso de reglas ACB  y después NBA cuántas parrillas iniciales pueden resolver el problema y en cuántos conjuntos disjuntos se componen todas las parrillas posibles y de cuántas parrillas se compone cada conjunto.

Explicación de las distintas parrillas con reglas ACB

Las distintas operaciones las denominamos. F1,F2,F3,F4,C1,C2,C3,C4,D1,D2. F es fila, C columna, D diagonal.
Se aprecia que las operaciones son conmutativas y además involutivas. Es decir: F1*F2 = F2*F1  y F1 * F1 := no produce cambio alguno.
Esto quiere decir que el orden da igual y que solo hay 10 posibles operaciones a realizar, pues más volvemos a algún estado anterior.
Sin embargo Si hacemos F1*F2*F3*F4*C1*C2*C3*C4 nos vuelve al estado inicial, luego sobra una de esas operaciones, digamos C4.
Esto quiere decir que F1*F2*F3*F4*C1*C2*C3 = C4.
Realmente podemos poner el signo "=" sustituyendo a uno cualquiera de producto"*" de una cadena que nos vuelva a a la situación inicial, por ejemplo F1*F2*F3*F4 = C1*C2*C3*C4

Pero también F1*F2*F3*F4*C1*C2*C3*D1*D2*C1*F2*F3  nos vuelve al estado inicial, de lo que deducimos que D2 = F1*F4*C2*C3*D1. Luego solo podemos usar D1 o D2 para producir estados diferentes. Es decir como mucho ocho operaciones. Sabemos que hay 2^16 = 65536 parrillas distintas y que con las operaciones descritas no podemos recorrer todas ellas desde una inicial, debe haber varios conjuntos excluyentes del mismo número de parrillas.
Tenemos 8 operaciones a realizar: F1,F2,F3,F4,C1,C2,C3,D1, Codificamos con 1 si usamos una determinada operación y un cero si no. 00000000 significa el estado inicial y sin operaciones y 11111111 el estado que se alcanza realizando las ocho posibles operaciones.  Eso nos da 2^8 = 256 estados diferentes alcanzables desde cada posición inicial -incluiido este-  y 2^16 / 2^8 = 2^8 = 256  conjuntos diferentes. Si la posición inicial está dentro del conjunto  que contiene la parrilla todos 1 tiene solución. O sea probabilidad 1/256.

Explicación de las distintas parrillas con reglas NBA

En el caso de que se apliquen las reglas NBA la cosa es mucho más sencilla pues las casillas de las esquinas y las cuatro del centro las podremos cambiar a nuestro antojo, las primeras con un solo movimiento cada una y las centrales con muy pocos. Así el problema será resoluble si en las 8 casillas restantes hay un número par de -1 y no tendrá solución si es impar. Solo queda calcular el número de casos del total que son pares o impares. Las pares serán la suma de las combinaciones pares:
 C (8,0) + C(8,2) + C(8,4) + C(8,6) + C(8,8) = 1+ 28 + 70 + 28 +1 = 128
Las impares;     C (8,1) + C(8,3) + C(8,5) + C(8,7)  =  8 + 56 + 56 +8 = 128
O sea tiene la misma probabilidad (1/2) de ser resoluble que irresoluble. El número total de parrillas es esas 256 posibilidades multiplicadas por las 16 casos posibles de las esquinas y por los 16 casos posibles de las centrales= (128 + 128) * 16 * 16 = 2^16 = 65536 

Un número curioso

El País plantea un problema de matemáticas nuevo pero fácil.
http://sociedad.elpais.com/sociedad/2013/12/16/videos/1387208927_861334.html

En mi blog ya había dado la solución para un problema casi idéntico:
http://ahoap.blogspot.com.es/2013/02/un-sencillo-problema-matematico.HTML

En este caso:

Es fácil, si al restarle n-1 es divisible por n quiere decir que  L + 1 es divisible por n para todo n desde 2 hasta 12 ambos incluidos. El menor de todos los números que cumple eso se llama Mínimo Común Múltiplo y que es igual a 2^3 * 3 ^2 * 5 * 7 * 11 = 27720, pero 27719 tiene dos cifras repetidas.

Los otros dos múltiplos menores de 100000 son MCM * 2 y MCM * 3, 55440 (55439) y 83160 (83159).

El único que no tiene cifras repetidas y por tanto la solución es:

 

83159

Chismes que se pasan por SMS

Hace unos días me llegó uno de esos SMS que se copian y pegan con texto como este:

No somos supersticiosos... pero este año el mes de Diciembre tiene 5 sábados, 5 domingos y cinco lunes. Esto ocurre una vez cada 823 años y es llamado la bolsa de dinero. Así que copia esto en tu estado y el dinero llegará dentro de 4 días. Basado en el Feng Shui chino. El que no copia no podrá contar con el dinero.

Quien lo había enviado este año ni siquiera había mirado el calendario pues diciembre de 2013 no cumple eso sino diciembre de 2012. Es evidente que el día de la semana en que comience el mes y los dos siguientes de los meses de 31 días serán cinco cada uno a lo largo del mes.

El hecho de que diciembre tenga 5 sábados, 5 domingos, 5 lunes ocurre más o menos cada 7 años como  es bastante lógico -o sea cada vez que el 1 de diciembre cae en sábado- aunque de una forma irregular aparentemente. Lo de cada 823 años es una soberana tontería.
¿Qué proporción exacta de años ocurre eso?

Y para los supersticiosos: ¿Cuándo es más probable que ocurra una desgracia, en martes 13 o viernes 13?

Los dos problemas son más laboriosos que otra cosa pero se tiene un rato de entretenimiento.

El calendario vigente es el Gregoriano que dice que los años bisiestos son los divisibles por 4, pero no los que son divisibles por 100 a menos que sean divisibles por 400, por ejemplo:
1700, 1800,1900,2100,2200,2300 no son años bisiestos.
2000, 2400 son años bisiestos.

¿Con qué frecuencia un año el mes de Diciembre tiene 5 sábados, 5 domingos y cinco lunes?

Construyamos un calendario perpetuo:

2001 LMXJ SDLM JVSD MXJV DLMX VSDL XJVS 

2029 LMXJ SDLM JVSD MXJV DLMX VSDL XJVS  

2057 LMXJ SDLM JVSD MXJV DLMX VSDL XJVS  

2085 LMXJ SDLM JVSD MXJV

2101 SDLM JVSD MXJV DLMX VSDL XJVS LMXJ

2129 SDLM JVSD MXJV DLMX VSDL XJVS LMXJ

2157 SDLM JVSD MXJV DLMX VSDL XJVS LMXJ

2185 SDLM JVSD MXJV DLMX

2201 JVSD MXJV DLMX VSDL XJVS LMXJ SDLM 

2229 JVSD MXJV DLMX VSDL XJVS LMXJ SDLM  

2257 JVSD MXJV DLMX VSDL XJVS LMXJ SDLM  

2285 JVSD MXJV DLMX VSDL   

2301 MXJV DLMX VSDL XJVS LMXJ SDLM JVSD

2329 MXJV DLMX VSDL XJVS LMXJ SDLM JVSD

2358 MXJV DLMX VSDL XJVS LMXJ SDLM JVSD

2385 MXJV DLMX VSDL XJVS

 Para conocer cualquier año simplemente restamos tantos múltiplos de 400 como haga falta para estar en el rango 2001-2400, por ejemplo el calendario del 3333 (-3*400) =2133 . O sea equivalente al del año 2133. Es decir un año que comienza en Jueves.
Cada año queda definido por el día de la semana que corresponde al 1 de enero y si es bisiesto o no. Los años bisiestos los he coloreado en violeta. El módulo siete de 365 es 1 y por tanto el de 366 es 2. Esto quiere decir que el día 1 de enero en años sucesivos va aumentando en un día de la semana excepto cuando el año año anterior fue bisiesto en caso aumenta en 2, es decir si el anterior año empezó en domingo siendo bisiesto el siguiente empieza en martes.

Si un mes de Diciembre tiene 5 sábados, 5 domingos y cinco lunes quiere decir que el año empezó en domingo si es bisiesto o en lunes en años normales. Solo hay que contar en la tabla anterior los domingos bisiestos y lunes no bisiestos y sale:
15 DOMINGOS BISIESTOS
11 11 11 10 = 43 LUNES NO BISIESTOS
Frecuencia 58 / 400 = 0,145. O sea ligeramente más frecuente que el aproximado 1/7 = 0,142857

Solución problema el profesor de probabilidad y combinatoria

http://ahoap.blogspot.com.es/2013/08/el-profesor-de-probabilidad-y.html
El método es que cada alumno elija en primer lugar la cartulina que ocupe el lugar que es igual al número asignado, si ahí no se encuentra su número, elige la que ocupa el lugar que es igual al número que acaba de descubrir y así sucesivamente.
¿Qué probabilidad tienen con este método de aprobar?
En primer lugar hay que observar que los 40 números forman subconjuntos sin intersección entre ellos que llamamos ciclos ya que al final volvemos al primer número. Los ciclos pueden ser desde longitud 1 -un número está colocado en su número de orden- hasta longitud 40 -en este caso para volver al número inicial hemos de recorrer todos los números.

En la imagen pongo un ejemplo de como el que tiene el número 1 va destapando diversas cartulinas
En la 1 se encuentra la 13 que a su vez contiene la 39 y esta la 31 y así varias más hasta  que finalmente la 8 contiene el 1, fin del ciclo.
1->13->39->31->15->17->22->26->8--------->1
Los alumnos aprueban si no hay ningún ciclo de longitud > de 20. Esto es evidente pero también es evidente que si hay un ciclo mayor de 20 no puede haber otro también mayor de 20. Son excluyentes y por tanto la probabilidad de que haya uno mayor que 20 es la suma de:

Probabilidad de que haya uno igual a 21
más probabilidad de que haya uno igual a 22 
...
...
más probabilidad de que haya uno igual a 39
más probabilidad de que haya uno igual a 40
¿Cuál es la probabilidad de que haya un ciclo de 40? Es fácil, en la primera posición pueden estar 39 números -todos menos el 1- en la segunda levantada 38 -todos menos el 1 y el anterior. Y así sucesivamente nos sale (N-1)! o sea 39!. A esto lo llamamos permutaciones restringidas. La probabilidad es pues 39! / 40! = 1 / 40. Casos favorables dividido casos posibles.
Para calcular los demás casos dividimos los 40 números en dos grupos: los que van a formar parte del anillo y los que no. Así sin importar el orden tenemos las combinaciones de 40 elementos tomados de n en n. Eso es 40! / (40 -n )! n! Por cada uno de esos casos se tiene las "permutaciones restringidas" que hemos definido antes. Y a su vez con los 40 -n restantes podemos hacer todas las permutaciones:
Casos favorables: (40! / (40 -n )! n!) * (n-1)! * (40 -n )! = 40! / n
Casos posibles: 40!
Probabilidad de que haya un anillo de longitud n (n> 20),   1 / n
Probabilidad de aprobar es: 1 - 1/21 - 1/22 - 1/23 ...-... 1/39 - 1/40
Aproximadamente sale un 32 % de aprobar.

El profesor de probabilidad y combinatoria

Érase una vez  un profesor de matemáticas que tenía la convicción de que todos los alumnos de su clase debían ser suspendidos pero su generosidad le obligó a darles una pequeña oportunidad de que aprobaran y además sería a todos en su conjunto.

Para ello les propuso el siguiente juego:
Los cuarenta alumnos tendrían un número asignado del 1 al 40 e irían pasando uno a uno por su despacho donde en una mesa tendría cuarenta cartulinas con los cuarenta números escritos boca a abajo. Cada alumno podría ver el número que estaba escrito en 20 cartulinas y si una de ellas coincidía con el suyo habría superado la prueba. Para aprobar, todos tendrían que haber encontrado su número en los 20 intentos.
Antes de empezar la prueba los alumnos se reúnen y pueden decidir una estrategia, pero una vez comenzada la prueba no se pueden comunicar entre ellos ni pueden modificar la disposición de las cartulinas que como he dicho se encuentran boca a abajo, por ejemplo en un rectángulo de 4 filas de 10 números.

¿Cuál es la mejor estrategia que pueden seguir los alumnos?
¿Qué probabilidad tienen de aprobar con esa estrategia?

Un sencillo problema matemático

Vi en la siguiente URL una curiosidad sobre el número 2519:
http://easycalculation.com/funny/interesting-facts/number-2519.php

Ahí simplemente se menciona como una curiosidad pero no se dice nada del porqué ni si hay una fórmula que dé el número para otros casos. En matemáticas las curiosidades suelen tener explicación así que me propuse encontrarla y si así fuera plantearlo como un problema.

Los números al dividirlos por 2 pueden dar resto 0 o 1 y se llaman par e impar respectivamente. Para cualquier otro número N, tenemos N posibles restos. Cada N números hay 1 que es divisible por N o sea resto cero, y también 1 que su resto es N-1. Justamente al número que da resto N-1 le sigue un número que da resto 0, o sea divisible. Si empezamos desde el 1 todos dan resto 1 y si vamos incrementado  secuencialmente veremos que los restos van variando según se ha descrito.
Así hasta llegar a un número que sea múltiplo de todos los números propuestos. ¿Cómo se llama el mínimo múltiplo de todos ellos? Mínimo Común Múltiplo. Y el número anterior nos dará que al dividirlo por cada uno de los N resto N-1. O sea la solución es MCM - 1.

Así fue el planteamiento:

¿Cuál es el menor número que:
al dividirlo por 2 da resto 1
al dividirlo por 3 da resto 2
al dividirlo por 4 da resto 3
al dividirlo por 5 da resto 4
al dividirlo por 6 da resto 5
al dividirlo por 7 da resto 6
al dividirlo por 8 da resto 7
al dividirlo por 9 da resto 8
al dividirlo por 10 da resto 9
al dividirlo por 11 da resto 10 ?

Por ejemplo 23 no vale porque al dividirlo por 2 da 1 de resto, al dividirlo por 3 da 2, al dividirlo por 4 da 3 pero al dividirlo por 5 nos da 3 de resto. 

Fue resuelto rápidamente.

La única dificultad -con el razonamiento anterior- es calcular el MCM pero hasta mentalmente se puede hacer en un caso como este.
Hay que factorizar -descomponer en primos- los números 2 a 11 y después multiplicar todos los primos elevados a la máxima potencia que tienen y descartar el resto: 8 descarta a 4 y 2. 9 descarta a 3.
6 y  10 quedan descartados porque son compuestos de primos tenidos en cuenta en 8, 9 o 5.
8X9 = 72
72X5 = 360
360 X 7= 2520. Que es MCM hasta el 10. Y 2519 el "valor curioso" de la URL.
Multiplicar por 11 es mutiplicar por 10 + 1 o sea 25200 + 2520.  O sea 27720 y por tanto 27719 es el número pedido.

Si seguimos, 12 es 2^2 X 3 o sea que es el  mismo MCM y la misma solución. Con 13 ya es difícil hacerlo mentalmente, pero lapicerito y sale 360360 de MCM y 360359 como solución.
14 tiene ya esos primos en el MCM así que no varía. Lo mismo el 15. Con 16 = 2^4 tenemos que multiplicar por 2 que muy fácil ya que son grupos de tres cifras iguales sin posible acarreo o sea 720720. Y la solución extendiendo el problema hasta 16 inclusive es 720719.

Obsérvese la obviedad de que el número a partir de 10 siempre acaba en 9.

Mensaje secreto

Descripción breve:
Un agente envía información codificada mediante la publicación de un carácter ASCII cada día en el periódico. Elige al azar un carácter cualquiera que se corresponde con siete bits, solo puede modificar uno de ellos o ninguno. El carácter modificado o no lo publica.
¿Cuántos bits de información puede enviar diaramente?

http://santiprofemates.wordpress.com/2012/03/01/desafio-51-mensaje-secreto/

El número de bits que se pueden codificar con ese método es 3.
Vamos a utilizar un concepto que llamamos semilla que es de tres bits. La semilla no se envía se calcula tanto por el transmisor como por el receptor.

Calculamos la semilla del número aleatorio mediante la fórmula:

S2 = a + b + c + d
S1 = a + b +  e + f
S0 = a + c + e + g
La operación  + es  la or-exclusiva
Siendo abcdefg el número. Obtenemos S2S1S0
El número que queremos codificar le hacemos la or-exclusiva con la semilla.
El resultado nos dice qué bit debemos cambiar.
En recepción calculamos la semilla que nos dice el valor codificado.
 

Explicación: tenemos la posibilidad de definir tres funciones de paridad en función de los dígitos del número que hemos obtenido aleatoriamente. En la recepción también se  podrán obtener esas mismas funciones. Las tres funciones de paridad han de producir diferentes valores para dos números que difieran en un solo dígito. Esto se consigue si las funciones de paridad se hacen de tal manera que se correspondan con los pesos de la codificación de la posición del dígito:

Posición dígito a cambiar	S2	S1	S0
No hay cambio	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

Así cada cambio de bit se corresponderá con un cambio diferente en la semilla, mientras el 7 = 111 cambiará los tres bits de la semilla.  El 1  = 001 solo cambiará el de menor peso. El 3 cambiará los dos de menor peso. Y así el resto.

Ejemplo: Tenemos el valor 0101010 calculamos la semilla y nos sale: 0, queremos codificar un 7.
7 orx 0 = 7. Debemos modificar el bit 7: 1101010
El receptor ve ese valor  y extrae la semilla = 7. 
Ejemplo; Tenemos el valor 1000010. La semilla es 5. Queremos codificar un 4
5 orx 4 = 1, Debemos modificar el bit 1,  1000011.
El receptor extrae 4 de semilla.