Rompecabezas de equilibrio

Un rompecabezas de equilibrio o rompecabezas de pesaje es un juego de lógica que consiste en equilibrar objetos (a menudo monedas) para determinar cuál tiene un peso diferente al resto, utilizando la balanza un número limitado de veces.La solución a las variantes más comunes de rompecabezas se resume en la siguiente tabla:

Conocido	Objetivo	Monedas máximas para n pesajes	Número de pesajes para c monedas
Si la moneda de destino es más ligera o más pesada que otros	Identificar moneda	${\displaystyle 3^{n}$	${\displaystyle \lceil \log _{3}(c)\rceil }$
La moneda de destino es diferente de otros	Identificar moneda	${\displaystyle {\tfrac {1}{2}}(3^{n}-1)}$	${\displaystyle \lceil \log _{3}(2c+1)\rceil }$
La moneda de destino es diferente de otros, o todas las monedas son iguales	Identificar si existe una moneda única, y si es más ligero o más pesado	${\displaystyle {\tfrac {2} {}} {}}} {}}} {}}} {}} {}}} {}}}} {}}}} {}}}}}} {}}}} {}}}}}} {}}}}} {}}}}} {}}}}}} {}}}}}}} {}}}}}}} {}}}}}}} {}}}}}}} {}}}}}}}}}}}}} {}}}}}}}}}}} {}}}}}}} {}}}}} {}}}}}}}}}}}}} {}}}}}}}}} {}}}}}}} {}}}}}}} {}}}}}}} {}}}}}}}}}}}}}}}}}}}}}$	${\displaystyle \lceil \log _{3}(2c+3)\rceil }$

Por ejemplo, al detectar una moneda disimilar en tres pesajes (⁠${\displaystyle n=3}$⁠), el número máximo de monedas que se pueden analizar es ⁠${\displaystyle {\tfrac {1}{2} {3}-1)=13}$⁠. Note que con ⁠${\displaystyle 3}$⁠ pesas y ⁠${\displaystyle 13}$⁠ monedas, no siempre es posible determinar la naturaleza de la última moneda (ya sea más pesado o más ligero que el resto), pero sólo que las otras monedas son todas iguales, lo que implica que la última moneda es la moneda disimilar. En general, con ⁠${\displaystyle n}$⁠ pesos, uno siempre puede determinar la identidad y la naturaleza de una sola moneda disimilar si hay ⁠${\displaystyle {\tfrac {2} {}} {}}} {}}} {}}} {}} {}}} {}}}} {}}}} {}}}}}} {}}}} {}}}}}} {}}}}} {}}}}} {}}}}}} {}}}}}}} {}}}}}}} {}}}}}}} {}}}}}}} {}}}}}}}}}}}}} {}}}}}}}}}}} {}}}}}}} {}}}}} {}}}}}}}}}}}}} {}}}}}}}}} {}}}}}}} {}}}}}}} {}}}}}}} {}}}}}}}}}}}}}}}}}}}}}$⁠ o menos monedas. En el caso de tres pesajes, es posible encontrar y describir una única moneda disimilar entre una colección de ⁠${\displaystyle 12}$⁠ monedas.

Esta versión de doce monedas del problema apareció impresa ya en 1945, y Guy y Nowakowski explican que "fue popular a ambos lados del Atlántico durante la Segunda Guerra Mundial; incluso se sugirió lanzarla sobre Alemania en un intento de sabotear su esfuerzo bélico".

Un ejemplo bien conocido incluye hasta nueve artículos, por ejemplo, monedas (o bolas), que pesan lo mismo, excepto uno, que es más ligero que los demás: una falsificación (una bola extraña). La diferencia solo se percibe al pesarlas en una báscula, pero solo se pueden pesar las monedas. ¿Cómo se puede aislar la moneda falsa con solo dos pesadas?Para encontrar una solución, primero consideramos el número máximo de objetos entre los cuales se puede encontrar el más ligero en una sola pesada. El máximo posible es tres. Para encontrar el más ligero, podemos comparar dos monedas cualesquiera, excluyendo la tercera. Si las dos monedas pesan lo mismo, entonces la más ligera debe ser una de las que no están en la balanza. De lo contrario, es la que la balanza indica como más ligera.Ahora, imaginemos las nueve monedas en tres pilas de tres monedas cada una. Con un solo movimiento, podemos determinar cuál de las tres pilas es más ligera (es decir, la que contiene la moneda más ligera). Luego, solo se necesita un movimiento más para identificar la moneda más ligera dentro de esa pila más ligera. Así, en dos pesadas, 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 entre 81 monedas.

