Las Doce Monedas (o Las Doce Bolsas de Oro)

Estamos trabajando en un problema de la lógica a partir de IMP Nivel 1, titulada "Doce bolsas de oro". Podemos resolver el problema cuando el resultado del primero pesaje es "igual", pero si es desigual necesitamos demasiados pesajes. El problema dice que un rey quiere encontrar la única bolsa de oro falso de sus 12 bolsas, sólo tiene una balanza del equilibrio y quiere hacerlo en 3 pesajes. No sabe si el oro falso es más pesado o más ligero que el oro auténtico. ¿Conoce este problema? Nos ha resultado muy interesante, y hemos estado trabajando en ella desde hace una semana. Agradecería cualquier orientación que se puede dar. Gracias, C.

(Nota. Este problema frecuentemente se presenta como el problema de"Doce monedas": se le da doce monedas, once de ellos justo y uno falso, y pide que use tres pesajes en una balanza para encontrar la moneda falsa y decir si es pesado o ligero. Llamaremos a este el Problema de Monedas de Peso Desigual. Si usted sabe de antemano si la moneda falsa es pesada o ligera, el problema es más sencillo, utilizando n pesajes se puede distinguir entre la moneda falsa 3^n monedas; por ejemplo, con 3 pesos se puede distinguir una moneda falsa de las 27 monedas en lugar de sólo 12. Llamaremos a este el Problema de Monedas de Peso Conocido. Si no está familiarizado con este problema más sencillo, usted debe estudiarlo primero. Está escrito como otro artículo de Lo Mejor de MathNerds aquí: La Moneda Falsa.)

¿Quiere una sugerencia? Haga clic aquí.

Haga clic aquí para ver la respuesta completa.

Sugerencia 1

Comience con algo pequeño. Doce monedas y tres pesajes es mucho, ¿puede trabajar un problema menor? Parece imposible deducir algo basado solamente en un pesaje, pero con dos pesajes usted puede encontrar la moneda falsa y su peso entre tres monedas. ¿Cómo?

Comience con algo grande. Trate de encontrar un método general que trabajará para n pesajes. Resulta que usted puede encontrar la moneda falsa y su peso sobre los (3^n - 3) / 2 monedas. El caso de doce monedas es n=3; usted puede también encontrar la moneda falsa de los 39 por medio de 4 pesajes, o un total de 120 con 5 pesajes. Tenga en cuenta que esto es sólo la mitad el número de monedas de el Problema de Monedas de Peso Conocido puede manejar, estamos en desventaja porque no sabemos si la moneda falsa es ligero o pesado. Vamos a llamar a un problema que permite n pesajes, un problema de orden n

Sugerencia 2

Pensando en algo pequeño: Llamamos los tres monedas A, B, C, y hacemos estos dos pesajes:

1. A contra B
2. B contra C

Que significa esto:

• Si cualquier de los pesajes muestra el mismo peso, sabemos que esas dos monedas son justos y la tercera moneda es falsa, y porque la tercera moneda participa en el otro pesaje con una moneda, que ya sabemos es justa, ya podemos decir si es ligero o pesado.
• Si ningún pesaje muestre igual, hay dos casos:
  • Moneda B es lo mismo in ambos pesajes (ambos pesadas o ambos ligeras); entonces B es la moneda falsa y es pesada o ligera de acuerdo con el pesaje.
  • Moneda B es ligera en un pesaje y pesada en el otro. Este caso es imposible, porque B tendría un peso que es entre los pesos de A y C, que nos da tres pesos diferentes en lugar de dos.

