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.

Mallas y colores

Supongamos que nos plantean el siguiente problema: tenemos una malla de 66 nodos y cada nodo está conectado con los otros con un segmento que puede ser de uno de cuatro colores diferentes, demostrar que al menos hay un conjunto de tres nodos que están conectados entre sí por el mismo color.
El problema parece imposible a primera vista pero partiendo de un caso más simple se puede ver que sí existe solución, veamos el problema planteado originalmente:
http://santiprofemates.wordpress.com/2012/02/16/desafio-409-los-mensajeros/

Caso A: tenemos 6 nodos y 2 colores

De cada nodo salen 5 líneas, 3 al menos han de ser del mismo color. Esas líneas van a tres nodos si alguna de las conexiones que conectan esos tres nodos fuera del mismo color tendríamos un triángulo monocolor. Pero en caso contrario tendríamos que las conexiones entre esos tres nodos serían del otro color formando un triángulo monocolor.

Hemos pintado las conexiones del nodo 0 a los nodos 1,2,3 de color rojo y a los nodos 4 y 5 de color azul. Ahora miramos las conexiones entre los nodos 1,2,3 que están provisionalmente en negro y debemos ponerlas en rojo o azul. Si la conexión 1-2 la ponemos en rojo el triángulo 0,1,2 será rojo en su conjunto, luego tenemos que poner 1-2 en azul. Lo mismo ocurre para la conexión 2-3 y para 1-3. Luego nos sale que el triángulo 1,2,3 es azul todo él o sea monocolor.

Caso B: 17 nodos y tres colores

De cada nodo salen 16 líneas, 6 al menos han de ser del mismo color. Esas líneas van a seis nodos si alguna de las conexiones que conectan  esos seis nodos fuera del mismo color tendríamos un triángulo monocolor. Pero en caso contrario tendríamos seis nodos conectados con dos colores diferentes que es el caso anterior A y que sabemos que ha de producir al menos un triángulo monocolor.

Caso C: 66 nodos con cuatro colores.

De cada nodo salen 65 líneas, 17 al menos han de ser del mismo color. Esas líneas van a 17 nodos si alguna de las conexiones que conectan esos 17 nodos fuera del mismo color tendríamos un triángulo monocolor. Pero en caso contrario tendríamos 17 nodos conectados con tres colores diferentes que es el caso anterior B y que sabemos que ha de producir al menos un triángulo monocolor.

Como se ve la generalización es muy sencilla y los siguientes valores para 5,6,7,8... colores sería: 327,1958,13701,109602... nodos

http://en.wikipedia.org/wiki/Ramsey%27s_theorem

Una cuadratura

El desafío consiste pues en transformar un cohete, pongamos por ejemplo de 2×8, en una media luna de la misma área, formada por dos arcos de círculo, explicando la forma de hacerlo o demostrando que no es posible.
http://santiprofemates.wordpress.com/2012/01/04/desafio-403-el-cohete-y-la-luna/

Cuadrar el círculo significa construir un círculo del mismo área que un cuadrado utilizando solo regla y compás. No es posible pues Pi es un número transcendental. Sin embargo los griegos encontraron un caso especial en que podían transformar el área de un triángulo rectángulo en un área formado por dos arcos de circunferencia que es el caso que se muestra aquí.
http://en.wikipedia.org/wiki/Lune_of_Hippocrates

1 Transformamos el rectángulo en un cuadrado de 4X4.
2 El cuadrado lo dividimos por la diagonal en dos triángulos rectángulos y los unimos formando un triángulo rectángulo mayor: EIHG que sigue teniendo el mismo área.
3 El área del sector EIKG es 1/4 Pi (4 * sqrt 2) ^2 = 8 * Pi
4 El área del sector HIJG 1/2 Pi 4 ^2 = 8 * Pi
Son iguales
Como el área de HIKG es común a los dos, nos queda que el área de la cuasi luna KIJG es igual al rectángulo EIHG o sea 16.
Esto demuestra que los griegos eran muy listos y que no tenían televisión pues así gastaron tanto tiempo en estas cosas.

El problema tiene un pequeño defecto y es que la forma de la luna creciente o decreciente no está formada por la intersección de dos círculos sino por un círculo y una elipse. En este caso no hay solución a menos que prohiban la televisión.

Uno de bombas

Tenemos que explotar 84 bombas que funcionan con un interruptor (1- encendido y 0-apagado) 12 de las cuales tienen un defecto que consiste en que están encendidas en posición 0 y apagadas en posición 1.
Las bombas defectuosas son indistinguibles de las que están en buen estado, esto es no es posible saber si una bomba es defectuosa ó no antes de que explote.
Podemos realizar las explosiones que queramos, sabiendo que en cada una, solo explotarán las bombas encendidas (posición 1, para las que estén en buen estado, ó posición 0 para las bombas defectuosas)
En cada explosión todas las bombas deben repartirse entre dos lugares diferentes(A y B), en grupos no necesariamente iguales, cada una con el interruptor en la posición que queramos.

  El desafío es encontrar una estrategia de colocación de las bombas, usando inteligentemente la posición de sus interruptores, para llevar a cabo la explosión de todas las bombas, cumpliendo que en cada explosión el número de bombas que exploten en cada lugar sea el mismo,(el número de bombas que explote en A debe ser igual al número de bombas que explote en B).

http://santiprofemates.wordpress.com/2011/12/29/desafio-402-la-bomba/

El problema en sí es muy bonito salvo por el hecho que está basado en otro que es muy conocido: el de las monedas que hay que conseguir que aparezcan el mismo número de caras en dos grupos diferentes.

Hacemos dos grupos de bombas uno de 12 bombas y otro de 72. Ponemos el primer grupo en A y el segundo en B. Las del grupo B las ponemos a 0, es decir la que normalmente no explota. Sin embargo las de A las ponemos a 1. Supongamos que en A hay X de las malas, luego en B habrá 12-X. En B explotan 12-X y en A explotarán las buenas que son 12-X. Explotan las mismas en ambos lados.

En la siguiente fase explotamos todas las que quedan, para ello les cambiamos el valor del interruptor es decir ponemos las de A a 0 y las de B a 1 y después equilibramos el número de bombas en ambos lados.

Como el número inicial era par y las explotadas también. las que nos quedan también lo son y las podemos repartir a partes iguales entre ambos lados.

1 fase

En A hay X malas y 12 –X buenas

En B hay 12- X malas y 60 + X buenas

Explotan buenas de A y malas de B

2 fase

Quedan X de A y 60 + X de B.

Las de A las ponemos a cero y las de B a 1. Finalmente pasamos 30 bombas de B a A.

Y hacemos explotar las 60 + 2X bombas que quedan.