Rompecabezas de equilibrio

Un rompecabezas de equilibrio o de pesaje es un rompecabezas de lógica que consiste en equilibrar objetos, a menudo monedas, para determinar cuál tiene un peso diferente al de los demás, utilizando una balanza un número limitado de veces.

La solución a las variantes más comunes del rompecabezas se resume en la siguiente tabla: ^{[ 1 ]}

Por ejemplo, al detectar una moneda diferente en tres pesajes ( ⁠${\displaystyle n=3}$⁠ ), el número máximo de monedas que se pueden analizar es ⁠${\displaystyle {\tfrac {1}{2}}(3^{3}-1)=13}$⁠ . Tenga en cuenta que con ⁠${\displaystyle 3}$pesajes y​${\displaystyle 13}$En las monedas, no siempre es posible determinar la naturaleza de la última moneda (si es más pesada o más ligera que las demás), sino solo que las otras monedas son todas iguales, lo que implica que la última moneda es la diferente. En general, con${\displaystyle n}$⁠ pesajes, siempre se puede determinar la identidad y la naturaleza de una sola moneda disímil si hay ⁠${\displaystyle {\tfrac {1}{2}}(3^{n}-3)}$o menos monedas. En el caso de tres pesajes, es posible encontrar y describir una sola moneda diferente entre una colección de${\displaystyle 12}$monedas .

Esta versión del problema, compuesta por doce monedas, apareció impresa ya en 1945 ^{[ 2 ] [ 3 ]} 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". ^{[ 3 ]}

Un ejemplo conocido consiste en hasta nueve objetos, digamos monedas (o bolas), que tienen el mismo peso excepto uno, que es más ligero que los demás: una falsificación (una pieza atípica). La diferencia solo se puede percibir pesándolas en una balanza , pero solo se pueden pesar las monedas. ¿Cómo se puede aislar la moneda falsificada con solo dos pesajes?

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 hay 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 en 1945. ^{[ 2 ]} ) El problema tiene una variante más simple con tres monedas en dos pesajes, y una variante más compleja con 39 monedas en cuatro pesajes.

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 cuál es esa moneda con una balanza y 3 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, compara los 2 grupos de 4 monedas entre sí:

a. Si las monedas se equilibran, la moneda extraña está en la población de 5 y procede a la prueba 2a.

b. La moneda que no es la misma está entre las 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 cualesquiera 3 monedas de la población de 8 monedas:

a. Si las 3 monedas se equilibran, entonces la moneda diferente se encuentra entre las 2 monedas restantes. Prueba una de las 2 monedas contra cualquier otra moneda; si se equilibran, la moneda diferente es la última moneda sin probar; si no se equilibran, la moneda diferente es la moneda que se está probando actualmente.

b. Si las 3 monedas no se equilibran, la moneda sobrante pertenece a este grupo. Observa la dirección del balanceo (hacia arriba, la moneda sobrante es más ligera; hacia abajo, es más pesada). Retira una de las 3 monedas y mueve otra al otro lado del balanceo (retira las demás). Si el balance se equilibra, la moneda sobrante es la que se retiró. Si el balance cambia de dirección, la moneda sobrante es la que se movió al otro lado; de lo contrario, es la que permaneció en su lugar.

/// \\\ \// /\\ /\/ \/\ //\ \\/ \/– /\– –\/ –/\ /–\ \–/ \\– //– –\\ –// \–\ /–/ /–– \–– –/– –\– ––/ ––\ ––– 

\// Una luz /\\ Una pesada /\/ B ligero \/\ B pesado //\ C ligero \\/ C pesado \/– Re ligero /\– Re pesado –\/ E ligero –/\ E pesado /–\ F ligero \–/ F pesado – Sol ligero // – Sol pesado –\\ H ligero –// H pesado \–\ Yo ligero /–/ Yo 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 (estuche para 12 monedas) 

Primer pesaje: lado izquierdo: ADGI, lado derecho: BCFJ Segundo pesaje: lado izquierdo: BEGH, lado derecho: ACDK Tercer pesaje: lado izquierdo: CFHI, lado derecho: ABEL 