Una versión más compleja tiene doce monedas, once de las cuales son idénticas. Si una es diferente, no sabemos si es más pesada o más ligera que las demás. En este caso, la balanza puede usarse tres veces para determinar si existe una moneda única y, de ser así, aislarla y determinar su peso en relación con las demás. (Este acertijo y su solución aparecieron por primera vez en un artículo de 1945). El problema tiene una variante más sencilla con tres monedas en dos pesadas y una variante más compleja con 39 monedas en cuatro pesadas.Este problema tiene más de una solución. Una es fácilmente escalable a un mayor número de monedas mediante numeración en base tres: etiquetar cada moneda con un número diferente de tres dígitos en base tres y colocar en el n-ésimo pesaje todas las monedas etiquetadas con el n-ésimo dígito idéntico a la etiqueta del plato (con tres platos, uno a cada lado de la balanza, etiquetados con 0 y 2, y uno fuera de la balanza, etiquetado con 1). Otros procedimientos paso a paso son similares al siguiente. Es menos sencillo para este problema, y el segundo y tercer pesaje dependen de lo que haya sucedido previamente, aunque no necesariamente sea así (ver más abajo).

• Cuatro monedas se ponen a cada lado. Hay dos posibilidades:

1. Un lado es más pesado que el otro. Si este es el caso, eliminar tres monedas del lado más pesado, mover tres monedas del lado más ligero al lado más pesado, y colocar tres monedas que no se pesaron la primera vez en el lado más ligero. (Recuerda qué monedas son cuáles.) Hay tres posibilidades:

1.a) El mismo lado que fue más pesado la primera vez es aún más pesado. Esto significa que la moneda que permaneció allí es más pesada o que la moneda que se quedó en el lado más ligero es más ligera. Balancing one of these against one of the other ten coins reveals which of these is true, thus resolution the puzzle.

1.b) El lado que fue más pesado la primera vez es más ligero la segunda vez. Esto significa que una de las tres monedas que pasaron del lado más ligero al lado más pesado es la moneda de luz. Para el tercer intento, pesar dos de estas monedas entre sí: si uno es más ligero, es la moneda única; si equilibran, la tercera moneda es la luz.

1.c) Ambos lados son iguales. Esto significa que una de las tres monedas que fue quitada del lado más pesado es la moneda pesada. Para el tercer intento, pesan dos de estas monedas entre sí: si uno es más pesado, es la moneda única; si equilibran, la tercera moneda es la pesada.

2. Ambos lados son iguales. Si este es el caso, las ocho monedas son idénticas y se pueden reservar. Tome las cuatro monedas restantes y coloque tres en un lado del balance. Lugar 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 usted ahora sabe que una de esas tres monedas es la extraña fuera y que es más ligero. Tomar dos de esas tres monedas y pesarlas entre sí. Si el balance indica que la moneda más ligera es la extraña. Si las dos monedas equilibran entonces la tercera moneda no en el balance es la extraña fuera y es más ligero.

2.b) Las tres monedas restantes son más pesadas. En este caso ahora sabes que una de esas tres monedas es la extraña y que es más pesada. Tomar dos de esas tres monedas y pesarlas entre sí. Si el saldo indica que la moneda más pesada es la extraña. Si las dos monedas equilibran entonces la tercera moneda que no está en el balance es la extraña hacia fuera y es más pesado.

2.c) Los tres saldos de monedas restantes. En este caso usted sólo tiene que pesar la moneda restante contra cualquiera de las otras 11 monedas y esto le dice si es más pesado, más ligero, o el mismo.

Dada una población de 13 monedas en la que se sabe que una de ellas tiene una masa diferente a la del resto, es sencillo determinar de qué moneda se trata con una balanza y tres pruebas, como se indica a continuación:

1) Subdivide 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í:

a. Si el saldo de las monedas, la moneda extraña está en la población de 5 y proceder a probar 2a.

b. La moneda extraña está entre la población de 8 monedas, proceder de la misma manera que en el problema de 12 monedas.

3) Prueba 2a, Prueba 3 de las monedas del grupo de 5 monedas contra cualquier 3 monedas de la población de 8 monedas:

a. Si el balance de 3 monedas, entonces la moneda extraña está entre la población restante de 2 monedas. Prueba una de las 2 monedas contra cualquier otra moneda; si equilibran, la moneda extraña es la última moneda no comprobada, si no equilibran, la moneda extraña es la moneda de prueba actual.