Se nota que giramos y no canjeamos para el segundo pesaje: Giramos A fuera de los platillos, giramos B del platillo derecho al platillo izquierdo, y giramos C en el platillo derecho. Esto es lógicamente equivalente a intercambio de A y C, pero resulta es más fácil pensar en rotación que en intercambio. Podemos usar esta método de rotación más generalmente, para distinguir tres grupos del mismo número de monedas. Siempre podemos escoger el grupo con la moneda falsa, y podemos decir si la moneda falsa es ligero o pesado. Y también: Incluso podemos tratar el caso en que los tres grupos contienen sólo las monedas justas, porque entonces va a equilibrar ambos pesajes (esto no puede suceder si hay una moneda falsa). El método de la rotación será nuestra principal herramienta para resolver el Problema de Monedas de Peso Desigual.

El Problema de Monedas de Peso Conocido tiene un estructura recursiva; es decir, contiene un problema más pequeño de tamaño 3^{n-1}, y podemos reducir el problema de orden n a otro problema de orden n-1 usando un pesaje. El Problema de Monedas de Peso Desigual también tiene estructura recursiva, pero es menos simple, y más difícil hallar. ¿Puede hallarla?

Sugerencia 3

Mirando a los tamaños, podríamos especular que si el Problema de Monedas de Peso Desigual contenga una versión más pequeña de sí misma, sería un paso más pequeño y contendría (3^{n-1} - 3) / 2 monedas. Habría sobrantes

monedas, lo que es lo mismo como el Problema de Monedas de Peso Conocido de orden n-1. ¿Coincidencia? Tal vez no. Podría ser posible salirse de una orden n Problema de Monedas de Peso Desigual a uno de un Problema de Monedas de Peso Desigual de orden n-1 o un Problema de Monedas de Peso Conocido de orden n-1, probablemente se basa en el resultado específico del pesaje. Un problema evidente es que necesitamos al menos dos pesajes para hacer cualquiera conclusión, mientras que sólo se les permite (en promedio) un peso por cada paso hacia abajo. Con el fin de lograr algún avance, vamos a dejarnos temporalmente dos pesajes por paso abajo. Luego más adelante veremos si lo podemos arreglar de alguna forma para usar sólo un peso. (Este es un método común en el descubrimiento matemático: hacer algunas suposiciones adicionales, o relajar algunas de las limitaciones, y ver si podemos obtener la respuesta en estas condiciones más favorables. Si lo podemos, entonces habremos aprendido algo sobre el problema, que podemos utilizar para atacar el problema original. Si no puede resolver un problema, trate de encontrar un problema relacionado, pero más simple, ¡que pueda solucionar!)

Sugerencia 4

Vamos a dividir arbitrariamente las (3^n - 3) / 2 monedas en dos grupos: Uno tiene 3^{n-1} monedas (esto llamamos el grupo mayor) y uno con (3^{n-1} - 3) / 2 monedas (el grupo menor). Dividimos el grupo mayor en tres subgrupos con 3^{n-2} monedas en cada uno, y aplicar el método de rotación para decidir si el grupo mayor contiene la moneda falsa. Esto necesita dos pesajes.

Esto no resuelve nuestro problema por completo, porque todavía estamos utilizando demasiados pesajes, es decir, dos para cada paso hacia abajo. Pero cuando el grupo mayor contiene la moneda falsa en realidad estamos bien, porque hemos pasado dos pesajes (dejando sobrante n-2 pesajes), y lo hemos reducido a un Problema de Monedas de Peso Conocido de orden n-2. Sabemos que podemos completarlo con n-2 pesajes. No somos tan afortunados en el caso del grupo menor, porque hemos pasado dos pesajes, pero sólo hemos reducido la orden del problema por uno.

Ahora piensa en cómo podríamos reducir el número de pesajes en el otro caso, donde el grupo mayor tiene solamente monedas justas, y por esto el grupo menor tiene la moneda falsa.

El Resto de la Respuesta

Podemos combinar dos pesajes en uno. Como antes, dividir el grupo mayor en tres partes iguales (llamarlos A, B, C), y dividir el grupo menor en tres partes iguales (llamarlos a, b, c). Poner una parte mayor y una parte menor en cada platillo, pero no giran las partes menores. Es decir, en el pesaje primero pesar (A y a) contra (B y b), en el pesaje segundo pesar (B y a) contra (C y b). ¿Qué pasa?