En otra generalización de este problema, tenemos dos balanzas que se pueden usar en paralelo. Por ejemplo, si sabes exactamente que una moneda es diferente pero no sabes si es más pesada o más ligera que una moneda normal, entonces en${\displaystyle n}$rondas, puedes resolver el problema con como máximo${\displaystyle (5^{n}-5)/2}$monedas. ^{[ 6 ]}

La generalización de este problema se describe en Chudnov. ^{[ 7 ]}

Dejar${\displaystyle \mathbb {R} ^{n}}$ser el${\displaystyle n}$espacio euclidiano de -dimensiones y${\displaystyle [\mathrm {e} ^{1},\mathrm {e} ^{2}]}$sea ​​el producto interno de vectores${\displaystyle \mathrm {e} ^{1}}$y ${\displaystyle \mathrm {e} ^{2}}$de ${\displaystyle \mathbb {R} ^{n}.}$Para vectores ${\displaystyle \mathrm {e} =(e_{1},\dots ,e_{n})\in \mathbb {R} ^{n}}$y subconjuntos ${\displaystyle E=\{\mathrm {e} ^{j}\}\subseteq \mathbb {R} ^{n},}$las operaciones ${\displaystyle (\cdot )^{*}}$y ${\displaystyle (\cdot )^{+}}$se definen, respectivamente, como ${\displaystyle \mathrm {e} ^{*}=(sign(e_{i}))_{i}}$ ;${\displaystyle E^{*}=\{(\mathrm {e} ^{j})^{*}\}}$,${\displaystyle \mathrm {e} ^{+}=(|sign(e_{i})|)_{i}}$,${\displaystyle E^{+}=\{(\mathrm {e} ^{j})^{+}\}.}$ Por ${\displaystyle I^{n}}$Denotaremos el cubo discreto [−1; 1] en ${\displaystyle \mathbb {R} ^{n}}$; es decir, el conjunto de todas las secuencias de longitud ${\displaystyle n}$sobre el alfabeto ${\displaystyle I=\{-1,0,1\}}$El conjunto ${\displaystyle I_{t}^{n}=\{\mathrm {x} \in I^{n}|w(\mathrm {x} )\leq t\}\subseteq I^{n}}$es la bola discreta de radio ${\displaystyle t}$ (en la métrica de Hamming)${\displaystyle w()}$) con centro en el punto ${\displaystyle \mathrm {0} .}$Pesos relativos de ${\displaystyle n}$Los objetos se representan mediante un vector.${\displaystyle \mathrm {x} =(x_{1},\dots ,x_{n})\in I^{n},}$que define las configuraciones de pesos de los objetos: el ${\displaystyle i}$El objeto tiene un peso estándar si ${\displaystyle x_{i}=0;}$el peso del ${\displaystyle i}$El objeto es mayor (menor) en un valor constante (desconocido) 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 pesaje (una verificación) viene dado por un vector ${\displaystyle \mathrm {h} \in I^{n};}$el resultado de una ponderación 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},\dots ,h_{n})}$tiene la siguiente interpretación: para una verificación dada, ${\displaystyle i}$El objeto participa en el pesaje si ${\displaystyle h_{i}\neq 0}$; se coloca en el plato de equilibrio izquierdo si${\displaystyle h_{i}<0}$y se coloca en la sartén correcta si${\displaystyle h_{i}>0.}$Para cada pesaje${\displaystyle \mathrm {h} }$, ambas bandejas deben contener la misma cantidad de objetos: si en alguna bandeja la cantidad de objetos es menor de lo que debería ser, entonces recibe algunos${\displaystyle r(\mathrm {h} )=[\mathrm {h} ;1,\dots ,1]}$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} , el plato izquierdo pesa más que el derecho si${\displaystyle s(\mathrm {x}$ ;\mathrm {h} )=-1} , y el plato derecho pesa más que el izquierdo si${\displaystyle s(\mathrm {x}$ ;\mathrm {h} )=1.} 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.${\displaystyle Z\subseteq I^{n},}$que también se denomina el conjunto de situaciones admisibles, los elementos de ${\displaystyle z\in Z}$ se denominan situaciones admisibles.

