Nuestro conjunto reciente de acertijos presentaba la humilde balanza de doble plato, históricamente un símbolo del comercio y el gobierno, el arte y la ciencia. Las balanzas también son populares en las matemáticas recreativas. Los acertijos de equilibrio requieren un razonamiento lógico claro y se prestan bien a la generalización matemática. veamos como ¿Cuánto los lectores equilibraron estas cualidades en los acertijos a continuación.
Puzzle 1
Tienes ocho monedas de aspecto idéntico. Uno es falso y más ligero que los otros, que tienen pesos idénticos. Encuentra la moneda mala en dos pesajes. Encuentre la fórmula general para el número máximo de monedas para las que puede encontrar la falsificación en x pesajes
Abordar una versión simple de un problema a menudo revela la clave de la solución. En este caso, imagina que tienes solo tres monedas, con una más ligera que las otras dos. Si compara uno de ellos con uno de los otros dos, se equilibrarán o no. Si no lo hacen, ya sabes cuál es más ligero. Si se equilibran, entonces el tercero es el ligero. Solo necesitas un único pesaje.
Entonces, en este rompecabezas, si puede aislar un grupo de tres (o menos) que contengan la moneda ligera en el primer pesaje, solo necesitará un pesaje más. Puede hacer esto equilibrando tres contra otros tres. Si los dos grupos están desequilibrados, ha encontrado el grupo que contiene el ligero y puede proceder como se indicó anteriormente para el segundo pesaje. Si se equilibran, solo pesa las dos monedas restantes entre sí y encontrarás la más liviana.
Tenga en cuenta que esto también funciona si hay tres en el grupo no pesado, por lo que podríamos haber comenzado con nueve monedas. Siguiendo esta lógica, y partiendo de tres monedas, por cada pesaje adicional podemos encontrar la moneda ligera en tres veces el número de monedas que teníamos anteriormente. La fórmula que nos da el número máximo de monedas n in w pesaje es por lo tanto n = 3w.
Puzzle 2
Tienes 12 monedas de aspecto idéntico. Uno es más pesado o más liviano que los otros, que tienen pesos idénticos.
-
Encuentra la moneda mala en tres pesajes.
-
¿Cuál es el número máximo de monedas para las que puedes encontrar la mala en cuatro pesajes? Describe cómo encontrarías la moneda falsa.
La solución a este rompecabezas fue bien descrita por Ted, quien también demostró que en realidad se puede detectar la moneda defectuosa entre 13 monedas en tres pesajes. Aquí está la solución de Ted (con muescas para separar los tres pesos en cada caso):
Comience pesando 4 monedas contra 4 monedas.
Caso 1: Si no está balanceada, para el segundo pesaje coloque 2 de cada lado más pesado en ambos lados de la balanza junto con 1 de cada lado más liviano.
1a: Si no está balanceada, la moneda mala son las 2 monedas que aún están en el lado pesado o la moneda única que aún está en el lado ligero.
Pesar las 2 monedas pesadas posibles, la mala es la más pesada de las dos, o la única ligera si están equilibradas.
1b: Si se equilibra el segundo pesaje, la moneda mala es una de las 2 no utilizadas del lado más claro del primer pesaje.
Pesarlos uno contra el otro, el más ligero es malo.
Caso 2: Si está balanceada, la moneda mala es una de las 5 restantes. Pese 3 de esos contra 3 ya pesados (que se sabe [que son] buenos).
Caso 2a: Si está desequilibrado, sabes que la moneda mala es una de esas 3 y si es ligera o pesada.
El tercer pesaje es cualquiera de 2 de esos uno contra el otro: si no está balanceado, eso identifica la moneda mala, si está balanceado, es el último de los tres.
Caso 2b: Si el segundo pesaje está equilibrado, la moneda mala es una de las 2 restantes.
Pese cualquiera de ellos contra una buena moneda conocida. Si este resultado está desequilibrado, esta nueva moneda es mala y sabes si es pesada o ligera. Si este resultado está equilibrado, la moneda número 13 es mala, pero no se sabe si es pesada o ligera (que no necesitamos saber, así que hemos terminado).
Ted también pasó a mostrar que el número máximo de monedas para cuatro pesajes es 40. La fórmula para este rompecabezas es: n = (3w − 1)/2.
Para los acertijos restantes, las fórmulas generalizadas aún están siendo investigadas por matemáticos profesionales y son objeto de artículos publicados, algunos de los cuales han sido citados por Rainer en la primavera. Me limitaré a las soluciones para el pequeño número de monedas que consideramos en los acertijos y solo mencionaré las generalizaciones que se derivan naturalmente de los métodos utilizados en estos casos.
Puzzle 3
Esta es una variación del rompecabezas 1. Nuevamente tienes ocho monedas de aspecto idéntico, una de las cuales es más liviana que las otras. Sin embargo, ahora tienes tres escalas. Dos de las escalas funcionan, pero la tercera está rota y da resultados aleatorios (a veces es correcto ya veces incorrecto). No sabes qué escala está rota. ¿Cuántas pesadas se necesitarán para encontrar la moneda ligera?
Como vimos en el problema 1, esto requiere solo dos pesajes con una buena balanza. También sabemos que las dos balanzas buenas siempre estarán de acuerdo, por lo que si repetimos cada pesaje en las tres balanzas, tendremos la respuesta en seis pesajes, como sugirió un lector. Si tratamos de hacerlo en un número menor de pesajes, se complica un poco. No podemos identificar una buena báscula simplemente pesando las mismas monedas en dos básculas, porque incluso si concuerdan, cualquiera de las dos podría seguir siendo una mala báscula. (Esto también muestra cuán fácilmente la desinformación o la información aleatoria pueden ofuscar la verdad).
De hecho, este problema se puede resolver, muy inteligentemente, ¡en solo cuatro pesajes! Rainer en la primavera publicó la solución utilizando una notación novedosa que parece haber sido creada para este rompecabezas. Pero antes de ir allí, quiero que imagine un escenario que espero haga las cosas más intuitivas.
Imagina que eres un detective que investiga un atropello con fuga en un pequeño país cuyos automóviles tienen placas de matrícula de dos dígitos y solo usan los dígitos 0, 1 y 2. Tres personas, A, B y C, observaron el incidente. Dos de ellos siempre responden correctamente una pregunta de tres opciones y uno da respuestas completamente aleatorias. No sabes quién es el que responde al azar. Tienes que hacerles a cada uno de ellos una sola pregunta de tres opciones y luego elegir al que definitivamente dice la verdad para obtener más información.
Así es como lo haces. Pregúntele a A si el primer dígito es 0, 1 o 2. Digamos que A dice 2. Pregúntele a B si el segundo dígito es 0, 1 o 2. Digamos que B dice 1. Luego pídale a C que elija entre estas tres declaraciones:
- Solo A dice la verdad.
- Solo B dice la verdad.
- Ambos están diciendo la verdad.
Puedes creer en el que C te dice y preguntarle a esa persona sobre el otro dígito. Para ver por qué, considere que si A está mintiendo, entonces C es confiable y dirá que B está diciendo la verdad. De hecho, el segundo dígito será 1 y luego puede preguntarle a B sobre el primer dígito. De manera similar, si B está mintiendo, entonces C vuelve a ser confiable y dirá que A está diciendo la verdad. Entonces el primer dígito es de hecho 2 y puedes preguntarle a A sobre el segundo dígito. Finalmente, si C está mintiendo, tanto A como B son confiables, por lo que aún puede creer y elegir a quien C le diga. (Y si C dice que tanto A como B están diciendo la verdad, entonces ambos deben estarlo). La clave aquí es que su elección de preguntas no le permite a C mentir de tal manera que ponga en duda tanto a A como a B. Dado que al menos uno de A y B debe ser confiable, siempre puede elegir el que esté de acuerdo con C, incluso si es solo una respuesta aleatoria. Si los tres están de acuerdo, entonces ya tienes los dos dígitos de la placa.
Aquí le mostramos cómo traducir esta historia a nuestro rompecabezas. Las escalas son A, B y C. Puede convertir los dos dígitos de la matrícula en monedas de la siguiente manera: 01 es la moneda 1, 02 es la moneda 2, 10 es la moneda 3, 11 es la moneda 4, 12 es la moneda 5, 20 es la moneda 6, 21 es la moneda 7 y 22 es la moneda 8. Los lectores astutos reconocerán que este es el sistema numérico de base 3 (o ternario). También tenga en cuenta que hay un posible número 00 adicional, que puede usar para una novena moneda para la que esta técnica también funcionará, como en el rompecabezas 1.
Para el primer pesaje, divide las monedas por su primer dígito (base 3), por lo que tus tres grupos serán monedas [1, 2], [3, 4, 5] y [6, 7, 8]. Pese [3, 4, 5] contra [6, 7, 8] en la báscula A. Si A funciona bien, tendrá el grupo de primer dígito correcto como en el rompecabezas 1. De manera similar, para el segundo pesaje en la báscula B, sus grupos serán los que tengan el mismo segundo dígito: [1, 4, 7], [2, 5, 8] y [3, 6]. Si B funciona bien, tendrá el segundo dígito correcto. Para el tercer pesaje, en la balanza C, se pesa el grupo que A identificó contra el grupo que hizo B. Siguiendo nuestro ejemplo, para el 21, los grupos serán [6, 7, 8] y [1, 4, 7]. La moneda 7 no se puede poner en ambos lados al mismo tiempo, así que la dejamos afuera y pesamos [6, 8] y [1, 4] uno contra el otro. Tenga en cuenta que si tanto A como B son confiables, entonces 7 es de hecho la respuesta correcta, y no importa de qué lado sale más ligero en C. Si por casualidad el peso en C está equilibrado, entonces las tres escalas concuerdan, y tienes tu respuesta (moneda 7) en tan solo tres pesadas. Si A es confiable y B no, la moneda más liviana está en [6, 8], cuya escala C confirmará, y si B es confiable y A no, la moneda más liviana está en [1, 4], cuya escala C también confirmará.
Entonces, en tres pesajes, identificamos la moneda ligera o la redujimos a un grupo de dos, y también identificamos una balanza que funciona. El cuarto pesaje en la báscula A o en la báscula B (cualquiera que sea la báscula con la que C esté de acuerdo) hará el resto.
¡Esta solución me parece increíblemente hermosa!
Este método se puede generalizar para encontrar la moneda ligera entre 32x monedas en 3x + 1 pesaje con el juego de balanzas dado. Por lo tanto, necesita siete pesajes para 81 monedas. Para un mayor número de monedas (>~1,000), una solución aún más fuerte existe.
Puzzle 4
Tienes 16 monedas, ocho de las cuales son pesadas y del mismo peso. Los otros ocho son ligeros y del mismo peso. No sabes qué monedas son pesadas o ligeras. Las monedas parecen idénticas excepto por una que tiene marcas especiales. Con una buena balanza, ¿puedes determinar si la moneda especial es liviana o pesada en tres pesajes? ¿Cuál es el número máximo de monedas con las que puede comenzar y resolver con éxito este problema en cuatro pesajes?
A primera vista, este rompecabezas parece casi imposible de hacer en tres pesajes, como concluyó uno de nuestros lectores. Sin embargo, con algo de ingenio se puede hacer, y tanto Ted y Rainer en la primavera proporcionó soluciones correctas. Ted proporcionó algunos principios generales invaluables a los que vale la pena prestar atención.
Primero, hasta que obtenga un resultado desequilibrado de un pesaje, no tendrá suficiente información para determinar si la moneda especial es pesada o liviana. Así que tienes que intentar forzar un resultado desequilibrado.
En segundo lugar, si obtiene un resultado equilibrado (digamos que la moneda especial A equilibra la moneda B), puede combinar las monedas que están equilibradas y pesarlas contra dos monedas más, C y D. Si no están equilibradas, tiene la respuesta; de lo contrario, ahora ha duplicado la cantidad de monedas que son similares, lo que podría ayudarlo a obtener una respuesta desequilibrada en el próximo pesaje. También puedes realizar este proceso a la inversa con números de monedas que sean potencias de dos (4, 8, etc.) si tienes un resultado inicial desequilibrado como se ve en la siguiente solución.
A continuación se muestra todo el procedimiento que permite identificar el tipo de moneda especial A en todos los casos en tres pesajes. (B, C y D son tres monedas colocadas en el mismo lado que A al pesar 1 (W1); X e Y son las dos monedas que no se usan en W1).
Este rompecabezas fue inventado por el matemático ruso. Konstantin Knop, una autoridad mundial en acertijos para pesar monedas. Muchos de sus artículos están en ruso, pero puedes encontrar varios acertijos de monedas (entre otros acertijos interesantes) en el blog de su colaboradora Tanya Khovanova.
En cuanto a la generalización, les dejo a ustedes ver si este mismo método sirve para encontrar el tipo de una moneda especial entre 32 monedas, de las cuales 16 son pesadas y 16 livianas.
Puzzle 5
Tiene n monedas de aspecto idéntico, algunas de las cuales son falsas y más ligeras que otras. Todo lo que sabe es que hay al menos una moneda falsa y que hay más monedas normales que falsas. Tu trabajo es detectar todas las monedas falsas.
El hecho de que haya al menos una moneda ligera y que haya más monedas normales que ligeras hace que este rompecabezas sea menos complejo de lo que parece, al menos para números pequeños. Veamos el número de pesajes de una a ocho monedas.
Para una y dos monedas, no puede haber monedas ligeras según la segunda condición, por lo que no se requieren pesajes.
Tres monedas: Solo una moneda ligera. Se requiere un pesaje por rompecabezas 1.
Cuatro monedas: Solo una moneda ligera. Se requiere un pesaje adicional, por lo que w = 2.
Cinco monedas: De una a dos monedas ligeras. Este es el primer caso interesante. La pregunta es: ¿Debemos pesar una moneda contra una, o dos monedas contra dos?
Si sopesamos uno contra uno, entonces podemos tener:
- Dos pesajes desequilibrados: Dos monedas descubiertas; hemos terminado.
- Un pesaje equilibrado de dos: Las monedas equilibradas tienen que ser normales, por lo que la última moneda necesita otro pesaje, w = 3.
- Dos pesajes equilibrados: En el tercer pesaje, pese una moneda de cada pesaje anterior contra otra. Si están balanceadas, las cuatro son normales y la moneda 5 es la ligera. Hemos terminado; w = 3 de nuevo. Si están desequilibradas, hemos encontrado las dos monedas ligeras, y hemos terminado en tres pesajes.
Si, en cambio, pesamos dos contra dos, todavía necesitamos tres pesajes, porque tenemos que distinguir entre las posibilidades de que las monedas puedan ser diferentes o similares en cualquier lado. Los pesajes que utilizan pequeñas cantidades de monedas agrupadas no parecen tener ninguna ventaja sobre los pesajes con monedas individuales.
Esto se confirma para:
Seis monedas: una o dos monedas ligeras; w = 4.
Siete monedas: de una a tres monedas ligeras; w = 5.
Ocho monedas: De una a tres monedas ligeras; w = 6. Esta solución tiene una estructura simple:
- Primero haga cuatro pesajes de una moneda contra la siguiente. Todas las monedas son usadas.
- En el peor de los casos: los cuatro pesajes están equilibrados (hay dos monedas ligeras que se equilibran entre sí).
- Siguientes dos pesajes: Pesar una moneda de peso 1 contra una moneda de peso 2; Del mismo modo, pese una moneda de peso 3 contra una moneda de peso 4.
- Uno de estos pesajes será desequilibrado, identificando las dos monedas ligeras. Terminamos en seis pesajes.
Lo sentimos, nuestra secuencia de 0, 0, 1, 2, 3, 4, 5, 6 ciertamente no es lo suficientemente interesante como para enviarla al Enciclopedia en línea de secuencias de enteros!
As Jonas Tøgersen Kjellstadli señalado, la solución parece ser w = n − 2 para números pequeños, pero no hemos probado que esto no cambie para números más grandes. En algún n, el uso de varios pesajes de monedas podría comenzar a funcionar mejor, o más pesajes que n − 2 pueden ser necesarios. Simplemente podemos generalizar la solución para ocho monedas a todas las potencias de 2, dando n − 2 como límite superior para el número de pesajes para todas las potencias de 2.
Mark Pearson discutió la similitud de este problema con los códigos de corrección de errores y sugirió usar un enfoque de teoría de la información basado en la cantidad de resultados posibles. Usando tal enfoque, Mike Roberts publicado un límite inferior para el caso más general, que Rainer en la primavera derivó una aproximación para. Rainer también publicó un límite superior de un artículo publicado, pero señaló que los límites no son nítidos para bajos n y, por lo tanto, no es útil para los números pequeños que hemos considerado anteriormente. Por lo tanto, para siete monedas, los límites citados dan un rango de 4 a 16, entre el cual se encuentra nuestra respuesta, 5. J. Payette da referencias matemáticas adicionales y límites para todos los acertijos.
Gracias a todos aquellos que participaron. El premio Insights de este mes se otorga conjuntamente a Ted y Rainer aus dem Spring. ¡Felicidades!
Nos vemos la próxima vez para nuevos Insights.