Si el grupo mayor contiene sólo las monedas justas, entonces la rotación no tiene ningún efecto sobre los resultados del pesaje. Por otra parte, si el grupo mayor contiene la moneda falsa, entonces el grupo menor sólo contiene monedas justas, por lo que la rotación no tiene ningún efecto sobre los resultados: un pesaje es igual y uno no, y de que podamos decir cuál subgrupo mayor contiene la moneda falsa, y podamos decir su peso.

¿Cuál es la ventaja de los grupos añadido a y b? Cuando el grupo mayor contiene solamente monedas justas, el resultado de nuestro pesaje es el mismo que el resultado del pesaje a contra b, que es el primero pesaje que usaríamos en el método de rotación para distinguir a, b, y c! Conseguimos un pesaje "extra" (es decir, estamos compartiendo los resultados de cada pesaje con dos pasos), y esto nos permite reducir el número de pesajes de uno por cada paso.

Resumen y Ejemplo

Eso fue un poco complicado! Vamos a trabajar de manera explícita los pasos para 12 monedas para asegurarnos que son legales todos los pesajes.

Para resolver 12 monedas, las dividen en un grupo mayor de 9 monedas y un grupo menor de 3 monedas, y dividir estos en tres grupos iguales A, B, C, de 3 monedas cada uno y tres grupos iguales a, b, c de una moneda cada uno. Los pesajes son las siguientes:

1. (A y a) contra (B y b).
2. (B y a) contra (C y b).
3. Existen dos casos para el tercer pesaje, según los resultados de los primeros dos pesajes:
   1. Si ambos resultados son los mismos, entonces la moneda falsa está en el grupo menor, y ya sabemos de los dos primeros pesajes el resultado de a contra b. Por tanto, nuestro tercero pesaje es girar el grupo menor (es decir, pesar b contra c), y terminamos como en Sugerencia 2.
   2. Si los dos resultados son diferentes, entonces la moneda falsa es en el grupo mayor, y sabemos en cuál de A, B, C está, y si es pesado o ligero. El subgrupo falsa contiene tres monedas, y pesamos cualquier dos contra entre sí. Si son iguales, la moneda falsa es la tercera, y si no son iguales, la moneda falsa es pesada o ligera de acuerdo con si la moneda falsa es saber para ser pesados o ligeros.

Algoritmo para Muchas Monedas

Vamos a mostrar como organizar este método en una manera muy sencilla y sistemática, que es especialmente útil cuando se trata de un gran número de monedas (por ejemplo, 120 monedas y 5 pesajes).

1. Dividir los (3^n - 3) / 2 monedas en 3 grupos con (3^{n-1} - 1) / 2 en cada grupo.
2. Subdividir cada grupo en n-1 subgrupos de 3^{n-2}, 3^{n-3}, ... 3^1, 3^0 monedas.
3. Para el primer pesaje, coloque los dos primeros grupos en los dos platillos.
4. A partir de los subgrupos más grandes y trabajando hacia los más pequeños, gire cada subgrupo una vez y observar si el resultado del pesaje ha cambiado. Si no, seguir trabajando hacia abajo. Si ha cambiado, entonces uno de los tres subgrupos tiene la moneda falsa, y podemos determinar cuál, y si la moneda es pesada o ligera. Aplicar la solución del Problema de Monedas de Peso Conocido a este subgrupo. (Opcionalmente, puede quitar los subgrupos más grandes después de cada pesaje, si el resultado no cambió, porque en este caso sabemos que los subgrupos contienen sólo las monedas justas, y no afectan los resultados.)
5. Si estamos en el último subgrupo, todavía lo giramos, pero no es necesario aplicar el método de Problema de Monedas de Peso Conocido porque ya hemos aislado la moneda falsa a un grupo de 1.