Cada pesaje${\displaystyle \mathrm {h} }$induce la partición del conjunto${\displaystyle I^{n}}$por el plano ( hiperplano )${\displaystyle [\mathrm {x}$ ;\mathrm {h} ]=0} en tres partes ${\displaystyle W(s|I^{n};\mathrm {h} )=\{\mathrm {x} \in I^{n}|s(\mathrm {x}$ ;\mathrm {h} )=s\}} , ${\displaystyle s\in I,}$y define la partición correspondiente del conjunto ${\displaystyle Z=W(0|Z,\mathrm {h} )+W(1|Z,\mathrm {h} )+W(-1|Z,\mathrm {h} ),}$dónde ${\displaystyle W(s|Z,\mathrm {h} )=W(s|I^{n},\mathrm {h} )\cap Z.}$

Definición 1. Un algoritmo de ponderación (AP)${\displaystyle {\mathcal {A}}}$de longitud ${\displaystyle m}$es una secuencia ${\displaystyle {\mathcal {A}}=<\mathrm {A} _{1},\dots ,\mathrm {A} _{m}>,}$dónde ${\displaystyle \mathrm {A} _{j}:I^{j-1}\to I^{n}}$es la función que determina la verificación ${\displaystyle \mathrm {h} ^{j}=\mathrm {A} _{j}(s^{j-1});\mathrm {h} ^{j}\in I^{n},}$en cada ${\displaystyle j}$º paso,${\displaystyle j=1,2,\dots ,m,}$ del algoritmo a partir de los resultados de ${\displaystyle \mathrm {s} ^{j-1}=(s_{1},\dots ,s_{j-1})\in I^{j-1}}$pesajes en los pasos anteriores (${\displaystyle \mathrm {h} ^{1}=\mathrm {A} _{1}()}$es una verificación inicial dada).

Dejar ${\displaystyle S(Z,{\mathcal {A}})}$ser el conjunto de todos ${\displaystyle (Z,{\mathcal {A}})}$-síndromes y ${\displaystyle W(s|{\mathcal {A}})\subseteq I}$ser el conjunto de situaciones con el mismo síndrome ${\displaystyle s}$; es decir,${\displaystyle W(s|{\mathcal {A}})=\{\mathrm {z} \in I^{m}|s(z|{\mathcal {A}})=s\}}$; ${\displaystyle W(s|Z;{\mathcal {A}})=W(s|{\mathcal {A}})\cap Z.}$

Definición 2. Un WA ${\displaystyle {\mathcal {A}}}$Se dice que: a) identifica las situaciones en un conjunto ${\displaystyle Z}$ si la condición ${\displaystyle |W(s|Z,{\mathcal {A}})|=1}$está satisfecho por todos ${\displaystyle s\in S(Z{\mathcal {A}});}$ b) identificar los tipos de objetos en un conjunto ${\displaystyle Z}$ si la condición ${\displaystyle |W^{+}(s|Z{\mathcal {A}})|=1}$está satisfecho por todos ${\displaystyle s\in S(Z{\mathcal {A}}).}$

^{En [ 7 ]} se demuestra que para los llamados conjuntos adecuados${\displaystyle Z}$un algoritmo de identificación los tipos identifica también las situaciones en${\displaystyle Z.}$

Como ejemplo, los algoritmos dinámicos perfectos (de dos cascadas) con parámetros${\displaystyle n=11,m=5,t=2}$^{En [ 7 ]} se construyen parámetros que corresponden al código Golay ternario perfecto (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, utilizando 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) contiene${\displaystyle 1+2C_{11}^{1}+2^{2}C_{11}^{2}=3^{5}}$situaciones, es decir, el WA construido se encuentra en el Hamming con destino a${\displaystyle t=2}$y en este sentido es perfecto.

Hasta la fecha se desconoce si existen otros WA perfectos que identifiquen las situaciones en${\displaystyle I_{t}^{n}}$para algunos valores de${\displaystyle n,t}$Además, se desconoce si para algunos${\displaystyle t>2}$Existen soluciones para la ecuación ${\displaystyle \sum _{i=0}^{t}2^{i}C_{n}^{i}=3^{m}}$ (correspondiente al límite de Hamming para códigos ternarios) que, obviamente, es necesario para la existencia de un WA perfecto. Solo se sabe que para${\displaystyle t=1}$No hay WA perfectos, y para${\displaystyle t=2}$Esta ecuación tiene una solución no trivial única.${\displaystyle n=11,m=5}$lo cual determina los parámetros del WA perfecto construido.

• El gran rompecabezas de pesos en NRICH