Rompecabezas de cuerda ardiente

En matemáticas recreativas , los rompecabezas de quemar cuerdas son una clase de rompecabezas matemático en el que a uno se le dan trozos de cuerda, cordón de fusible o cordones de zapatos que se queman durante un período de tiempo determinado, y se combinan para prenderles fuego, y debe usarlos. para medir una cantidad de tiempo no unitaria. Los números de fusibles se definen como las cantidades de tiempo que se pueden medir de esta manera.

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

Ejemplo

Una versión común y simple de este problema requiere medir un tiempo de 45 segundos usando solo dos fusibles que se queman cada uno durante un minuto. Las suposiciones del problema generalmente se especifican de una manera que evita medir 3/4 de la longitud de un fusible y quemarlo de un extremo a otro, por ejemplo, indicando 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 fundido, han transcurrido 30 segundos y quedan 30 segundos de tiempo de combustión en el primer fusible. Encienda 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 diferentes períodos de tiempo entre sí. ^[5]

Números fusibles

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 tiempo que se quema otro fusible. Si solo se enciende un extremo de un fusible a la vez , se quemará en ese momento . Si ambos extremos de un fusible están encendidos a veces y , a veces se quemará . Un número es un número fusible si es posible usar fusibles de tiempo unitario para medir unidades de tiempo usando solo estas operaciones. Por ejemplo, por la solución del problema de ejemplo, es un número fusible. ^[6]${\displaystyle x}$${\displaystyle x+1}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x+y+1)/2}$${\displaystyle x}$${\displaystyle x}$${\displaystyle {\tfrac {3}{4}}}$

Se puede suponer sin pérdida de generalidad que cada fusible se enciende en ambos extremos, reemplazando un fusible que se enciende solo en un extremo a la vez por dos fusibles, el primero encendido en ambos extremos a la vez y el segundo encendido en ambos extremos. en el momento en que se quema el primer fusible. De esta forma, los números fusibles se pueden definir como el conjunto de números que se pueden obtener del número mediante la aplicación repetida de la operación , aplicados a pares que ya se han obtenido y para los cuales . ^[6]${\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 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 orden se puede clasificar como un número épsilon (un caso especial de los números ordinales infinitos ). Debido a que están bien ordenados, para cada entero hay un número fusible más pequeño único entre los números fusibles mayores que ; tiene la forma para algunos . ^[6]${\displaystyle \varepsilon _{0}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n+1/2^{k}}$${\displaystyle k}$Este número crece muy rápidamente en función de , tan rápidamente que para él (en la notación de flecha hacia arriba de Knuth para números grandes) ya es mayor que . ^[7] La existencia de este número , para cada uno , no se puede probar en la aritmética de Peano . ^[6]${\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 fusibles permiten que los fusibles se enciendan en más puntos que en sus extremos, se puede medir una mayor cantidad de tiempo. Por ejemplo, si una mecha se enciende de tal manera que, mientras se quema, 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 iluminados actuales se quemen), se quemará durante 1/3 de una unidad de tiempo en lugar de una unidad completa. Al representar una cantidad determinada de tiempo como una suma de fracciones unitarias , y quemar sucesivamente fusibles con múltiples puntos encendidos para que duren por cada fracción unitaria de tiempo, es posible medir cualquier número racionalde unidades de tiempo. Sin embargo, mantener el número deseado de llamas encendidas, incluso con una sola mecha, puede requerir un número infinito de pasos de reencendido. ^[4]

El problema de representar un número racional dado como una 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 fusibles, no es necesario que las fracciones sean diferentes entre sí. Utilizando métodos conocidos para las fracciones egipcias, se puede probar que medir una fracción de tiempo , con , solo necesita fusibles (expresados ​​en notación O grande ). ^[8] Una conjetura no probada de Paul Erdős sobre las fracciones egipcias sugiere que menos fusibles,, siempre pueden ser suficientes. ^[9]${\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 atribuye al estadístico de Harvard Carl Morris la fuente original de estos acertijos. ^[4]

Ver también

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

Referencias

1. Mongano, Juan; 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 las matemáticas de la escuela secundaria , Routledge, págs.  191 , 309 , ISBN 978-1-136-75622-1
3. Haselbauer, Nathan (2020), Rompecabezas de 60 segundos Rompecabezas sin lápiz: Rascadores cortos de lo fácil a casi imposible , Fair Winds Press,  págs.77 , 121 , ISBN 978-1-63159-927-9
4. Winkler, Peter (2004), "Usos de los fusibles", Rompecabezas matemáticos: Colección de un conocedor , AK Peters, págs. 2, 6, ISBN 1-56881-201-9
5. Hess, Dick (2009), "Relojes de cordones" , Rompecabezas de Mathlete All-Star , Libros oficiales de Mensa Puzzle, p. 9, ISBN 978-1-4027-5528-6
6. 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
7. Sloane, N. J. A. (ed.), "Secuencia A188545" , La enciclopedia en línea de secuencias de enteros , Fundación OEIS
8. Vose, M. (1985), "fracciones egipcias", Boletín de la Sociedad Matemática de Londres , 17 : 21, doi : 10.1112 / BLM / 17.01.21 , MR 0766441 
9. Erdős, Pál (1950), "Az egyenlet egész számú megoldásairól" [En una ecuación diofántica] (PDF) , Matematikai Lapok (en húngaro), 1 : 192-210, MR 0043117 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}}}