Un rompecabezas de equilibrio o un rompecabezas de pesaje es un rompecabezas de lógica sobre el equilibrio de elementos, a menudo monedas, para determinar cuál tiene un valor diferente, mediante el uso de balanzas un número limitado de veces. Estos se diferencian de los rompecabezas que asignan pesos a los elementos, en que solo la masa relativa de estos elementos es relevante.
Conocido | Objetivo | Monedas máximas para n pesajes | Número de pesajes para monedas c |
---|---|---|---|
Si la moneda objetivo es más liviana o más pesada que otras | Identificar moneda | ||
La moneda objetivo es diferente a las demás | Identificar moneda | [1] | |
La moneda objetivo es diferente a las demás, o todas las monedas son iguales | Identificar si existe una moneda única y si es más liviana o más pesada |
Por ejemplo, al detectar una moneda diferente en tres pesajes (n = 3), el número máximo de monedas que se pueden analizar es 3 3 - 1/2= 13. Tenga en cuenta que con 3 pesas y 13 monedas, no siempre es posible determinar la identidad de la última moneda (si es más pesada o más liviana que el resto), sino simplemente que la moneda es diferente. En general, con n pesa, puede determinar la identidad de una moneda si tiene 3 n - 1/2- 1 o menos monedas. En el caso de n = 3, realmente puede descubrir la identidad de la moneda diferente de 12 monedas.
Problema de nueve monedas
Un ejemplo bien conocido tiene hasta nueve artículos, digamos monedas (o bolas), que son idénticos en peso excepto uno, que es más liviano que los demás: una falsificación (un bicho raro). La diferencia es perceptible solo al pesarlas en una balanza, pero solo las monedas mismas se pueden pesar. ¿Cómo se puede aislar la moneda falsa con solo dos pesajes?
Solución
Para encontrar una solución, primero consideramos el número máximo de artículos entre los que se puede encontrar el más liviano en un solo pesaje. El número máximo posible es tres. Para encontrar la más ligera, podemos comparar dos monedas cualesquiera, dejando la tercera fuera. Si las dos monedas pesan lo mismo, entonces la moneda más liviana debe ser una de las que no están en la balanza. En caso contrario, es el indicado como más ligero por la balanza.
Ahora, imagina las nueve monedas en tres pilas de tres monedas cada una. En un movimiento podemos encontrar cuál de las tres pilas es más liviana (es decir, la que contiene la moneda más liviana). Entonces solo se necesita un movimiento más para identificar la moneda ligera desde dentro de esa pila más ligera. Entonces, en dos pesajes, podemos encontrar una sola moneda ligera de un conjunto de 3 × 3 = 9 .
Por extensión, solo se necesitarían tres pesajes para encontrar la moneda ligera impar entre 27 monedas, y cuatro pesajes para encontrarla a partir de 81 monedas.
Problema de las doce monedas
Una versión más compleja tiene doce monedas, once o doce de las cuales son idénticas. Si uno es diferente, no sabemos si es más pesado o más ligero que los demás. Esta vez, la balanza se puede utilizar tres veces para determinar si hay una moneda única y, si la hay, para aislarla y determinar su peso en relación con las demás. (Este rompecabezas y su solución aparecieron por primera vez en un artículo en 1945. [2] ) El problema tiene una variante más simple con tres monedas en dos pesos, y una variante más compleja con 39 monedas en cuatro pesos.
Solución
Este problema tiene más de una solución. Uno es fácilmente escalable a un número mayor de monedas mediante el uso de la numeración de base tres: etiquetar cada moneda con un número diferente de tres dígitos en la base tres y colocar en el n -ésimo pesa todas las monedas que están etiquetadas con el n -ésimo dígito idéntico a la etiqueta de la placa (con tres placas, una a cada lado de la escala y otra fuera de la escala). Otros procedimientos paso a paso son similares a los siguientes. Es menos sencillo para este problema, y el segundo y tercer pesaje dependen de lo que haya sucedido anteriormente, aunque no es necesario que sea el caso (ver más abajo).
- Se ponen cuatro monedas a cada lado. Hay dos posibilidades:
- 1. Un lado es más pesado que el otro. Si este es el caso, retire tres monedas del lado más pesado, mueva tres monedas del lado más liviano al lado más pesado y coloque tres monedas que no fueron pesadas la primera vez en el lado más liviano. (Recuerde qué monedas son cuáles). Hay tres posibilidades:
- 1.a) El mismo lado que pesaba la primera vez lo es aún más. Esto significa que la moneda que se quedó allí es más pesada o que la moneda que se quedó en el lado más liviano es más liviana. Equilibrar una de estas con una de las otras diez monedas revela cuál de ellas es verdadera, resolviendo así el rompecabezas.
- 1.b) El lado que pesaba más la primera vez es más ligero la segunda vez. Esto significa que una de las tres monedas que pasó del lado más liviano al lado más pesado es la moneda liviana. Para el tercer intento, pese dos de estas monedas entre sí: si una es más ligera, es la única moneda; si se equilibran, la tercera moneda es la ligera.
- 1.c) Ambos lados están parejos. Esto significa que una de las tres monedas que se quitó del lado más pesado es la moneda pesada. Para el tercer intento, pese dos de estas monedas entre sí: si una es más pesada, es la única moneda; si se equilibran, la tercera moneda es la pesada.
- 2. Ambos lados están parejos. Si este es el caso, las ocho monedas son idénticas y se pueden reservar. Tome las cuatro monedas restantes y coloque tres a un lado de la balanza. Coloque 3 de las 8 monedas idénticas en el otro lado. Hay tres posibilidades:
- 2.a) Las tres monedas restantes son más ligeras. En este caso, ahora sabe que una de esas tres monedas es la única y que es más liviana. Toma dos de esas tres monedas y pésalas entre sí. Si el saldo se inclina, la moneda más ligera es la que sale impar. Si las dos monedas se equilibran, la tercera moneda que no está en la balanza es la que sale impar y es más ligera.
- 2.b) Las tres monedas restantes son más pesadas. En este caso, ahora sabe que una de esas tres monedas es la única y que es más pesada. Toma dos de esas tres monedas y pésalas entre sí. Si el saldo se inclina, la moneda más pesada es la que sale impar. Si las dos monedas se equilibran, la tercera moneda que no está en la balanza es la que sale impar y es más pesada.
- 2.c) El saldo de las tres monedas restantes. En este caso, solo necesita pesar la moneda restante con cualquiera de las otras 11 monedas y esto le indica si es más pesada, más liviana o lo mismo.
Variaciones
Dada una población de 13 monedas en la que se sabe que 1 de las 13 es diferente (masa) del resto, es sencillo determinar qué moneda es con una balanza y 3 pruebas de la siguiente manera:
- 1) Subdividir las monedas en 2 grupos de 4 monedas y un tercer grupo con las 5 monedas restantes.
- 2) Prueba 1, prueba los 2 grupos de 4 monedas entre sí:
- una. Si las monedas se equilibran, la moneda impar está en la población de 5 y proceda a la prueba 2a.
- B. La moneda impar está entre la población de 8 monedas, proceda de la misma manera que en el problema de las 12 monedas.
- 3) Prueba 2a, prueba 3 de las monedas del grupo de 5 monedas contra 3 monedas cualesquiera de la población de 8 monedas:
- una. Si las 3 monedas se equilibran, entonces la moneda impar se encuentra entre la población restante de 2 monedas. Pruebe una de las 2 monedas contra cualquier otra moneda; si se equilibran, la moneda impar es la última moneda no probada, si no se equilibran, la moneda impar es la moneda de prueba actual.
- B. Si las 3 monedas no se equilibran, entonces la moneda impar es de esta población de 3 monedas. Preste atención a la dirección del balanceo (hacia arriba significa que la moneda impar es liviana, hacia abajo significa que es pesada). Retire una de las 3 monedas, mueva otra al otro lado de la balanza (retire todas las demás monedas de la balanza). Si el saldo se iguala, la moneda impar es la moneda que se retiró. Si el saldo cambia de dirección, la moneda impar es la que se movió hacia el otro lado, de lo contrario, la moneda impar es la moneda que permaneció en su lugar.
Con una moneda de referencia
Si hay una moneda auténtica como referencia, las monedas sospechosas pueden ser trece. Numere las monedas del 1 al 13 y la moneda auténtica número 0 y realice estos pesajes en cualquier orden:
- 0, 1, 4, 5, 6 contra 7, 10, 11, 12, 13
- 0, 2, 4, 10, 11 contra 5, 8, 9, 12, 13
- 0, 3, 8, 10, 12 contra 6, 7, 9, 11, 13
Si la balanza solo está fuera de balance una vez, entonces debe ser una de las monedas 1, 2, 3, que solo aparecen en un pesaje. Si nunca hay saldo, entonces debe ser una de las monedas 10-13 que aparecen en todos los pesajes. Siempre es posible elegir la moneda falsa correspondiente a cada uno de los 27 resultados (13 monedas, una demasiado pesada o demasiado liviana son 26 posibilidades), excepto cuando todos los pesos están equilibrados, en cuyo caso no hay moneda falsa (o su peso es correcto). Si las monedas 0 y 13 se eliminan de estos pesos, dan una solución genérica al problema de las 12 monedas.
Si dos monedas son falsificadas, este procedimiento, en general, no recoge ninguna de estas, sino alguna moneda auténtica. Por ejemplo, si las monedas 1 y 2 son falsas, la moneda 4 o la 5 se eligieron incorrectamente.
Sin moneda de referencia
En una variación relajada de este rompecabezas, uno solo necesita encontrar la moneda falsa sin ser necesariamente capaz de decir su peso en relación con las demás. En este caso, claramente cualquier solución que pesó previamente cada moneda en algún momento se puede adaptar para manejar una moneda extra. Esta moneda nunca se coloca en la balanza, pero si todos los pesos están equilibrados, se elige como moneda falsa. No es posible hacerlo mejor, ya que a cualquier moneda que se ponga en la balanza en algún momento y se la recoja como moneda falsa siempre se le puede asignar un peso en relación con las demás.
Un método que pesa los mismos juegos de monedas independientemente de los resultados le permite a uno
- (entre 12 monedas AL) concluya si todas pesan lo mismo, o encuentre la moneda impar y diga si es más liviana o más pesada, o
- (entre 13 monedas AM) encuentre la moneda impar y, para 12 de ellas, diga si es más liviana o más pesada.
Los tres posibles resultados de cada pesaje se pueden indicar con "\" para que el lado izquierdo sea más ligero, "/" para el lado derecho sea más ligero y "-" para ambos lados que tengan el mismo peso. Los símbolos de los pesajes se enumeran en secuencia. Por ejemplo, "// -" significa que el lado derecho es más ligero en el primer y segundo pesaje, y ambos lados pesan lo mismo en el tercer pesaje. Tres ponderaciones dan los siguientes 3 3 = 27 resultados. A excepción de "---", los conjuntos se dividen de modo que cada conjunto de la derecha tenga una "/", mientras que el conjunto de la izquierda tiene una "\", y viceversa:
/// \\\\ // / \\/ \ / \ / \// \ \\ /\ / - / \ -- \ / - / \/ - \ \ - /\\ - // -- \\ - //\ - \ / - // - \ -- / - - \ -- / - \---
Como cada pesaje da un resultado significativo solo cuando el número de monedas del lado izquierdo es igual al número del lado derecho, ignoramos la primera fila, de modo que cada columna tiene el mismo número de símbolos "\" y "/" (cuatro de cada uno). Las filas están etiquetadas, el orden de las monedas es irrelevante:
\ // Un ligero / \\ Un pesado/ \ / B ligero \ / \ B pesado// \ C ligero \\ / C pesado\ / - D ligero / \ - D pesado- \ / E ligero - / \ E pesado/ - \ F ligero \ - / F pesado\\ - G ligero // - G pesado- \\ H ligero - // H pesado\ - \ I ligero / - / I pesado/ - J ligero \ - J pesado- / - K ligero - \ - K pesado- / L ligero - \ L pesado--- M más ligero o más pesado (caja de 13 monedas), o todas las monedas pesan lo mismo (caja de 12 monedas)
Utilizando el patrón de resultados anterior, se puede determinar la composición de monedas para cada pesaje; por ejemplo, el conjunto "\ / - D light" implica que la moneda D debe estar en el lado izquierdo en el primer pesaje (para hacer que ese lado sea más claro), en el lado derecho en el segundo y sin usar en el tercero:
1er pesaje: lado izquierdo: ADGI, lado derecho: BCFJ2do pesaje: lado izquierdo: BEGH, lado derecho: ACDK3er pesaje: lado izquierdo: CFHI, lado derecho: ABEL
Luego, los resultados se leen de la mesa. Por ejemplo, si el lado derecho es más liviano en los dos primeros pesajes y ambos lados pesan lo mismo en el tercero, el código correspondiente "// - G pesado" implica que la moneda G es la impar y es más pesada que las demás. . [3]
Generalizaciones
La generalización de este problema se describe en Chudnov. [4]
Dejar ser el -espacio euclidiano dimensional ,ser el producto interno de los vectores y de Para vectores y subconjuntos las operaciones y se definen, respectivamente, como ; , , Por denotaremos el discreto [−1; 1] -cubo en; es decir, el conjunto de todas las secuencias de longitud sobre el alfabeto El conjunto es la bola discreta de radio (en la métrica de Hamming ) con centro en el punto Pesos relativos de los objetos están dados por un vector que define las configuraciones de pesos de los objetos: el El objeto tiene un peso estándar si el peso del El objeto es mayor (menor) por un valor constante (desconocido) si (respectivamente, ). El vector caracteriza los tipos de objetos: el tipo estándar, el tipo no estándar (es decir, configuraciones de tipos) y no contiene información sobre pesos relativos de objetos no estándar.
Un peso (un cheque) viene dado por un vector el resultado de sopesar una situación es El peso dado por un vector tiene la siguiente interpretación: para un cheque dado, el El objeto participa en el pesaje si ; se coloca en el plato de equilibrio izquierdo si y se coloca en la sartén derecha si Por cada pesaje , ambas bandejas deben contener el mismo número de objetos: si en alguna bandeja el número de objetos es menor de lo que debería ser, entonces recibe algunos objetos de referencia. El resultado de un pesaje describe los siguientes casos: el saldo si , el plato izquierdo pesa más que el derecho si , y el plato derecho supera al izquierdo si La incompletitud de la información inicial sobre la distribución de pesos de un grupo de objetos se caracteriza por el conjunto de distribuciones admisibles de pesos de objetos. que también se llama el conjunto de situaciones admisibles, los elementos de se denominan situaciones admisibles.
Cada pesaje induce la partición del conjunto por el avión ( hiperplano ) en tres partes , y define la partición correspondiente del conjunto dónde
Definición 1 . Un algoritmo de pesaje (WA) de longitud es una secuencia dónde es la función que determina el cheque en cada el paso, del algoritmo a partir de los resultados de pesajes en los pasos anteriores ( es una comprobación inicial determinada).
Dejar ser el conjunto de todos -síndromes y ser el conjunto de situaciones con un mismo síndrome ; es decir,;
Definición 2 . A WA se dice que: a) identifica las situaciones en un conjunto si la condición está satisfecho por todos b) identificar los tipos de objetos en un conjunto si la condición está satisfecho por todos
Se demuestra en [4] que para los llamados conjuntos adecuados un algoritmo de identificación los tipos identifica también las situaciones en
Como ejemplo, los algoritmos dinámicos perfectos (dos cascadas) con parámetros se construyen en [4] que corresponden a los parámetros del código ternario perfecto Golay ( código Virtakallio-Golay). Al mismo tiempo, se establece que no existe un WA estático (es decir, un código de ponderación) con los mismos parámetros.
Cada uno de estos algoritmos que utiliza 5 pesajes encuentra entre 11 monedas hasta dos monedas falsificadas que podrían ser más pesadas o más ligeras que las monedas reales por el mismo valor. En este caso, el dominio de incertidumbre (el conjunto de situaciones admisibles) contienesituaciones, es decir, el WA construido se encuentra en el Hamming con destino a y en este sentido es perfecto.
Hasta la fecha no se sabe si existen otros WA perfectos que identifican las situaciones en para algunos valores de . Además, no se sabe si para algunos existen soluciones para la ecuación (correspondiente a la cota de Hamming para los códigos ternarios) que es, obviamente, necesaria para la existencia de un WA perfecto. Solo se sabe que por no hay WA perfecta, y para esta ecuación tiene la única solución no trivial que determina los parámetros del WA perfecto construido.
Rompecabezas de pesajes paralelos original
Konstantin Knop inventó este rompecabezas [ cita requerida ] . Hay N monedas indistinguibles, una de las cuales es falsa (no se sabe si es más pesada o más liviana que las monedas genuinas, que pesan todas lo mismo). Hay dos balanzas que se pueden utilizar en paralelo. Cada pesaje dura un minuto. ¿Cuál es la mayor cantidad de monedas N para las que es posible encontrar la moneda falsa en cinco minutos? [5]
En literatura
- Niobe, el protagonista de Piers Anthony 's novela Con una enredada madeja , debe resolver la variación en doce monedas de este rompecabezas para encontrar a su hijo en el infierno : Satanás ha disfrazado el hijo de un aspecto idéntico a otros once demonios, y él es más pesado o más ligero dependiendo de si está condenado a mentir o si es capaz de hablar con sinceridad. La solución del libro sigue el ejemplo 1.c.
- Beremiz, el personaje principal del libro de Júlio César de Mello e Souza El hombre que contaba , se encuentra con un comerciante indio que lo desafía con el rompecabezas de equilibrio estándar con ocho perlas de idéntica forma (una perla ligeramente más clara que el resto). Beremiz lo resuelve enmarcando explícitamente todas las variables del problema, utilizando solo dos ponderaciones.
En television
- En el episodio "The Wedding Scammer" de Cyberchase , el grupo de protagonistas debe encontrar una llave más ligera entre ocho llaves (las otras siete pesan lo mismo), y la resuelven subóptimamente, con tres ponderaciones, cuando dos son suficientes.
- En el episodio "The Bye-Bye Sky High IQ Murder Case" de Columbo , Columbo resuelve el siguiente acertijo: https://www.mathsisfun.com/puzzles/weighing-10-bags-solution.html
- En el episodio "Capitán Peralta" de Brooklyn Nine-Nine , Holt presenta a su equipo una versión del problema de las doce monedas que involucra a doce hombres y un balancín.
Referencias
- ^ Weisstein, Eric W. "Pesaje" . mathworld.Wolfram.com . Consultado el 16 de agosto de 2017 .
- ^ Grossman, Howard (1945). Scripta Mathematica XI .
- ^ http://mathforum.org/library/drmath/view/55618.html
- ^ a b c Chudnov, Alexander M. (2015). "Pesaje de algoritmos de clasificación e identificación de situaciones". Matemáticas y aplicaciones discretas . 25 (2): 69–81. doi : 10.1515 / dma-2015-0007 . S2CID 124796871 .
- ^ Khovanova, Tanya (2013). "Solución al problema de las monedas falsas y su generalización". arXiv : 1310.7268 [ matemáticas.HO ].