El problema de las 12 monedas

Iñaki Úcar7 comentarios

Hoy os quiero plantear un pequeño reto para que penséis un ratito: el problema de las 12 monedas. Sin embargo, antes de meternos en harina, analizaremos un problema mucho más sencillo del que extraeremos una conclusión muy importante a la hora de lanzarnos a resolver el otro.

Vamos a plantear entonces el siguiente reto preliminar:

Disponemos de 9 monedas y una balanza. Sabemos que una de las monedas es defectuosa y pesa menos que las demás. ¿Cómo podemos averiguar cuál es la moneda defectuosa con un total de dos pesadas?

Si bien al principio resulta sorprendente (¡pesando dos veces únicamente?), en realidad si lo pensáis un poco es muy fácil, lo resolveréis enseguida. A continuación muestro la solución. Está oculta para el que no quiera leerla y prefiera sacarla por sí mismo. Si sois unos impacientes, pinchad a continuación y se os mostrará.

Solución (pincha AQUÍ para ver la solución):

¿Fácil, no? Pues gracias a este ejemplo hemos llegado a un resultado muy importante: necesitamos descartar el máximo número de monedas en cada pesada para conseguir nuestro objetivo en el menor número de intentos posible. Y nos hemos dado cuenta intuitivamente de que esto se consigue comparando un tercio con un tercio de las monedas. Para resolver este tipo de problemas es fundamental tener esto último siempre en mente, porque a veces no resulta tan intuitivo.

Ya hemos calentado motores. Ahora vamos con el problema de verdad:

Disponemos de 12 monedas y una balanza. Sabemos que una de las monedas es defectuosa, pero no sabemos si pesa más o menos que las demás. ¿Cómo podemos averiguar cuál es la moneda defectuosa y si pesa más o menos con un total de tres pesadas?

La cosa se complica. Os dejo tiempo para pensarlo y ya publicaré la solución. Necesitaréis un lápiz y un papel. Suerte.

Recordad la conclusión a la que hemos llegado antes, ya que es la manera correcta de afrontar este tipo de problemas. Y se puede demostrar también matemáticamente. Como bola extra, para el que le interese, pongo un pequeño análisis matemático al respecto.

La teoría de la información nos dice que la cantidad de información I que extraemos en cada pesada es igual a la incertidumbre H (o entropía) inicial menos la final. Si ponemos en cada lado de la balanza r monedas de un total de n, tenemos que:

I(r)=H_{inicial}-H_{final}(r)=\log_2 n-\left [ \displaystyle \frac{2r}{n} \log_2 r + \displaystyle \frac{n-2r}{n} \log_2 (n-2r) \right ]

Se demuestra que la información se maximiza cuando r=\displaystyle \frac{n}{3}, y es igual a:

I(\frac{n}{3})=H_{inicial}-H_{final}(\frac{n}{3})=\log_2 n-\left [ \displaystyle \frac{2}{3} \log_2 \frac{n}{3} + \displaystyle \frac{1}{3} \log_2 \frac{n}{3} \right ]=\log_2 3

Por lo tanto, si en cada pesada extraemos una cantidad de información igual a \log_2 3, necesitaremos un total k de pesadas mayor o igual que la incertidumbre inicial partido por la información máxima. Es decir:

k \ge \displaystyle \frac{\log_2 n}{\log_2 3}

En el primer caso, con nueve monedas,

k \ge \displaystyle \frac{\log_2 9}{\log_2 3}=2

Aproximando π

Iñaki Úcar7 comentarios

En 1777, el naturalista francés Georges Louis Leclerc, conde de Buffon, demostró que si disponemos una superficie con líneas paralelas situadas a una distancia D y lanzamos una aguja de longitud L=D de manera aleatoria, la probabilidad de que ésta corte una línea es igual a \frac{2}{\pi}. A este problema de probabilidad geométrica se le llamó la Aguja de Buffon, en honor a su creador.

Generalizando, cuando la distancia entre líneas es mayor que la longitud de la aguja, es decir D>L, esta probabilidad es proporcional al cociente de \frac{L}{D}, por lo tanto:

p=\displaystyle\frac{2L}{\pi D}

Así que podemos utilizar este resultado para aproximar π mediante baja tecnología. En la expresión anterior, p se puede sustituir por \frac{A}{N}, donde N es el número total de lanzamientos de la aguja y A es el número de veces que ésta corta una línea.

Por lo tanto, podemos llenar una cartulina de líneas paralelas con una separación un poco mayor que la largura de una aguja y realizar tantos lanzamientos (lo más al azar posible) como queramos (cuantos más, mejor), contando las veces que la aguja corta alguna línea. Después, utilizaremos la expresión anterior. Sustituyendo como hemos comentado y despejando π, obtenemos:

\pi=\displaystyle\frac{2LN}{DA}

Bonus: si no os queréis aburrir de tirar la aguja, aquí tenéis un simulador.

Lo esencial es invisible a los ojos

Almudena M. Castro2 comentarios

Si un virus implacable aniquilara a todos y cada uno de los mamíferos del planeta, continuaría habiendo vida en la tierra, que apenas se vería afectada por la pérdida. En cambio, si de la noche a la mañana desaparecieran las bacterias, toda la vida del planeta se extinguiría en cuestión de años.

(Steven Johnson, científico americano, en «El mapa fantasma», el fantástico libro que gané gracias al concurso de la Fotoviñeta… me ha recordado a la célebre frase de Saint-Exupéry de «El Principito», que podéis leer en el título)