Rompecabezas de cuerdas quemadas

Rompecabezas matemático

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

1. Al encender un extremo (línea roja) de una cuerda (línea marrón), ésta se quema en 60 s.
2. Al encender ambos extremos se quema en 30 segundos.
3. La solución estándar con dos cuerdas, inicialmente la primera con ambos extremos encendidos y la segunda con uno solo. Al quemarse la primera cuerda se enciende el segundo extremo de la segunda cuerda (flecha azul), quemándose en un total de 45 s.
4. Una solución alternativa con la segunda cuerda apagada inicialmente. La primera cuerda que se quema provoca la iluminación de ambos extremos y de un punto aleatorio en la segunda cuerda. Cada vez que se quema un segmento, 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 rompecabezas de quema de cuerdas son una clase de rompecabezas matemático en el que se dan trozos de cuerda, cordón de mecha o cordón de zapato que arden durante un tiempo determinado y cerillas para encenderlos, y se deben usar para medir una cantidad de tiempo no unitaria. Los números fusibles se definen como las cantidades de tiempo que se pueden medir de esta manera.

Además de tener interés recreativo, estos rompecabezas 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 estudiantes de matemáticas de secundaria. ^[2]

Ejemplo

Una versión común y sencilla de este problema consiste en medir un tiempo de 45 segundos utilizando sólo dos mechas que arden durante un minuto cada una. Las hipótesis del problema suelen especificarse de forma que se evite medir 3/4 de la longitud de una mecha y quemarla de punta a punta, por ejemplo, indicando que las mechas arden de forma 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 de la primera mecha y ambos extremos de la segunda.
• Una vez que se haya quemado la segunda mecha, habrán transcurrido 30 segundos y todavía le quedarán 30 segundos de combustión a la primera. Encienda el otro extremo de la primera mecha.
• Una vez que se quema el primer fusible, habrán transcurrido 45 segundos.

Son posibles muchas otras variaciones, en algunos casos utilizando mechas que arden durante distintos periodos de tiempo entre sí. ^[5]

Números fusibles

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

En las versiones comunes del problema, cada mecha dura una unidad de tiempo, y las únicas operaciones utilizadas o permitidas en la solución son encender uno o ambos extremos de una mecha en tiempos conocidos, determinados ya sea como el inicio de la solución o como el tiempo en que se quema otra mecha. Si solo se enciende un extremo de una mecha en el tiempo , se quemará en el tiempo . Si ambos extremos de una mecha se encienden en los tiempos y , se quemará en el tiempo , porque una parte de se quema a la velocidad original, y la parte restante de se quema al doble de la velocidad original, por lo tanto, la mecha se quema a ${\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 fusible si es posible utilizar fusibles de unidad de tiempo para medir unidades de tiempo utilizando únicamente estas operaciones. Por ejemplo, según la solución del problema de ejemplo, es un número fusible. ^[7] ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle {\tfrac {3}{4}}}$

Se puede suponer sin pérdida de generalidad que toda mecha se enciende por ambos extremos, sustituyendo una mecha que se enciende sólo por un extremo a la vez por dos mechas, la primera encendida por ambos extremos a la vez y la segunda encendida por ambos extremos a la vez cuando la primera mecha se funde. De esta manera, 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 que . ^[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 uno elige una secuencia decreciente de números fusibles, la secuencia siempre debe ser finita. Entre los conjuntos bien ordenados, su ordenación puede clasificarse 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 único número fusible más pequeño entre los números fusibles mayor que ; tiene la forma para algún . ^[7] Este número crece muy rápidamente como una función de , tan rápidamente que para es (en la notación de flecha hacia arriba de Knuth para números grandes) ya mayor que . ^[8] La existencia de este número , para cada , 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 una mecha

Si las reglas de los acertijos de encendido de mechas se interpretan de modo que permitan 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 se enciende una mecha 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 cuando uno o dos de los puntos encendidos actuales se queman), entonces arderá durante 1/3 de una unidad de tiempo en lugar de una unidad completa. Al representar una cantidad dada de tiempo como una suma de fracciones unitarias y quemar sucesivamente mechas con múltiples puntos encendidos de modo que duren cada cantidad de fracción unitaria de tiempo, es posible medir cualquier número racional de unidades de tiempo. Sin embargo, mantener la cantidad deseada de llamas encendidas, incluso en una sola mecha, puede requerir una cantidad infinita 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 los 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 mechas (expresadas en notación O mayúscula ). ^[9] Una conjetura no demostrada 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 rompecabezas titulado Shoelace Clock Puzzles , creado por Dick Hess para una conferencia de Gathering 4 Gardner en 1998 , Hess atribuye al estadístico de Harvard Carl Morris como su fuente original para estos rompecabezas. ^[4]

Véase también

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

Referencias

1. Mongan, John; Kindler, Noah Suojanen; Giguère, Eric (2012), "Fusibles encendidos", Entrevistas de programación expuestas: secretos para conseguir su próximo trabajo (3.ª ed.), John Wiley & Sons, pág. 234, ISBN 978-1-118-28720-0
2. Brumbaugh, Douglas K. (2013), Enseñanza de las matemáticas en la escuela secundaria , Routledge, págs. 191, 309, ISBN 978-1-136-75622-1
3. Haselbauer, Nathan (2020), Rompecabezas de 60 segundos sin lápiz: breves acertijos que te harán pensar, 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 de zapatos", All-Star Mathlete Puzzles , Libros oficiales de rompecabezas de Mensa, pág. 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.), "Secuencia A188545", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
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, MR  0043117