Terminamos con un grupo de tamaño 3^{n-k}, donde 2 \le k \le n-1, y usamos el método par el Problema de Monedas de Peso Conocido sobre un grupo de tamaño 3^{n-k-1}. Entonces el número de pesajes es 1 + k + (n - k - 1) = n.

El algoritmo para el Problema de Monedas de Peso Conocido es hacer esta secuencia de pasos repetidamente:

1. Dividir las monedas en tres grupos iguales.
2. Elige cualquiera de los dos grupos y ponerlos en los platillos.
3. Si pesan lo mismo, poner esos grupos a un lado y pasar al tercer grupo. Si no hay equilibrio, uno de ellos contiene la moneda falsa, y podemos determinar cuál porque ya sabemos que si la moneda falsa es ligero o pesado. Coloque los otros dos grupos a un lado y trabaje con el grupo falso.

El Problema de 13 Monedas

Una variante del problema de 10 monedas es el problema de 13 monedas. Como antes, se le permitió tres pesajes, y no sabemos si la moneda falsa es ligero o pesado, pero ahora no es necesario determinar el peso de la moneda falsa. Este problema se puede trabajar por exactamente el mismo método. Sólo hay que poner una moneda al lado, y trabajar el problema de 12 monedas para las monedas restantes. La solución para 12 monedas vale, incluso si todas las monedas son justas, así que si la 13a moneda era la moneda falsa, vamos a detectar que las otras 12 son justas y correctamente determinar que la 13a es falsa (aunque no sabremos su peso). Si uno de las 12 es falso, lo detectará con su peso.

Menor que 12 Monedas

¿Podemos resolver tal problema con menos de doce monedas dadas? Podría ser más sencillo aislar una moneda falsa de (por ejemplo) 10 monedas que a partir del 12, pero nuestros métodos dependen de tener un conjunto adecuado de monedas justas, así que tener un menor número total de monedas no es necesariamente una ventaja. Experimentalmente se desprende que podemos resolver el problema para la mayoría de las monedas en un número menor que 12, pero no en todos casos. Por ejemplo, 11 monedas en tres pesajes pueden ser resueltos en casi la misma manera que el problema de 12 monedas, ya que en la solución de 12 monedas representa una moneda (en el grupo menor) que no se utiliza en los primeros dos pesajes. Podemos fingir que está ahí, y el uso de una moneda conocida por ser necesario para el pesaje tercero. Por otro lado, si sólo contamos con dos monedas, es imposible hacer ningún progreso, independientemente de cuántos pesajes nos permite, porque hay una moneda justa y una falsa, y no hay manera inherente a decir cuál es cuál.

Referencias

• Martin Gardner, Comunicación extraterrestre y otros pasatiempos matemáticos (Ediciones Cátedra, Madrid, 1986). "El Sistema Ternario". Da una solución usando notación ternaria (base-3).
• (en inglés) Puede ver la pregunta original de "C" aquí.
• El Problema de Monedas de Peso Conocido es otro artículo de Lo Mejor de MathNerds: La Moneda Falsa.
• (en ingles) Hay una amplia discusión del problema de 12 monedas en el sitio Cut The Knot!. Allá están soluciones por Brian D. Bundy, por Donald J. Newman, por W. McWorter, y por Jack Wert. Nuestro solución es por Jack Wert y es una versión revisada de su solución en Cut The Knot!.
• J. Dominguez-Montes, "Solución definitiva al problema de la moneda falsa", Qüestiio, Vol. 7, No. 2, June 1983. Se puede descargar aquí. Analiza el problema desde el punto de vista de teoría de la información.
• (en inglés) Mario Martelli y Gerald Gannon, "Weighing Coins: Divide and Conquer to Detect a Counterfeit", College Mathematics Journal, Vol. 28, No. 5 (Nov., 1997), pp. 365-367. Este artículo da métodos sencillos para resolver los problemas, tanto si el peso relativo de la moneda falsa es conocido y si no lo es.
• Wikipedia tiene un artículo sobre la Problema de las Doce Monedas.