b. Si las 3 monedas no equilibran, entonces la moneda extraña es de esta población de 3 monedas. Preste atención a la dirección del balanceo (up significa que la moneda extraña es ligera, abajo significa que es pesado). Quitar una de las 3 monedas, mover otro al otro lado del balance (remover todas las otras monedas del balance). Si el saldo se equilibra, la moneda extraña es la moneda que fue quitada. Si el balance cambia la dirección, la moneda extraña es la que se movió al otro lado, de lo contrario, la moneda extraña es la moneda que permaneció en su lugar.

Si hay una moneda auténtica como referencia, las monedas sospechosas pueden ser trece. Numere las monedas del 1 al 13 y la auténtica, el 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 se desequilibra una vez, debe ser una de las monedas 1, 2 o 3, que solo aparecen en un pesaje. Si nunca se desequilibra, debe ser una de las monedas 10 a 13 que aparecen en todos los pesajes. Siempre es posible identificar la moneda falsa correspondiente a cada uno de los 27 resultados (13 monedas, una demasiado pesada o una demasiado ligera, son 26 posibilidades), excepto cuando todos los pesajes están equilibrados, en cuyo caso no hay ninguna moneda falsa (o su peso es correcto). Si se eliminan las monedas 0 y 13 de estos pesajes, se obtiene una solución genérica al problema de las 12 monedas.

Si dos monedas son falsas, este procedimiento, por lo general, no selecciona ninguna de ellas, sino una moneda auténtica. Por ejemplo, si las monedas 1 y 2 son falsas, la moneda 4 o la 5 se seleccionan incorrectamente.En una variante relajada de este rompecabezas, solo se necesita encontrar la moneda falsa sin poder determinar necesariamente su peso en relación con las demás. En este caso, cualquier solución que previamente pesara todas las monedas en un momento dado puede adaptarse para admitir una moneda adicional. Esta moneda nunca se pesa, pero si todos los pesos están equilibrados, se considera la moneda falsa. No es posible hacerlo mejor, ya que a cualquier moneda que se pese en un momento dado y se considere falsa, siempre se le puede asignar un peso en relación con las demás.Un método que pesa los mismos conjuntos de monedas independientemente del resultado permite...

1. (entre 12 monedas A–L) concluyen si todos pesan lo mismo, o encuentran la moneda extraña y dicen si es más ligero o más pesado, o
2. (entre 13 monedas A–M) encontrar la moneda extraña, y, a 12/13 probabilidad, decir si es más ligero o más pesado (para la probabilidad 1/13 restante, sólo que es diferente).

Los tres resultados posibles de cada pesaje se representan con "\" para el lado izquierdo más ligero, "/" para el lado derecho más ligero y "–" para ambos lados con el mismo peso. Los símbolos de los pesajes se listan 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 pesajes dan los siguientes 3³ = 27 resultados. Excepto por "–––", los conjuntos se dividen de tal manera que cada conjunto de la derecha tiene un "/" donde el conjunto de la izquierda tiene un "\", y viceversa:

/// \\\\\

\////
/ \/ \/\
//\\\\\/

\/
–\/
/- \–/

¿Qué?
- '
#

/––
––
– – ––

––

Como cada pesaje solo da un resultado significativo cuando el número de monedas del lado izquierdo es igual al del lado derecho, ignoramos la primera fila, de modo que cada columna tenga el mismo número de símbolos "\" y "/" (cuatro de cada uno). Las filas están etiquetadas; el orden de las monedas es irrelevante:

\/// Una luz /\\\\ un pesado
/\/B light \/\ B heavy
// C light \\/ C heavy

#/- D light /\-D heavy
- '/ E light -/ 'E heavy
/–\ F light \–/ F heavy

# G light // G heavy
- 'H light -/ H heavy
# I light // I heavy

/– J light \– J heavy
–/– Lámpara K–
– / L luz – ‘L pesado

–– M más ligero o más pesado (caso de 13 monedas),
o todas las monedas pesan el mismo caso (12 monedas)

Usando el patrón de resultados anterior, se puede determinar la composición de las 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 que ese lado sea más claro), en el lado derecho en el segundo y sin usar en el tercero:

1o peso: lado izquierdo: ADGI, lado derecho: BCFJ
2o peso: lado izquierdo: ALTO, lado derecho: ACDK
3o peso: lado izquierdo: CFHI, lado derecho: ABEL

Los resultados se leen de la tabla. Por ejemplo, si el lado derecho pesa menos en las dos primeras pesadas y ambos lados pesan lo mismo en la tercera, el código correspondiente «//– G pesada» implica que la moneda G es la impar y pesa más que las demás.

