Rompecabezas de quema de cuerdas

rompecabezas matemático

Visualización del rompecabezas de la quema de cuerdas, el eje horizontal indica el tiempo transcurrido en segundos y el eje vertical indica el tiempo de combustión restante en una cuerda (no su longitud).

1. Al encender un extremo (línea roja) de una cuerda (línea marrón) se quema en 60 s.
2. Al encender ambos extremos se quema en 30 s.
3. La solución estándar con dos cuerdas, inicialmente la primera con ambos extremos iluminados y la segunda con solo uno. La primera cuerda que se quema activa el encendido del segundo extremo de la segunda cuerda (flecha azul), quemándola en un total de 45 s.
4. Una solución alternativa con la segunda cuerda inicialmente apagada. La primera cuerda que se quema activa ambos extremos y un punto aleatorio en la segunda cuerda. Cada vez que un segmento se quema, se enciende un punto aleatorio en la cuerda restante. En teoría, la segunda cuerda se quema en 15 s, lo que da un total de 45 s.

En matemáticas recreativas , los acertijos de quema de cuerdas son una clase de acertijo matemático en el que a uno se le dan trozos de cuerda, cordón fusible o cordón de zapato que se queman durante un período de tiempo determinado, y cerillas para prenderles fuego, y debe usarlos. medir una cantidad de tiempo no unitaria. Los números fusibles se definen como la cantidad de tiempo que se puede medir de esta manera.

Además de ser de interés recreativo, estos acertijos a veces se plantean en entrevistas de trabajo como una prueba de la capacidad de resolución de problemas de los candidatos, ^[1] y se han sugerido como actividad para estudiantes de matemáticas de secundaria. ^[2]

Ejemplo

Una versión común y simple de este problema pide medir un tiempo de 45 segundos usando solo dos fusibles que arden cada uno durante un minuto. Las suposiciones del problema generalmente se especifican de una manera que impide medir 3/4 de la longitud de un fusible y quemarlo de un extremo a otro, por ejemplo, afirmando que los fusibles se queman de manera desigual a lo largo de su longitud. ^{[1] [2] [3] [4]}

Una solución a este problema es realizar los siguientes pasos: ^[3]

• Encienda un extremo del primer fusible y ambos extremos del segundo fusible.
• Una vez que el segundo fusible se ha quemado, han transcurrido 30 segundos y quedan 30 segundos de tiempo de combustión del primer fusible. Enciende el otro extremo del primer fusible.
• Una vez que se quema el primer fusible, han transcurrido 45 segundos.

Son posibles muchas otras variaciones, en algunos casos utilizando fusibles que se queman durante períodos de tiempo diferentes entre sí. ^[5]

Números fusibles

Visualización de los números fusibles más pequeños mayores que 0, 1 y 2: 1/2, 11/8y 21/1024, respectivamente (negrita) ^[6]

En versiones comunes del problema, cada fusible dura una unidad de tiempo, y las únicas operaciones utilizadas o permitidas en la solución son encender uno o ambos extremos de un fusible en momentos conocidos, determinados como el inicio de la solución o como el momento en que se quema otro fusible. Si sólo se enciende un extremo de un fusible a la vez , se quemará al mismo tiempo . Si ambos extremos de un fusible se encienden a veces y , se quemará en el momento , porque una parte de se quema a la velocidad original y la parte restante se quema al doble de la velocidad original, por lo tanto, el fusible se quema a la velocidad original. ${\displaystyle x}$ ${\displaystyle x+1}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x+y+1)/2}$ ${\displaystyle y-x}$ ${\displaystyle 1-(y-x)}$

${\displaystyle x+(y-x)+[1-(y-x)]/2=(x+y+1)/2}$.

Un número es un número de fusible si es posible utilizar fusibles de unidad de tiempo para medir unidades de tiempo utilizando sólo estas operaciones. Por ejemplo, según la solución al problema de ejemplo, hay un número de fusible. ^[7] ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle {\tfrac {3}{4}}}$

Se puede suponer, sin pérdida de generalidad, que cada fusible está encendido en ambos extremos, reemplazando un fusible que está encendido solo en un extremo a la vez por dos fusibles, el primero encendido en ambos extremos al mismo tiempo y el segundo encendido en ambos extremos. en el momento en que se funde el primer fusible. De esta forma, los números fusibles se pueden definir como el conjunto de números que se pueden obtener a partir del número mediante la aplicación repetida de la operación , aplicada a pares que ya se han obtenido y para los cuales . ^[7] ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x+1/2}$ ${\displaystyle 0}$ ${\displaystyle x,y\mapsto (x+y+1)/2}$ ${\displaystyle x,y}$ ${\displaystyle |x-y|<1}$

