Uno de nuestros lectores, Nicolas Audet, me llamó la atención sobre el encantador rompecabezas de esta semana. Nicolas dice que se usó como cerebro avance para una entrevista de trabajo en finanzas. Tengo que entregárselo a Wall Street en este caso: es un pequeño y encantador rompecabezas. Gracias por compartiendo, Nicolás!
Esta es una gran oportunidad para recordarte que si conoces un rompecabezas interesante, original o no , envíalo a mi manera y Puede aparecer aquí. ¿No estás seguro de si tu rompecabezas es apropiado para esta serie? Pruébame y te lo haré saber. ¿Puedes enviarme un mensaje en Twitter? @JackPMurtagh o envíeme un correo electrónico a [email protected]
¿Te perdiste el rompecabezas de la semana pasada? Compruébalo aquí, y encuentre su solución al final del artículo de hoy. Tenga cuidado de no leer demasiado adelante si no ha resuelto el último ¡semana todavía!
Rompecabezas #18 El Largo Pasillo
Hay un pasillo con 100 puertas etiquetadas 1, 2, 3, etc. hasta 100 en orden. Al principio, todas las las puertas están cerradas. Por alternar una puerta, me refiero a cambiar su posición (es decir, abrirla si está cerrada y cerrarla si está abierta). Camine por el pasillo y alterne cada puerta (en este caso, abriéndolas todas). Luego, una segunda persona atraviesa y alterna cada segunda puerta (puertas 2, 4, 6, etc.) Luego, una tercera persona alterna cada tercera puerta (3, 6, 9, etc.) Esto continúa hasta que la centésima persona solo activa la centésima puerta. ¿Qué puertas están abiertas al final?
Por supuesto, podrías resolver esto forzando una simulación del pasillo y simplemente observando qué puertas terminan abiertas. sería mucho más satisfactorio pensar en el problema y descubrir la razón que una puerta termina abierta o cerrada.
Regresaremos el próximo lunes con la solución y un nuevo rompecabezas.
Solución al rompecabezas #17: Envenenamiento de zombis
La semana pasada, tú sacrificó a los no-muertos para salvar a tu clan de la sed. Para identificar el barril envenenado entre 1000 en un día, sorprendentemente, solo necesitas 10 zombis. Alimentarás a los zombis con gotas de agua de varios barriles y llevarás un registro de qué barriles alimentas a qué zombis. La idea clave es para asignar a cada barril un grupo único de zombis para probarlo. Para tener una idea de cómo funciona esto, imaginemos que solo tenía cuatro barriles 1, 2, 3, 4 y dos zombis A y B. No alimentamos a ningún zombi del barril 1 ; alimentamos el barril 2 al zombi A solamente; el barril 3 al zombi B solamente; y el barril 4 a ambos zombis. Luego observamos quién muere. Si ninguno muere, entonces el barril 1 es el culpable. Si sólo muere A, el barril 2 es el culpable, y así El subconjunto de zombis que muere es una huella digital única ligada a un barril específico.
Observe que dos zombis no serían suficientes si tuviéramos cinco barriles, porque sólo hay cuatro subconjuntos únicos que se pueden formar a partir de dos zombis. Para ampliar el método, la pregunta es: ¿cuántos subgrupos únicos puedes formar a partir de 10 zombis? La respuesta es 210, o 1.024, más que suficiente para probar los 1.000 barriles. Si 210 es nuevo para tí, nuevamente piensa en menos zombis para la intuición. Con solo un zombi, hay dos posibles grupos (2 = 21), es decir, el propio zombi y ningún zombi en absoluto. Con dos zombis, vimos que obtenemos cuatro posibles subconjuntos (4 = 22). Cada zombi tiene dos estados posibles: en el grupo o no en el grupo, por lo que cada zombi adicional duplica el número de posibles grupos que podemos hacer.
La solución tal como está escrita funciona. Pero si quieres una forma sistemática e ingeniosa de cómo asignar realmente un grupo único de zombis a cada uno barril, puedes usar números binarios.
Numere los barriles de 0 a 999 y luego convierta cada número de barril en binario. Los 1 en la representación binaria de cada número de barril Nos dirá qué zombis alimentarnos de ese barril, y los 0 nos dirán qué zombis saltarnos para ese barril. Por ejemplo, 771 en binario es 1100000011. Corresponde esta secuencia de 10 dígitos a los 10 zombis. Alineando a los zombis en una fila, alimentaremos el barril 771 a los dos primeros y solo a los dos últimos (correspondientes a los de la representación binaria de 771) . Si, por ejemplo, sólo el 3er y 5º zombis de la izquierda mueren, entonces sabemos que el barril 0010100000 = 160 es el culpable.
Gritar a Eugenio por detectar la solución del número binario y explicarla bien.
Solución al rompecabezas #17b
Tener dos días para realizar las pruebas aumenta la complejidad. ¡Para encontrar el barril contaminado entre los 2000, solo necesitas siete zombis! Tomaremos prestado nuestro truco de números binarios del primer rompecabezas. Sin embargo, esta vez, por cada barril, cada zombi tiene tres Posibles acciones: no beber de él, beber de él el día 1 o beber de él el día 2. Entonces, Asigne a cada barril una etiqueta única de 7 dígitos compuesta por 0, 1 y 2. Nuevamente, imagine que tenemos dos zombis A y B. . Cuando sólo teníamos un día para realizar las pruebas, solo podíamos manejar cuatro barriles con dos zombis. Con dos días, poder probar nueve. Aquí están nuestras etiquetas de nueve barriles:
00, 01, 02, 10, 11, 12, 20, 21, 22
El Zombi A beberá según los dígitos situados más a la izquierda, lo que significa que no beberá nada de los primeros tres barriles, sino que beberá. de los siguientes tres el día 1 y los últimos tres el día 2. Zombi B beberá de acuerdo con los dígitos más a la derecha. Nota ese zombi A podría morir después del día 1 y nunca llegar al día 2. ¡Pero esto está bien! Porque si A muere el día 1, entonces sabemos que sólo los barriles 10, 11 y 12 podrían ser los culpables (A no bebió de los barriles con 0 o 2 el día 1). Así que ya no necesitamos probar los barriles de los que A era responsable el día 2. Si B nunca muere, entonces 10 es el culpable, si B muere después del día 1, entonces 11 es el culpable, y si B muere después del día 2, entonces el 12 es el culpable.
Este fenómeno aumenta. Si el enésimo zombi muere después del día 1, significa que el enésimo dígito de la etiqueta del barril envenenado a1.Si el enésimo dígito del zombi muere después del día 2, entonces el enésimo dígito es un 2. Si el enésimo zombi nunca muere , el enésimo dígito es un 0. Al observar qué zombis mueren en qué días, podemos reconstruir la etiqueta.
Nuevamente, esto se reduce a la pregunta: ¿cuántas etiquetas únicas de 7 dígitos (correspondientes a siete zombis) compuestas de 0, 1 y 2? ¿podemos hacer? Estos se llaman ternario números porque usan tres dígitos diferentes (0, 1 y 2), así como los números binarios usan dos (0 y 1). son 37 = 2187 etiquetas de 7 dígitos, más que suficientes para probar 2000 barriles.
Eugenio También resolvió la parte b de una manera instructiva, sin usar el método de los números ternarios y descubriendo inadvertidamente esta clara identidad combinatoria.