En otra generalización de este problema, tenemos dos escalas de equilibrio que se pueden utilizar en paralelo. Por ejemplo, si usted sabe exactamente una moneda es diferente pero no sabe si es más pesado o más ligero que una moneda normal, entonces en ${\displaystyle n}$ rondas, puedes resolver el problema con la mayoría ${\displaystyle (5^{n}-5)/2$ monedas.

La generalización de este problema se describe en Chudnov.

Vamos. ${\displaystyle \mathbb {R} {} {}} {\fn}}$ ser el ${\displaystyle n}$-dimensional Espacio euclidiano y ${\displaystyle [\mathrm {e} {1},\mathrm {e}$ ser el producto interno de los vectores ${\displaystyle \mathrm {e}$ y ${\displaystyle \mathrm {e} {2}$ desde ${\displaystyle \mathbb {R} ^{n}$ Para vectores ${\displaystyle \mathrm {e} =(e_{1},\dotse_{n}\in \mathbb {R} ^{n}$ y subconjuntos ${\displaystyle E=\{\mathrm {e}\subseteq \mathbb {R} ^{n}$ las operaciones ${\displaystyle (\cdot)}}$ y ${\displaystyle (\cdot)}$ se definen, respectivamente, como ${\displaystyle \mathrm {e} {}=(sign(e_{i})_{i}}$; ${\displaystyle ¿Qué?$, ${\displaystyle \mathrm {e} ^{+}=(Primersign(e_{i})$, ${\displaystyle ¿Qué?$ Por ${\displaystyle I^{n}$ denotaremos la discreta [−1; 1] ${\displaystyle \mathbb {R} {} {}} {\fn}}$; es decir, el conjunto de todas las secuencias de longitud ${\displaystyle n}$ sobre el alfabeto ${\displaystyle I=\{-1,0,1\}$ El set ${\displaystyle I_{t}{n}=\{\mathrm {x}\in I^{n}Sobrevivw(\mathrm {x}\leq t\}\subseteq I^{n}$ es la bola discreta del radio ${\displaystyle t}$ (en la métrica Hamming ${\displaystyle w()}$) con centro en el punto ${\displaystyle \mathrm {0}$ Pesos relativos de ${\displaystyle n}$ objetos son dados por un vector ${\displaystyle \mathrm {x} =(x_{1},\dotsx_{n}\in I^{n}$ que define las configuraciones de pesos de los objetos: ${\displaystyle i}$t objeto tiene peso estándar si ${\displaystyle x_{i}=0;}$ el peso del ${\displaystyle i}$t objeto es mayor (smaller) por un valor constante (no conocido) si ${\displaystyle x_{i}=1}$ (respectivamente, ${\displaystyle x_{i}=-1}$). El vector ${\displaystyle \mathrm {x}$ 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) es dado por un vector ${\displaystyle \mathrm {h} \in I^{n}$ el resultado de un peso para una situación ${\displaystyle \mathrm {x}\in I^{n}$ es ${\displaystyle s(\mathrm {x};\mathrm {h})=sign([\mathrm {x};\mathrm {h} ]).}$ El peso dado por un vector ${\displaystyle \mathrm {h} =(h_{1},\dotsh_{n}}$ tiene la siguiente interpretación: para un cheque dado el ${\displaystyle i}$t objeto participa en el pesaje si ${\displaystyle h_{i}\neq 0}$; se pone en el balance de la izquierda si ${\displaystyle ¿Qué?$ y se pone en la cacerola derecha si ${\displaystyle ¿Qué?$ Para cada pesaje ${\displaystyle \mathrm {h}$, ambas sartenes deben contener el mismo número de objetos: si en alguna cacerola el número de objetos es menor de lo que debe ser, entonces recibe algunos ${\displaystyle r(\mathrm {h}=[\mathrm {h};1,\dots1]}$ objetos de referencia. El resultado de un pesaje ${\displaystyle s(\mathrm {x};\mathrm {h})}$ describe los siguientes casos: el saldo si ${\displaystyle s(\mathrm {x};\mathrm {h}=0}$, la sartén izquierda supera a la derecha si ${\displaystyle s(\mathrm {x};\mathrm {h}=-1}$, y la cacerola derecha supera la izquierda si ${\displaystyle s(\mathrm {x};\mathrm {h})=1.}$ La falta de 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 ${\displaystyle Z\subseteq I^{n}$ que también se llama el conjunto de situaciones admisibles, los elementos ${\displaystyle z\in Z}$ se llaman situaciones admisibles.

Cada pesaje ${\displaystyle \mathrm {h}$ induce la partición del conjunto ${\displaystyle I^{n}$ por el avión (hiperplano) ${\displaystyle [\mathrm {x}\mathrm {h}=0}$ en tres partes ${\displaystyle W(s habitI^{n};\mathrm {h}=\{\mathrm {x}\in I^{n} bendiciones(\mathrm {x};\mathrm {h})=s\}$, ${\displaystyle s\in I,}$ y define la partición correspondiente del conjunto ${\displaystyle Z=W(0 imperZ,\mathrm {h})+W(1 vidasZ,\mathrm {h})+W(-1 vidasZ,\mathrm {h}),}$ Donde ${\displaystyle W(s habitZ,\mathrm {h})=W(s habitI^{n},\mathrm {h})\cap Z.}$

Definición 1. Un algoritmo de pesaje (WA) ${\displaystyle {\fnMithcal}}$ de longitud ${\displaystyle m}$ es una secuencia ${\displaystyle {\Mathcal {}=traducido\mathrm {A} _{1},\dots\mathrm {A} {m} título,}$ Donde ${\displaystyle \mathrm {A} _{j}:I^{j-1}\to I^{n}$ es la función que determina el cheque ${\displaystyle \mathrm {h} ^{j}=\mathrm {A} _{j}(s^{j-1});\mathrm {h} ^{j}\in I^{n}$ a cada uno ${\displaystyle j}$a paso, ${\displaystyle j=1,2,\dotsm,}$ del algoritmo de los resultados de ${\displaystyle \mathrm {s} ^{j-1}=(s_{1},\dotss_{j-1})\in I^{j-1}$ pesos en los pasos anteriores (${\displaystyle \mathrm {h} }=\mathrm {A} _{1}()}$ es un cheque inicial dado).

Vamos. ${\displaystyle S(Z,{\mathcal {A}}}$ ser el conjunto de todos ${\displaystyle (Z,{\mathcal {A})}$- Síndromes y ${\displaystyle W(s tuberculosis{\mathcal {A})\subseteq I}$ ser el conjunto de situaciones con el mismo síndrome ${\displaystyle s}$i.e., ${\displaystyle W(s habit{\mathcal {A})=\{\mathrm {z}\in I^{m}prehensis(z sometida{\mathcal {A})=s\}$; ${\displaystyle W(s habitZ;{\mathcal {A})=W(s detained{\mathcal {A})\cap Z.}$

Definición 2. A WA ${\displaystyle {\fnMithcal}}$ se dice: a) identificar las situaciones en un conjunto ${\displaystyle Z}$ si la condición ${\fnMicrosoft Sans Serif}$ está satisfecho para todos ${\displaystyle s\in S(Z{\mathcal {A});}$b) identificar los tipos de objetos en un conjunto ${\displaystyle Z}$ si la condición ${\displaystyle TENW^{+}(s habitZ{\mathcal {A})$ está satisfecho para todos ${\displaystyle s\in S(Z{\mathcal {A}).}$

Se prueba en que para los llamados conjuntos adecuados ${\displaystyle Z}$ un algoritmo de identificación de los tipos identifica también las situaciones ${\displaystyle Z.}$

Como ejemplo, los algoritmos dinámicos perfectos (dos cascadas) con parámetros ${\displaystyle n=11,m=5,t=2}$ se construyen en los que corresponden a los parámetros del código Golay ternario perfecto (código Virtakallio-Golay). Al mismo tiempo, se establece que una WA estática (es decir, código de ponderación) con los mismos parámetros no existe.

Cada uno de estos algoritmos usando 5 pesajes encuentra entre 11 monedas hasta dos monedas falsificadas que podrían ser más pesados o más ligeros que las monedas reales por el mismo valor. En este caso el dominio de incertidumbre (el conjunto de situaciones admisibles) contiene ${\displaystyle 1+2C_{11}{1}+2^{2}C_{11}=3^{5}$ situaciones, es decir, la ES construida se encuentra en el límite de Hamming ${\displaystyle t=2}$ y en este sentido es perfecto.

Hasta la fecha no se sabe si hay otra WA perfecta que identifique las situaciones en ${\displaystyle Yo...$ para algunos valores ${\displaystyle n,t}$. Además, no se sabe si para algunos ${\displaystyle t fiel2}$ existen soluciones para la ecuación ${\displaystyle \sum ¿Qué?$(correspondiendo al límite de Hamming para códigos ternarios) que es, obviamente, necesario para la existencia de una WA perfecta. Sólo se sabe que ${\displaystyle t=1}$ no hay una WA perfecta, y para ${\displaystyle t=2}$ esta ecuación tiene la solución única ${\displaystyle n=11,m=5}$ que determina los parámetros de la ES perfecta construida.

• El gran rompecabezas de pesas en NRICH