Problema de las doce monedas

De Wikipedia, la enciclopedia libre

En el problema de las doce monedas se propone encontrar una moneda falsa, entre un grupo de doce monedas, empleando una balanza de dos platillos.

La moneda falsa tiene un peso distinto de las otras. Hay que determinar, utilizando sólo tres pesadas, cuál es y si esta moneda pesa más o menos que cada una de las once restantes, que son exactamente iguales.

El problema admite una generalización inmediata aumentando el número de monedas y de pesadas: ¿Cuál es el número máximo de monedas (con una moneda falsa de distinto peso) que se pueden discernir con un número determinado de pesadas?

En su versión de 12 monedas habría aparecido en 1945, sin que se sepa su procedencia.

[editar] Solución

Existen varios procedimentos para solucionar el problema. Uno de ellos, simple y de fácil generalización para más monedas, se explica a continuación.

Antes de nada se necesita conocer cuál es el número mínimo de pesadas necesarias para determinar la moneda falsa cuando se conoce si ésta pesa más o menos que el resto de monedas. Este es lo que llamaremos método A.

Sea un ejemplo con 9 monedas. Se realizan tres grupos de tres monedas cada uno y se pesa el grupo 1 frente al grupo 2:

• Si existe equilibrio la moneda falsa está en el grupo 3.
• Si no existe equilibrio la inclinación de la balanza indica cuál de los grupos es el que tiene la moneda falsa (pues conocemos si pesa más o menos).

De la pesada anterior quedan tres monedas que contiene la falsa. Se pesa la moneda A contra la moneda B:

• Si existe equilibrio la moneda falsa es la moneda C.
• Si no existe equilibrio la inclinación de la balanza indica cuál de las monedas es la falsa (recuérdese que se conoce si pesa más o menos que las demás).

Este algoritmo es fácilmente generalizable a un número cualquiera de monedas.

 Pesadas             Monedas totales         Grupos
       1              3                       1  
       2              9                       3
       3             27                       9
     ...            ...                     ...

Veamos ahora como podemos llegar a un conjunto de monedas al que se le pueda aplicar el método A. Tomamos el conjunto de doce monedas, los dividos en tres grupos de 4 monedas cada uno, y dividimos cada uno de los grupos de 4 monedas en una moneda y un grupo de 3 monedas.

Ponemos dos grupos de 4 monedas en la balanza y dejamos el tercero fuera sobre la mesa. Observar la situación de la balanza. Ésta es la pesada número uno.

  Brazo derecho          Brazo izquierdo        Mesa
       1                       5                  9
     2,3,4                   6,7,8             10,11,12

Rotar los grupos de tres moviendo el del brazo de la derecha a la mesa, el de la mesa al brazo de la izquierda y el del brazo de la izquierda al brazo de la derecha.

  Brazo derecho          Brazo izquierdo        Mesa
       1                       5                  9
    10,11,12                 2,3,4              6,7,8              

Observar la situación de la balanza. Ésta es la pesada número dos.

• Si la posición cambia esto identifica el grupo de tres que tiene la moneda falsa y nos dice si es más pesada o no. Utilizamos el método A para determinar en una pesada cuál es la moneda falsa.

• Si la posición no cambia es una moneda del grupo de una, nos quedamos con los grupos de una moneda y las rotamos en sus posiciones. Esto nos da la moneda falsa y si pesa más o menos.

Este problema admite una generalización en la que tenemos que 3ⁿ = X siendo X el número de monedas entre las cuales hay una falsa. Con n pesadas podemos descubrir cuál es la falsa y si ésta pesa más o menos que el resto.

Con el algoritmo anterior el problema se puede resolver fácilmente con un número de monedas mayor. Por ejemplo una moneda falsa entre 1.092 monedas con 7 pesadas.