Los números fusibles incluyen todos los números enteros no negativos y son un subconjunto bien ordenado de los números racionales diádicos , las fracciones cuyos denominadores son potencias de dos . Estar bien ordenado significa que, si se elige una secuencia decreciente de números fusibles, la secuencia siempre debe ser finita. Entre los conjuntos bien ordenados, su ordenación se puede clasificar como un número épsilon (un caso especial de los infinitos números ordinales ). Debido a que están bien ordenados, para cada número entero hay un número fusible único y más pequeño entre los números fusibles mayores que ; tiene la forma para algunos . ^[7] Este número crece muy rápidamente en función de , tan rápidamente que (en la notación de flecha hacia arriba de Knuth para números grandes) ya es mayor que . ^[8] La existencia de este número , para cada uno , no puede probarse en la aritmética de Peano . ^[7] ${\displaystyle \varepsilon _{0}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n+1/2^{k}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n=3}$ ${\displaystyle 2\uparrow ^{9}16}$ ${\displaystyle k}$ ${\displaystyle n}$

Encender más de dos puntos de un fusible.

Si se interpreta que las reglas de los rompecabezas de quema de mechas permiten que las mechas se enciendan en más puntos que sus extremos, se puede medir un conjunto mayor de cantidades de tiempo. Por ejemplo, si una mecha se enciende de tal manera que, mientras arde, siempre tiene tres extremos encendidos (por ejemplo, encendiendo un punto en el medio y un extremo, y luego encendiendo otro extremo u otro punto en el medio siempre que uno o dos de los puntos encendidos actuales se quemen), entonces arderá durante 1/3 de una unidad de tiempo en lugar de una unidad completa. Al representar una cantidad de tiempo determinada como una suma de fracciones unitarias y quemar sucesivamente mechas con múltiples puntos encendidos para que duren cada fracción unitaria de tiempo, es posible medir cualquier número racional de unidades de tiempo. Sin embargo, mantener encendida la cantidad deseada de llamas, incluso en un solo fusible, puede requerir una cantidad infinita de pasos para volver a encenderla. ^[4]

El problema de representar un número racional dado como suma de fracciones unitarias está estrechamente relacionado con la construcción de fracciones egipcias , sumas de fracciones unitarias distintas; sin embargo, para problemas de quema de mechas no es necesario que las fracciones sean diferentes entre sí. Utilizando métodos conocidos para fracciones egipcias, se puede demostrar que medir una cantidad fraccionaria de tiempo , con , solo necesita fusibles (expresados ​​en notación O grande ). ^[9] Una conjetura no probada de Paul Erdős sobre las fracciones egipcias sugiere que menos mechas, , siempre pueden ser suficientes. ^[10] ${\displaystyle x/y}$ ${\displaystyle x<y}$ ${\displaystyle O({\sqrt {\log y}})}$ ${\displaystyle O(\log \log y)}$

Historia

En un folleto sobre estos acertijos titulado Shoelace Clock Puzzles , creado por Dick Hess para una conferencia Gathering 4 Gardner de 1998 , Hess acredita al estadístico de Harvard Carl Morris como su fuente original para estos acertijos. ^[4]

Ver también

• Rompecabezas de vertido de agua , otra clase de rompecabezas que involucran la combinación de medidas.

Referencias

1. Mongan, John; Kindler, Noah Suojanen; Giguère, Eric (2012), "Fusibles ardientes", Entrevistas de programación expuestas: secretos para conseguir su próximo trabajo (3ª ed.), John Wiley & Sons, p. 234, ISBN 978-1-118-28720-0
2. Brumbaugh, Douglas K. (2013), Enseñanza de matemáticas en la escuela secundaria , Routledge, págs.191, 309, ISBN 978-1-136-75622-1
3. Haselbauer, Nathan (2020), Acertijos sin lápiz de 60 segundos: breves rascadores de cabeza desde lo fácil hasta lo casi imposible , Fair Winds Press, págs.77, 121, ISBN 978-1-63159-927-9
4. Winkler, Peter (2004), "Usos de fusibles", Acertijos matemáticos: una colección para conocedores , AK Peters, págs. 2, 6, ISBN 1-56881-201-9
5. Hess, Dick (2009), "Relojes con cordones", All-Star Mathlete Puzzles , Libros oficiales de rompecabezas de Mensa, p. 9, ISBN 978-1-4027-5528-6
6. Jeff Erickson, Números fusibles
7. Erickson, Jeff; Nivasch, Gabriel; Xu, Junyan (junio de 2021), "Números fusibles y aritmética de Peano", Actas del 36.º Simposio anual ACM/IEEE sobre lógica en informática (LICS 2021) , IEEE, págs. 1-13, arXiv : 2003.14342 , doi : 10.1109 /lics52264.2021.9470703
8. Sloane, N. J. A. (ed.), "Sequence A188545", La enciclopedia en línea de secuencias enteras , Fundación OEIS
9. Vose, M. (1985), "Fracciones egipcias", Boletín de la Sociedad Matemática de Londres , 17 : 21, doi :10.1112/blms/17.1.21, MR  0766441
10. Erdős, Pál (1950), "Az 1 x 1 + 1 x 2 + ⋯ + 1 x n = a b {\displaystyle \textstyle {\frac {1}{x_{1}}}+{\frac {1}{ x_{2}}}+\cdots +{\frac {1}{x_{n}}}={\frac {a}{b}}} egyenlet egész számú megoldásairól" [Sobre una ecuación diofántica] (PDF) , Matematikai Lapok (en húngaro), 1 : 192–210, SEÑOR  0043117