 |
 |
|
|||||||||||||||||
| Pablo de la Mora y Alex George | |||||||||||||||||||
| Vamos a suponer que contamos con doce monedas, una
de ellas falsa, (más pesada o más ligera), y también vamos a suponer que contamos con una balanza. ¿Cómo se podría encontrar la moneda falsa usando la balanza sólo tres veces? ¿Podríamos a la vez saber si la moneda falsa es mas liviana o más pesada, o si no hay tal moneda falsa?
Este problema es antiguo, y se han encontrado ya muchas soluciones, generalmente utilizando el sistema de prueba y error. Aparentemente las soluciones son asimétricas. La descripción completa de las soluciones se complica por todas las diferentes posibilidades que hay que incluir.
Los puntos interesantes de este problema son: a) Las simetrías ocultas de las soluciones; b)El desarrollo de un método conciso para describir la solución y encontrar las diferentes soluciones; y c) Determinar el número máximo de monedas para las que bastan tres pesadas, y extender el problema a cuatro o más pesadas.
Este artículo presenta un estudio de la estructura y de las simetrías de este problema. Muestra algoritmos que llevan a soluciones de una forma natural, y hacen explícitas las simetrías del problema. Además analiza los puntos anteriores.
Descripción de la solución
Una descripción de la solución debe de incluir todas las diferentes posibilidades. Una forma concisa de hacer esto se muestra en la figura I (a esta solución particular se le llamará la “solución simétrica con signos alternos”).
En esta descripción, cada pesada se representa con una balanza (. .) y abajo de los extremos de la balanza están las monedas que se colocan en los platos respectivos. En medio están las monedas que se dejan fuera de la balanza, pero que no se han eliminado aún, entre las cuales también puede estar la moneda falsa. Abajo de esta balanza están tres balanzas más pequeñas que representan las siguientes pesadas, esto crea un diagrama de árbol, que se separa en tres posibilidades diferentes después de cada pesada. La balanza izquierda, media o derecha se escoge dependiendo de si en la pesada anterior la balanza se inclinó a la izquierda, no se inclinó o se inclinó a la derecha. El signo sobre la moneda representa que la moneda subió (-) o bajó (+) en la pesada anterior, lo cual, aunque no es esencial contiene la información relevante de las pesadas anteriores. Abajo de la tercera pesada esta el renglón de respuestas, indicando cuál fue la moneda falsa y si ésta es más pesada (+) o más liviana (-). El asterisco (*) representa a una moneda neutral (que pudo haber sido eliminada en una pesada anterior) y el signo ‘=’ representa al caso de que todas las monedas fueran iguales.
El número máximo de monedas
Para encontrar el número máximo de monedas que se pueden examinar en tres pesadas es necesario conocer previamente la máxima cantidad de datos que la balanza puede proveer en estas pesadas. Observando la solución (figura I), se ve que en cada pesada hay tres posibilidades: que se incline la balanza a la izquierda, a la derecha o se quede balanceada. A la siguiente pesada cada uno de estos casos tiene a su vez tres posibilidades, quedando 3 x 3 = 9 y en tres pesadas queda 9 x 3 = 27 = 33.
¿Cuántas monedas se pueden pesar con estas 27 posibilidades? Una de las probabilidades es que todas las monedas sean iguales, si restamos esta posibilidad quedan 33 - 1 = 26. Como la moneda falsa puede ser o más pesada o más liviana, entonces por cada moneda debemos tomar dos casos, por lo que el número se reduce a (33 - 1) / 2 = 13.
Otro requerimiento es que el número de monedas, en cada uno de los platos de la balanza, sea el mismo. ¿Cuántas monedas se pueden poner en la balanza en la primera pesada? Observando la solución (figura I), contamos 18 diferentes posibilidades de que una moneda que está sobre la balanza en la primera pesada sea mala, y como esta moneda puede ser más pesada o más liviana, encontramos que el número máximo de monedas sobre la balanza es 9(= 32) que es impar, por lo que hay que restar uno al número total (33 - 1) / 2 - 1 = 12. Ahora bien, si afuera del grupo de monedas por analizar, se tiene una moneda buena o neutra, ésta se puede usar para igualar el número de monedas en la balanza, y así se incrementa el número a 13.
Quedan 4 monedas afuera de la balanza después de la primera pesada (13 - 9). ¿Pueden estas monedas ser analizadas? Si, cuatro es el número máximo de monedas que se pueden analizar en dos pesadas cuando se tiene una moneda neutra (32 - 1) / 2 = 4, la moneda neutra se toma de entre las que se eliminaron en la primera pesada.
Esto se puede generalizar para un número r arbitrario de pesadas, y se encuentra que el número máximo de monedas n es n = (3r - 1) / 2 si se tiene una moneda neutra al principio y n = (3r - 1) / 2 - 1 si no. El número de monedas que se deja afuera en la primera pesada es (3r - 1) / 2, igual al número de monedas que se pone en cada plato, si no hay moneda neutra.
Si las condiciones del problema se cambian y se especifica que siempre hay una moneda mala y que además no se tiene que averiguar si ésta es más pesada o más ligera, entonces el número que se puede examinar se incrementa en uno. Esta es una extensión trivial del problema anterior ya que se aparta una moneda del montón, luego se examinan las monedas restantes, y si éstas resultan todas iguales, entonces la moneda falsa es la que se apartó.
Si se resuelve el problema de las trece monedas más la moneda neutra, entonces también se resuelve el problema de las doce monedas sin moneda neutra. Esto se logra de la siguiente manera en la figura I: en la primera pesada se quita la moneda neutra y otra moneda del otro plato de la balanza y en las siguientes pesadas también se quita esta otra moneda de la balanza (para igualar el número de monedas en los platos de la balanza, se pueden utilizar monedas que se descartaron en la primera pesada). Hay ciertas soluciones que no permiten esto, como se puede ver un ejemplo en la figura V.
Por lo tanto, sólo es necesario resolver el problema de las trece monedas más una moneda neutral.
Solución del problema
Si se tienen 9 monedas neutras o más, el problema se vuelve muy simple (figura II); en la primera pesada se colocan 9 monedas en un plato y 9 monedas neutras en el otro, si la balanza queda balanceada esas monedas se descartan y en la siguiente pesada se comparan tres monedas contra tres monedas neutrales. Si las monedas bajan (suben), entonces son más pesadas (livianas); en este caso, en la siguiente pesada, las monedas se dividen en tres grupos de tres monedas y, finalmente, en tres grupos de una moneda.
Llamaremos soluciones simétricas a las que la parte derecha del renglón respuesta corresponde a la reflexión ‘negativa’ de la parte izquierda, donde la moneda reflejada tiene el signo opuesto a la moneda no reflejada.
Cualquier solución simétrica se puede encontrar a partir de la solución anterior (figura II), transfiriendo primero una moneda de un lado de la balanza al otro, esta moneda se transfiere en las tres pesadas. En este proceso hay que añadir, o quitar, una moneda neutra, para mantener el número igual de monedas en los platos de la balanza, aunque el objetivo es eliminar monedas neutras de la primera pesada. Como resultado la moneda X+ cambia su signo a X- y viceversa, pero el diagrama sigue representando una solución del problema con muchas monedas neutras. La figura III ejemplifica este movimiento con la moneda F, este movimiento no cambia la posición de la moneda en el renglón de respuesta, solo cambia el signo.
Transfiriendo cuatro monedas a la derecha se eliminan 8 monedas neutrales de la primera pesada, dejando sólo la moneda neutral original. Si estas monedas se escogen mal, entonces se pueden requerir 6 monedas neutras en la segunda pesada, como lo ejemplifica la figura IV. Como las monedas que se eliminan en la primera pesada, se pueden usar como neutras en las siguientes pesadas, es claro que la figura IV no es la solución, ya que requiere demasiadas monedas neutras en la segunda pesada.
La solución de la figura I se puede encontrar cambiando en la figura II las monedas B D F H J L y luego renombrando las monedas.
Si sólo se tiene el renglón de respuestas, es posible reconstruir el resto del diagrama. Por ejemplo, en la figura I, para que la balanza escoja la sexta posición, es decir la moneda L, y que sea ésta más ligera, la balanza tuvo que inclinarse en la primera pesada a la izquierda, en la segunda no inclinarse y, finalmente hacerlo a la derecha, y como la moneda era más ligera (-) entonces estaba en el plato que subió, o sea primero estaba en la derecha, luego fuera y finalmente izquierda. Haciendo esto para todas las monedas se completa el diagrama.
Por lo tanto la solución está determinada unívocamente con solo el renglón de respuestas (signo y posición).
Para las respuestas simétricas la posición de las monedas no es importante, ya que cada moneda aparece en posiciones simétricas y las diferentes soluciones que tengan la misma configuración de signos, es solamente un reordenamiento o renombramiento de las monedas. Por lo tanto lo único relevante es el renglón de los signos. Las monedas de la mitad izquierda, que tienen signo negativo en el renglón de respuestas, son las que se transfirieron de plato en la construcción de la solución, partiendo del caso en que se tenían 9 monedas neutras.
Esto sugiere un refinamiento de la estrategia anterior para encontrar las soluciones; el renglón de soluciones se divide en secciones 1, 2 y 3 y éstas se subdividen en izquierda y derecha (ver parte inferior de la figura I). El número de monedas neutras impone condiciones sobre el renglón de signos: Los signos positivos de la sección 3I muestran las monedas que en la primera pesada estaban en el lado izquierdo de la balanza y los negativos en el lado derecho, por lo que el número de signos positivos y negativos no debe diferir más de uno en la sección 3I, si se tiene una moneda neutra, y cero si no se tiene. Para la segunda pesada la condición es más complicada, para esto la sección 3I se subdivide en 3Ia, 3Ib y 3Ic; en la sección 3Ic se cambian los signos a su opuesto (para propósitos de conteo solamente), luego se cuenta el número de signos positivos y negativos en 3Ia y 3Ic, y estos no deben diferir en más de 5 (el número de monedas neutras que se tienen para la segunda pesada, cuatro si se comienza sin moneda neutra).
Por lo tanto, cualquier orden de signos que cumpla con las condiciones anteriores, es la solución del problema. La parte derecha del renglón de signos es la reflexión negativa de la izquierda. La solución general incluye soluciones no simétricas. En este caso el renglón de soluciones no es necesariamente simétrica, y siguen habiendo condiciones para que sea solución, aunque no tan estrictas. Si una moneda está en el lado izquierdo de una sección, también debe estar en esa misma sección del lado derecho, aunque no necesariamente en posición equivalente, pero con signo contrario. En este caso, en el renglón de respuestas son importantes tanto el signo como la letra de la moneda. Las condiciones de la segunda pesada se deben revisar en cada lado, independientemente.
Una ilustración de esto se puede ver en la figura V, en donde en el lado izquierdo se utilizan 4 monedas neutras, y en el lado derecho sólo dos; es más, si la moneda G se cambia de un lado de la balanza al otro, entonces se necesitarán 6 monedas neutras en la segunda pesada del lado izquierdo y ninguna en el derecho.
Para el problema de 12 monedas se utilizan las mismas condiciones, pero en la primera pesada no hay monedas neutras, y en la segunda sólo hay 4. Para generar una solución a partir del problema anterior, se quita una moneda de la sección 3 (izquierda y derecha) del renglón de respuestas, dejando un espacio.
Para entender este problema relativo a 4 o más pesadas, el sistema es el mismo, excepto que el número de monedas neutras que hay para la segunda pesada, es diferente.
La solución de monedas apareadas
Esta solución particular no requiere de un diagrama, y es válida para cualquier número de pesadas.
Aquí el problema de r pesadas y (3r - 1) / 2 monedas, se reduce, después de una pesada, al problema de r - 1 pesadas y (3r-1 - 1) / 2 monedas.
En la primera pesada se forman tres montones de (3r-1 - 1) / 2 monedas, dejando una moneda fuera ((3r - 1) / 2 = 3 x (3r-1 - 1) / 2 + 1). Se pone un montón en cada uno de los platos de la balanza, también dejando uno fuera, la moneda que se quedó fuera de los montones se coloca en uno de los platos, y la neutral en otro.
Si la balanza permanece equilibrada entonces el problema se redujo a r - 1 pesadas y (3r-1 - 1) / 2 monedas.
Si la balanza no queda equilibrada, se forman monedas apareadas, tomando una moneda de cada lado de la balanza y se juntan formando una moneda doble o una moneda apareada. Una de las monedas que forman la moneda apareada, viene del plato que bajo, por lo que no puede ser más liviana. En la notación de la solución anterior se le ponía un signo 1 después de la letra de la moneda. La otra moneda del par no podía ser más pesada y llevaba el signo 2.
Las monedas apareadas se pueden representar de la siguiente forma:
A/B (= A-B+)
Las monedas apareadas pueden pesar más, menos, o igual que una moneda apareada neutral, lo que equivale en la moneda A/B, a que respectivamente B sea más pesada, A sea más liviana o ninguna de las dos es falsa, teniendo así una equivalencia entre las monedas sencillas y las apareadas.
Se formaron (3r-1 - 1) / 2 monedas apareadas con monedas no neutras y una que incluye a la moneda neutral, esta última moneda se pone aparte. Las monedas apareadas se trabajan como las sencillas, cuando una de ellas es más pesada o más liviana ya se sabe cual de las monedas sencillas que la forman es la falsa, y en caso de que todas las monedas apareadas sean iguales, entonces la falsa es la que se apartó (y también se sabe si es más liviana o más pesada, porque ya estuvo en la balanza). De esta forma también se reduce al problema de n - 1 pesadas y (3r-1 - 1) / 2 monedas pero apareadas, y los dos casos son equivalentes.
En las pesadas siguientes es necesario aparcar monedas apareadas, pero éstas se reducen a una sola moneda apareada:
(A/B)/(C/D) = A/D
eliminándose B y C (B se eliminó, ya que originalmente venía del lado de la balanza que bajó, y luego la moneda A/B estuvo en el plato que subió).
Como se ve, esta solución no necesita de ningún diagrama para localizar la moneda falsa, y la situación de una pesada es equivalente a la siguiente, pero con menos monedas.
Esta solución está ilustrada en la figura VI para el caso de tres pesadas. En este ejemplo, para la primera pesada, el caso de que la balanza se inclina a la izquierda se puede comparar con el caso en que la balanza no se inclina; en un caso la moneda F/B se comporta igual a J en el otro caso, la moneda apareada */M, en el primer caso, representa la situación en que en el segundo caso todas las monedas son iguales.
Conclusiones
En este artículo se analizó el problema de separar la moneda falsa de un montón de monedas, usando una balanza un número mínimo de veces. Primero se construye un diagrama para representar las soluciones, lo que facilita el análisis y permite encontrarlas más fácilmente. Con este diagrama es más fácil visualizar las simetrías de las soluciones, aunque hay soluciones asimétricas. Se estudia cuántos datos provee la balanza, cuanta información es necesaria para separar la moneda falsa, y como optimizar este proceso. Se muestran algoritmos para encontrar las diferentes soluciones al problema. La solución de signos alternos es posiblemente la solución de mayor simetría.
Por último se muestra la solución de monedas apareadas, la cual muestra otro tipo de simetría, y además no necesita utilizar un diagrama de soluciones para encontrar la moneda falsa, sino unas reglas sencillas. Esta solución es válida para cualquier número de pesadas.
|
|
 |
|
||||||||||||||||
|
Agradecimientos
La lectura detallada y las múltiples sugerencias hechas por Gerardo Ruíz Chavarría ayudaron mucho a hacer claro y entendible este artículo.
|
|||||||||||||||||||
| ____________________________________________________________ | |||||||||||||||||||
| Pablo de la Mora
Departamento de Física, Facultad de Ciencias,
Universidad Nacional Autónoma de México.Alex George
Wolfson College, Oxford, Inglaterra.
|
|||||||||||||||||||
| ___________________________________________ | |||||||||||||||||||
|
cómo citar este artículo → De la Mora, Pablo y George, Alex. 1991. Simetrías del problema de las doce monedas. Ciencias núm. 23, julio-septiembre, pp. 35-39. [En línea] |
|||||||||||||||||||
