Diferencia entre revisiones de «Problema de las doce monedas»
añado categoría |
|||
Línea 1: | Línea 1: | ||
En el |
En el "problema de las doce monedas" se propone identificar la moneda falsa, entre un grupo de doce monedas, empleando 3 pesadas de balanza. |
||
La moneda falsa tiene un peso distinto de las otras |
La moneda falsa tiene un peso distinto de las otras, y hay que averiguar si esta moneda pesa más o menos que las otras. |
||
⚫ | |||
El problema admite una generalización inmediata aumentando el número de monedas y de pesadas: ¿Cuál es el máximo de monedas para "n" pesadas? |
El problema admite una generalización inmediata aumentando el número de monedas y de pesadas: ¿Cuál es el máximo de monedas para "n" pesadas? |
||
⚫ | |||
⚫ | |||
⚫ | |||
== 1ª Solución == |
== 1ª Solución == |
||
La primera solución, de fácil generalización para más pesadas, se explica a continuación: |
|||
La 1ª pesada la realizamos así: |
|||
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''. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
En la 2ª pesada, rotamos los grupos de tres monedas: |
|||
⚫ | |||
* 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). |
|||
⚫ | |||
* Si la inclinación de la balanza cambia, esto identifica el grupo de tres que tiene la moneda falsa. |
|||
Este algoritmo es fácilmente generalizable a un número cualquiera de monedas. |
|||
* Si la inclinación de la balanza no cambia, la moneda falsa está entre las tres que no hemos rotado: 1, 5, 9. |
|||
Pesadas Monedas totales Grupos |
|||
1 3 1 |
|||
2 9 3 |
|||
3 27 9 |
|||
... ... ... |
|||
Y nos queda la 3ª pesada para identificar entre 3 monedas cual es la falsa: sólo tenemos que pesar dos de ellas, pues como ya tenemos información de anteriores pesadas podemos así identificarla. |
|||
Veamos ahora el procedimiento general, con la ayuda del método A: |
|||
== Generalización == |
|||
Tomamos el conjunto de doce monedas, los divido 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. |
|||
Veamos primero el método A: procedimiento cuando conocemos que la moneda pesa más (si pesa menos será análogo). |
|||
Ponemos dos grupos de 4 monedas en la balanza y dejamos el tercero fuera sobre la mesa. |
|||
Observad la situación de la balanza. Ésta es la pesada número uno. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
Rotad 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. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
De la pesada anterior quedan tres monedas que contiene la falsa. Se pesa la moneda A contra la moneda B, e identificamos fácilmente cual es la falsa. |
|||
Observad la situación de la balanza. Ésta es la pesada número dos. |
|||
La clave de la generalización reside en el método A, y consiste en identificar |
|||
* 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. |
|||
el grupo de 3^n monedas con n pesadas: Formamos 3 grups, pesamos 2 de ellos e |
|||
identificamos el grupo problemático. Y repetimos el proceso hasta obtener una |
|||
moneda. |
|||
Veamos ahora el caso general: |
|||
* 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. |
|||
El problema admite una generalización a 4 pesadas añadiendo una nueva fila de 9 monedes en cada uno de los 3 grupos: 13 monedas en cada grupo... Rotaremos los grupos de 9 monedas y razonamos igual que antes: si la posición cambia identificamos el grupo de 9 con la moneda falsa y le aplicamos el método A. Si la posición no cambia, quitamos los grupos de 9 y nuestras condiciones son ahora las del problema de 12 monedas con 3 pesadas. |
|||
Con 5 pesadas añadiremos otra fila más de 27 monedas en cada uno de los 3 grupos: 40 monedas en cada grupo. Y procedemos análogamente como en el caso anterior. |
Con 5 pesadas añadiremos otra fila más de 27 monedas en cada uno de los 3 grupos: 40 monedas en cada grupo. Y procedemos análogamente como en el caso anterior. |
||
Como estamos agregando potencias de 3 en cada paso, obtendremos la suma de una progresión geométrica: |
|||
3 monedas en 2 pesadas |
3 monedas en 2 pesadas |
||
Línea 84: | Línea 77: | ||
que, curiosamente, coincide con la mitad del máximo de la balanza, es decir como cada brazo de balanza. |
que, curiosamente, coincide con la mitad del máximo de la balanza, es decir como cada brazo de balanza. |
||
Finalmente, sumamos el máximo obtenido en la mesa y en la balanza, y obtenemos otra progresión geómetrica: |
Finalmente, sumamos el máximo obtenido en la mesa y en la balanza, y obtenemos otra suma de progresión geómetrica: |
||
1+3+9+...+3^(n-1) + 3^n-1 = 3+9+...+ 3^(n-1) + 3^n |
1+3+9+...+3^(n-1) + 3^n-1 = 3+9+...+ 3^(n-1) + 3^n |
||
Línea 157: | Línea 150: | ||
X(n) = (3^n-3)/2. Como queríamos demostrar |
X(n) = (3^n-3)/2. Como queríamos demostrar |
||
Además, por ser X(n) progresión geométrica se cumple que cada brazo y la mesa tienen las mismas monedas, pues: |
Además, por ser X(n) suma de progresión geométrica se cumple que cada brazo y la mesa tienen las mismas monedas, pues: |
||
mesa = balanza / 2 |
mesa = balanza / 2 |
||
Línea 199: | Línea 192: | ||
Si se inclina como la 1ª pesada, está en el grupo (1,2,6). |
Si se inclina como la 1ª pesada, está en el grupo (1,2,6). |
||
Si no, estará en el grupo (3,4,5). |
Si no, estará en el grupo (3,4,5). |
||
⚫ | |||
[[Categoría:Matemática recreativa]] |
|||
[[ca:Problema de les 12 monedes]] |
|||
⚫ | |||
[[en:Counterfeit coin problem]] |
Revisión del 06:59 26 feb 2010
En el "problema de las doce monedas" se propone identificar la moneda falsa, entre un grupo de doce monedas, empleando 3 pesadas de balanza.
La moneda falsa tiene un peso distinto de las otras, y hay que averiguar si esta moneda pesa más o menos que las otras.
En su versión de 12 monedas habría aparecido en 1945, sin que se sepa su procedencia.
El problema admite una generalización inmediata aumentando el número de monedas y de pesadas: ¿Cuál es el máximo de monedas para "n" pesadas?
Ofrecemos aquí dos soluciones del problema.
1ª Solución
La primera solución, de fácil generalización para más pesadas, se explica a continuación:
La 1ª pesada la realizamos así:
Brazo derecho Brazo izquierdo Mesa 1 5 9 2,3,4 6,7,8 10,11,12
En la 2ª pesada, rotamos los grupos de tres monedas:
Brazo derecho Brazo izquierdo Mesa 1 5 9 10,11,12 2,3,4 6,7,8
- Si la inclinación de la balanza cambia, esto identifica el grupo de tres que tiene la moneda falsa.
- Si la inclinación de la balanza no cambia, la moneda falsa está entre las tres que no hemos rotado: 1, 5, 9.
Y nos queda la 3ª pesada para identificar entre 3 monedas cual es la falsa: sólo tenemos que pesar dos de ellas, pues como ya tenemos información de anteriores pesadas podemos así identificarla.
Generalización
Veamos primero el método A: procedimiento cuando conocemos que la moneda pesa más (si pesa menos será análogo).
Veamos un ejemplo con 9 monedas: Formamos 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, e identificamos fácilmente cual es la falsa.
La clave de la generalización reside en el método A, y consiste en identificar el grupo de 3^n monedas con n pesadas: Formamos 3 grups, pesamos 2 de ellos e identificamos el grupo problemático. Y repetimos el proceso hasta obtener una moneda.
Veamos ahora el caso general:
El problema admite una generalización a 4 pesadas añadiendo una nueva fila de 9 monedes en cada uno de los 3 grupos: 13 monedas en cada grupo... Rotaremos los grupos de 9 monedas y razonamos igual que antes: si la posición cambia identificamos el grupo de 9 con la moneda falsa y le aplicamos el método A. Si la posición no cambia, quitamos los grupos de 9 y nuestras condiciones son ahora las del problema de 12 monedas con 3 pesadas.
Con 5 pesadas añadiremos otra fila más de 27 monedas en cada uno de los 3 grupos: 40 monedas en cada grupo. Y procedemos análogamente como en el caso anterior.
Como estamos agregando potencias de 3 en cada paso, obtendremos la suma de una progresión geométrica:
3 monedas en 2 pesadas 12 monedas en 3 pesadas: 3 + 3^2 = 12 39 monedas en 4 pesadas: 12 + 3^3 = 39 120 monedas en 5 pesadas: 39 + 3^4 = 120 363 monedas en 6 pesadas: 120 + 3^5 = 363 120 monedas en 7 pesadas: 363 + 3^6 = 1092 (3^n-3)/2 monedas, con n pesadas.
¿Cuál es el máximo de monedas para "n" pesadas?
Ofrecemos ahora una demostración intuitiva, que sólo utiliza el método A descrito al principio:
Para (n+1) pesadas analicemos el máximo de monedas, entre balanza y mesa:
Un máximo en la balanza es 3^n monedas, pues después de la 1ª inclinación de balanza nos quedan n pesadas y el método A asegura que 3^n es el máximo de monedas cuando conocemos su "inclinación". Pero como tiene que ser par (dos platillos), en la balanza habrá hasta 3^n-1 como máximo.
Veamos el máximo de monedas en la mesa: si la moneda falsa está en la mesa entonces hay equilibrio en la 1ª pesada y dispondremos de monedas "buenas": Escogemos 3^(n-1) monedas de la mesa y las pesamos con otras tantas "buenas", si está ahí la moneda falsa el método A asegura encontrarla con (n-1) pesadas que nos quedan; si hay equilibrio repetimos el proceso con 3^(n-2) monedas, con (n-2) pesadas que nos quedan;...; si hay equilibrio repetimos el proceso con 3^2 monedas con otras 9 "buenas"; si hay equilibrio repetimos el proceso con 3^1 monedas con otras 3 "buenas"; finalmente, si hay equilibrio pesamos la última moneda con 1 "buena" para saber si pesa más o menos, con la última pesada que nos queda. Sumando todas las monedas de la mesa que hemos pesado, tenemos una progresión geómetrica de razón 3 y primer término A(1)=1:
S (n) = 1+3+9+...+ 3^(n-1) = A(1)*(r^n-1)/(r-1) = (3^n-1)/2
que, curiosamente, coincide con la mitad del máximo de la balanza, es decir como cada brazo de balanza.
Finalmente, sumamos el máximo obtenido en la mesa y en la balanza, y obtenemos otra suma de progresión geómetrica:
1+3+9+...+3^(n-1) + 3^n-1 = 3+9+...+ 3^(n-1) + 3^n
que coincide con la obtenida en el procedimiento general. Luego ese es el máximo para (n+1) pesadas.
Para una demostración más precisa del máximo necesitamos otro planteamiento, la 2ª solución.
2ª Solución
Primero veamos un método de separación en grupos, parecido al método A descrito antes, que consigue aislar la moneda falsa en grupos de 3, 9, 27,.., 3^n para monedas "orientadas" (procedentes de la 1ª inclinación de balanza):
Para 3 monedas "orientadas", la solución es pesar 2 de ellas.
Si tenemos 9 monedas "orientadas", pondremos en cada brazo dos "monedas pesadas" (procedentes del brazo inclinado en la 1ª pesada) que denotamos (2+), y una "moneda ligera" (procedente del brazo opuesto) que denotamos (1-):
brazo izquierdo brazo derecho mesa (2+), (1-) (2+), (1-) monedas restantes Según se incline la balanza identificamos un grupo de 3 donde está la moneda falsa.
Análogamente, si tenemos 27 monedas "orientadas" identificamos un grupo de 9 monedas: brazo izquierdo brazo derecho mesa (6+), (3-) (6+), (3-) monedas restantes
Y en general, formamos 3 grupos de 3^(n+1) monedas:
brazo izquierdo brazo derecho mesa (2*3^n+), (3^n-) (2*3^n+), (3^n-) monedas restantes
En general, para 3^n monedas "orientadas" necesitamos n pesadas: si 3 es el máximo para 1 pesada, no podemos exceder 3 grupos de 3 monedas en 2 pesadas; ni 3 grupos de 9 monedas en 3 pesadas...etc; por tanto:
El máximo de monedas "orientadas" con n pesadas es 3^n.
Veamos ahora el procedimiento general:
Ahora sólo queda ver cómo configurar la primera pesada.
Sea la sucesión X(n)= máximo de monedas para n pesadas.
Calculemos X(n+1): máximo de monedas para (n+1) pesadas:
Podremos poner en los dos brazos hasta 3^n monedas, que es el máximo de monedas "orientadas" con n pesadas. Y como la balanza exige un número par, restamos 1:
Balanza = 3^n - 1
Y en la mesa pondremos X(n)+1: sumamos 1 por no tener la exigencia de pesar un número par, pues ahora tenemos monedas extra procedentes del equilibrio de la balanza:
Mesa = X(n) + 1
Calculamos el total entre los brazos y la mesa:
Total = Balanza + Mesa X(n+1) = 3^n-1 + X(n)+1 = 3^n + X(n)
Por tanto, X(n) tiene estructura de suma de una progresión geométrica de razón r= 3.
El primer término de la sucesión X(n) es:
X(2)= balanza + mesa = 2+1 = 3
pues en la mesa es evidente que sólo podemos poner 1 moneda, y en la balanza ya hemos argumentado que ha de ser igual a 3^1-1=2.
X(3) = 3^2 + X(2) = 12; X(4) = 3^3 + X(3) = 39; X(5) = 3^4 + X(4) = 120;........
Así pues, X(n+1) = 3+9+27+...+3^n = 3*(3^n-1)/2 X(n) = (3^n-3)/2. Como queríamos demostrar
Además, por ser X(n) suma de progresión geométrica se cumple que cada brazo y la mesa tienen las mismas monedas, pues:
mesa = balanza / 2 X(n)+1 = (3^n-1)/2
Veamos un esquema de los primeros términos, así como la configuración de la primera pesada para cada caso.
PRIMERA PESADA brazo izquierdo brazo derecho mesa 2 pesadas: 1 moneda 1 moneda 1 moneda 3 pesadas: 4 monedas 4 monedas 4 monedas = X(2) + 1 4 pesadas: 13 monedas 13 monedas 13 monedas = X(3) + 1 5 pesadas: 40 monedas 40 monedas 40 monedas = X(4) + 1 6 pesadas: 121 monedas 121 monedas 121 monedas = X(5) + 1 7 pesadas: 364 monedas 364 monedas 364 monedas = X(6) + 1
Veamos el ejemplo de 12 monedas:
Brazo derecho Brazo izquierdo Mesa 1,2,3,4 5,6,7,8 9,10,11,12
a) Si se equilibra, atacamos las 4 bolas restantes formando un grupo de 3 monedas, pues ahora sí podemos pesar un número impar en los dos brazos, al tener monedas buenas:
Brazo derecho Brazo izquierdo Mesa 9,10 11,1 12
b) Y si se inclina, tenemos 8=3^2-1 monedas "orientadas" y aplicamos el método de separación descrito:
Brazo derecho Brazo izquierdo Mesa 1 2 5 3 4 6 7,8
Si se equilibra, está en el grupo (7,8), evidentemente. Si se inclina como la 1ª pesada, está en el grupo (1,2,6). Si no, estará en el grupo (3,4,5).