Diferencia entre revisiones de «Acertijo del puente y la antorcha»

Contenido eliminado Contenido añadido

En renglón

Revisión actual - 05:20 10 feb 2024

El problema del puente y la antorcha (también conocido como El Tren de Medianoche^[1] y El cruce Peligroso^[2]) es un acertijo lógico de la categoría de acertijos de cruzar el río, en el que un número de personajes debe cruzar un río cumpliendo una serie de restricciones.^[3]

Argumento

Cuatro individuos llegan a un río de noche. Hay un puente estrecho, pero este solo soporta a dos personas a la vez. Los individuos tienen una antorcha y, debido a que es de noche, deben utilizarla cuando cruzan el puente; por lo tanto, si cruzan dos personas, uno debe volver atrás llevando la antorcha para que puedan cruzar los demás. El individuo A puede cruzar el puente en un minuto, el individuo B en dos minutos, el individuo C en cinco minutos, y el individuo D en ocho minutos. Cuando dos individuos cruzan el puente juntos, tardan lo que tarda el más lento de ellos. El problema es: ¿pueden cruzar todos el puente en quince minutos o menos?^[2]

Solución

Una primera idea obvia es que el coste de la devolución de la antorcha a la gente que esperaba para cruzar es un costo inevitable que debe ser minimizado. Esta estrategia toma como portador de la antorcha al individuo A (el más rápido):^[4]

Tiempo Transcurrido	Lado de Partida	Acción	Lado de Llegada
0 minutos	A B C D
2 minutos	C D	A y B cruzan hacia adelante, toma 2 minutos	A B
3 minutos	A C D	A regresa, toma 1 minuto	B
8 minutos	D	A y C cruzan hacia adelante, toma 5 minutos	A B C
9 minutos	A D	A regresa, toma 1 minuto	B C
17 minutos		A y D cruzan hacia adelante, toma 8 minutos	A B C D

Esta estrategia no permite un cruce en quince minutos. Para encontrar la solución correcta, uno debe darse cuenta de que cruzar individualmente a las personas más lentas es una pérdida de tiempo que se puede ahorrar si cruzan ambas a la vez:^[4]

Tiempo Transcurrido	Lado de Partida	Acción	Lado de Llegada
0 minutos	A B C D
2 minutos	C D	A y B cruzan hacia adelante, toma 2 minutos	A B
3 minutos	A C D	A regresa, toma 1 minuto	B
11 minutos	A	C y D cruzan hacia adelante, toma 8 minutos	B C D
13 minutos	A B	B regresa, toma 2 minutos	C D
15 minutos		A y B cruzan hacia adelante, toma 2 minutos	A B C D

Una segunda solución es intercambiando a los portadores de la antorcha. Básicamente, los dos individuos más rápidos cruzan juntos en el primer y quinto viaje, los dos individuos más lentos cruzan juntos en el tercer viaje, y uno de los dos individuos más rápidos regresa en el segundo viaje, y el otro más rápido en el cuarto viaje.

Así, el tiempo mínimo para cuatro personas viene dado por las siguientes ecuaciones matemáticas: Cuando $A<B<C<D$ ,
$\min(B+A+C+A+D,B+A+D+B+B)$
$\min(2A+B+C+D,A+3B+D)$

Variaciones

Existen varias versiones, con variaciones como distintos nombres de los personajes o diferentes tiempos de cruce.^[5] En algunas versiones la antorcha puede caducar en cierto tiempo y así servir de tiempo límite. O puede ser una linterna con baterías y el límite de tiempo se corresponde con la energía remanente en las baterías de la linterna.^[6]^[7]

El acertijo es conocido por haber aparecido en 1981, en el libro Super Strategies For Puzzles and Games. En esta versión, A, B, C y D demoran 5, 10, 20, y 25 minutos respectivamente en cruzar, y el tiempo límite es 60 minutos.^[8]^[9] En todas estas variaciones, la estructura y la solución del rompecabezas siguen siendo los mismos.

El problema se ha analizado completamente mediante métodos de teoría de gráficos, en el caso de que haya un número arbitrario de personas con tiempos de cruce arbitrarios y también que la capacidad del puente siga siendo igual a dos personas.^[4]

Martin Erwig de la Oregon State University ha utilizado una variación del problema para defender la usabilidad del lenguaje de programación Haskell sobre Prolog para resolver problemas de búsqueda.^[10]

El rompecabezas también se menciona en el libro de Daniel Dennett From Bacteria to Bach and Back como su ejemplo favorito de una solución que es contraria a la intuición.

Véase también

Referencias

↑ «MURDEROUS MATHS BRAINBENDERS». Archivado desde el original el 6 de marzo de 2008. Consultado el 8 de febrero de 2008.
↑ ^a ^b Gleb Gribakin. «Some simple and not so simple maths problems». Consultado el 8 de febrero de 2008.
↑ Tricky Crossings Archivado el 20 de enero de 2008 en Wayback Machine., Ivars Peterson, Science News, 164, #24 (December 13, 2003); accessed on line February 7, 2008.
↑ ^a ^b ^c Rote, Günter (2002). «Crossing the bridge at night». Bulletin of the European Association for Theoretical Computer Science (en inglés) 78. pp. 241-246.
↑ «The Bridge Crossing Puzzle». Archivado desde el original el 31 de mayo de 2008.
↑ Juan Pablo Romero Aguirre (18 de marzo de 2011). «Acertijo. Cuatro personas necesitan cruzar por un puente colgante de noche para volver a su campamento.». http://www.jpromero.com/index.html. Consultado el 31 de agosto de 2017.
↑ Paenza, Adrián (19 de septiembre de 2007). «Problema de las cuatro mujeres y el puente». Página/12. p. Contratapa. Consultado el 31 de agosto de 2017.
↑ Torsten Sillke (septiembre de 2001). «Crossing the bridge in an hour». Consultado el 9 de febrero de 2008.
↑ Levmore, Saul X.; Cook, Elizabeth Early (1981). Super strategies for puzzles and games. Garden City, New York: Doubleday & Company. ISBN 0-385-17165-X.
↑ Erwig, Martin (2004). «Escape from Zurg» (en inglés). Journal of Functional Programming, Vol. 14, No. 3. pp. 253-261.

Enlaces externos

En inglés

Slides of the Capacity C Torch Problem [1]
Paper discussing the Capacity C Torch Problem [2]
Ted Ed Video and Exercise Based on Bridge and Torch Problem [3]
Paper discussing A Systematic Solution to the Bridge Riddle using Combinatorics [4]

Datos: Q4966324

[mm-1] «MURDEROUS MATHS BRAINBENDERS». Archivado desde el original el 6 de marzo de 2008. Consultado el 8 de febrero de 2008.

[webam-2] Gleb Gribakin. «Some simple and not so simple maths problems». Consultado el 8 de febrero de 2008.

[a-3] Tricky Crossings Archivado el 20 de enero de 2008 en Wayback Machine., Ivars Peterson, Science News, 164, #24 (December 13, 2003); accessed on line February 7, 2008.

[eatcs-4] Rote, Günter (2002). «Crossing the bridge at night». Bulletin of the European Association for Theoretical Computer Science (en inglés) 78. pp. 241-246.

[visi-5] «The Bridge Crossing Puzzle». Archivado desde el original el 31 de mayo de 2008.

[6] Juan Pablo Romero Aguirre (18 de marzo de 2011). «Acertijo. Cuatro personas necesitan cruzar por un puente colgante de noche para volver a su campamento.». http://www.jpromero.com/index.html. Consultado el 31 de agosto de 2017.

[7] Paenza, Adrián (19 de septiembre de 2007). «Problema de las cuatro mujeres y el puente». Página/12. p. Contratapa. Consultado el 31 de agosto de 2017.

[sillke-8] Torsten Sillke (septiembre de 2001). «Crossing the bridge in an hour». Consultado el 9 de febrero de 2008.

[9] Levmore, Saul X.; Cook, Elizabeth Early (1981). Super strategies for puzzles and games. Garden City, New York: Doubleday & Company. ISBN 0-385-17165-X.

[ezurg-10] Erwig, Martin (2004). «Escape from Zurg» (en inglés). Journal of Functional Programming, Vol. 14, No. 3. pp. 253-261.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Línea 1: / Línea 1: @@
+[[File:bridge_and_torch_problem.svg|thumb|upright=1.5]]
-El '''problema del puente y la antorcha''' (también conocido como ''El Tren de Medianoche'')<ref name="mm">{{cita web|título=MURDEROUS MATHS BRAINBENDERS|url=http://www.murderousmaths.co.uk/books/BKMMPxbb.htm|fechaacceso=8 de febrero de 2008|urlarchivo=https://web.archive.org/web/20080306104015/http://www.murderousmaths.co.uk/books/BKMMPxbb.htm|fechaarchivo=6 de marzo de 2008}}</ref> y ''El cruce Peligroso''<ref name="webam">{{cita web|título=Some simple and not so simple maths problems|autor=Gleb Gribakin|url=http://web.am.qub.ac.uk/users/g.gribakin/problems.html|fechaacceso=8 de febrero de 2008}}</ref>) es un [[acertijo lógico]] de la categoría de [[acertijos de cruzar el río]], en el que un número de [[Personaje|personajes]] debe cruzar un [[río]] cumpliendo una serie de restricciones.<ref name=a>[http://www.sciencenews.org/articles/20031213/mathtrek.asp Tricky Crossings], Ivars Peterson, ''Science News'', '''164''', #24 (December 13, 2003); accessed on line February 7, 2008.</ref>
+El '''problema del puente y la antorcha''' (también conocido como ''El Tren de Medianoche''<ref name="mm">{{cita web|título=MURDEROUS MATHS BRAINBENDERS|url=http://www.murderousmaths.co.uk/books/BKMMPxbb.htm|fechaacceso=8 de febrero de 2008|urlarchivo=https://web.archive.org/web/20080306104015/http://www.murderousmaths.co.uk/books/BKMMPxbb.htm|fechaarchivo=6 de marzo de 2008}}</ref> y ''El cruce Peligroso''<ref name="webam">{{cita web|título=Some simple and not so simple maths problems|autor=Gleb Gribakin|url=http://web.am.qub.ac.uk/users/g.gribakin/problems.html|fechaacceso=8 de febrero de 2008}}</ref>) es un [[acertijo lógico]] de la categoría de [[acertijos de cruzar el río]], en el que un número de [[personaje]]s debe cruzar un [[río]] cumpliendo una serie de restricciones.<ref name=a>[http://www.sciencenews.org/articles/20031213/mathtrek.asp Tricky Crossings] {{Wayback|url=http://www.sciencenews.org/articles/20031213/mathtrek.asp |date=20080120135128 }}, Ivars Peterson, ''Science News'', '''164''', #24 (December 13, 2003); accessed on line February 7, 2008.</ref>
 == Argumento ==
-Cuatro individuos llegan a un río en la [[noche]]. Hay un [[puente]] estrecho, pero este sólo soporta a dos personas a la vez. Los individuos tienen una [[antorcha]], y debido a que es de noche, deben utilizar la antorcha cuando cruzan el puente, por lo tanto, si cruzan dos personas, uno debe volver atrás llevando la antorcha para que puedan cruzar los demás. El individuo A puede cruzar el puente en un minuto, el individuo B en dos minutos, el individuo C en cinco minutos, y el individuo D en ocho minutos. Cuando dos individuos cruzan el puente juntos, tardan lo que tarda el más lento de ellos. El problema es: ¿Pueden cruzar todos el puente en quince minutos o menos?.<ref name=webam />
+Cuatro individuos llegan a un río de [[noche]]. Hay un [[puente]] estrecho, pero este solo soporta a dos personas a la vez. Los individuos tienen una [[antorcha]] y, debido a que es de noche, deben utilizarla cuando cruzan el puente; por lo tanto, si cruzan dos personas, uno debe volver atrás llevando la antorcha para que puedan cruzar los demás. El individuo A puede cruzar el puente en un minuto, el individuo B en dos minutos, el individuo C en cinco minutos, y el individuo D en ocho minutos. Cuando dos individuos cruzan el puente juntos, tardan lo que tarda el más lento de ellos. El problema es: ¿pueden cruzar todos el puente en quince minutos o menos?<ref name=webam />
 == Solución ==
-Una primera idea obvia es que el coste de la devolución de la antorcha a la gente que esperaba para cruzar es un costo inevitable que debe ser minimizado. Esta estrategia toma como portador de la antorcha a el individuo A (el más rápido):<ref name=eatcs />
+Una primera idea obvia es que el coste de la devolución de la antorcha a la gente que esperaba para cruzar es un costo inevitable que debe ser minimizado. Esta estrategia toma como portador de la antorcha al individuo A (el más rápido):<ref name=eatcs>{{Cita noticia | apellido = Rote | nombre = Günter | año = 2002 | título = Crossing the bridge at night | periódico = Bulletin of the European Association for Theoretical Computer Science | volumen = 78 | páginas = 241–246 |url=http://page.mi.fu-berlin.de/%7Erote/Papers/pdf/Crossing+the+bridge+at+night.pdf | postscript = <!--None-->|idioma=inglés}}</ref>
 {| class="wikitable"
@@ Línea 45: / Línea 46: @@
 |}
-Esta estrategia no permite un cruce en quince minutos. Para encontrar la solución correcta, uno debe darse cuenta que cruzar individualmente a las personas más lentas es una pérdida de tiempo que se puede ahorrar si cruzan ambas a la vez:<ref name=eatcs />
+Esta estrategia no permite un cruce en quince minutos. Para encontrar la solución correcta, uno debe darse cuenta de que cruzar individualmente a las personas más lentas es una pérdida de tiempo que se puede ahorrar si cruzan ambas a la vez:<ref name=eatcs />
 {| class="wikitable"
@@ Línea 86: / Línea 87: @@
 Una segunda solución es intercambiando a los portadores de la antorcha. Básicamente, los dos individuos más rápidos cruzan juntos en el primer y quinto viaje, los dos individuos más lentos cruzan juntos en el tercer viaje, y uno de los dos individuos más rápidos regresa en el segundo viaje, y el otro más rápido en el cuarto viaje.
+Así, el tiempo mínimo para cuatro personas viene dado por las siguientes ecuaciones matemáticas:
+Cuando <math>A < B < C < D</math>, <br>
+<math>\min(B + A + C + A + D, B + A + D + B + B)</math> <br>
+<math>\min(2A + B + C + D,A + 3B + D)</math>
 == Variaciones ==
 Existen varias versiones, con variaciones como distintos nombres de los personajes o diferentes tiempos de cruce.<ref name="visi">{{cita web|título=The Bridge Crossing Puzzle|url=http://www.visi.com/cgi-bin/cgiwrap/~heyyousir/bridge.cgi|urlarchivo=https://web.archive.org/web/20080531013610/http://www.visi.com/cgi-bin/cgiwrap/~heyyousir/bridge.cgi|fechaarchivo=31 de mayo de 2008}}</ref>
-En algunas versiones la antorcha puede caducar en cierto tiempo y así servir de tiempo límite. O puede ser una [[Linterna eléctrica|linterna]] con [[Batería eléctrica|baterías]] y el límite de tiempo se corresponde con la energía remanente en las baterías de la linterna.<ref>{{Cita web|url=http://www.jpromero.com/2011/03/acertijo-cuatro-personas-necesitan.html|título=Acertijo. Cuatro personas necesitan cruzar por un puente colgante de noche para volver a su campamento.|fechaacceso=31 de agosto de 2017|autor=Juan Pablo Romero Aguirre|fecha=18 de marzo de 2011|sitioweb=http://www.jpromero.com/index.html|editorial=|idioma=Español}}</ref>  <ref>{{Cita noticia|apellidos=Paenza|nombre=Adrián|título=Problema de las cuatro mujeres y el puente|url=https://www.pagina12.com.ar/diario/contratapa/13-91615-2007-09-19.html|fecha=19 de septiembre de 2007|fechaacceso=31 de agosto de 2017|periódico=Página/12|página=Contratapa}}</ref>
+En algunas versiones la antorcha puede caducar en cierto tiempo y así servir de tiempo límite. O puede ser una [[Linterna eléctrica|linterna]] con [[Batería eléctrica|baterías]] y el límite de tiempo se corresponde con la energía remanente en las baterías de la linterna.<ref>{{Cita web|url=http://www.jpromero.com/2011/03/acertijo-cuatro-personas-necesitan.html|título=Acertijo. Cuatro personas necesitan cruzar por un puente colgante de noche para volver a su campamento.|fechaacceso=31 de agosto de 2017|autor=Juan Pablo Romero Aguirre|fecha=18 de marzo de 2011|sitioweb=http://www.jpromero.com/index.html|editorial=|idioma=Español}}</ref><ref>{{Cita noticia|apellidos=Paenza|nombre=Adrián|título=Problema de las cuatro mujeres y el puente|url=https://www.pagina12.com.ar/diario/contratapa/13-91615-2007-09-19.html|fecha=19 de septiembre de 2007|fechaacceso=31 de agosto de 2017|periódico=Página/12|página=Contratapa}}</ref>
-El acertijo es conocido por haber aparecido en 1981, en el libro ''Super Strategies For Puzzles and Games''. En esta versión, A, B, C y D demoran 5, 10, 20, y 25 minutos respectivamente en cruzar, y el tiempo límite es 60 minutos.<ref name="sillke">{{cita web|url=http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/crossing-bridge|título=Crossing the bridge in an hour|autor=Torsten Sillke|fecha=septiembre de 2001|fechaacceso=9 de febrero de 2008}}</ref><ref>{{cita libro | last1 = Levmore | first1 = Saul X. | last2 = Cook | first2 = Elizabeth Early | título = Super strategies for puzzles and games | editorial = Doubleday & Company | place = Garden City, New York | año = 1981 | isbn = 0-385-17165-X | postscript = <!--None-->}}</ref> En todas estas variaciones, la estructura y la solución del rompecabezas siguen siendo los mismos.
+El acertijo es conocido por haber aparecido en 1981, en el libro ''Super Strategies For Puzzles and Games''. En esta versión, A, B, C y D demoran 5, 10, 20, y 25 minutos respectivamente en cruzar, y el tiempo límite es 60 minutos.<ref name="sillke">{{cita web|url=http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/crossing-bridge|título=Crossing the bridge in an hour|autor=Torsten Sillke|fecha=septiembre de 2001|fechaacceso=9 de febrero de 2008}}</ref><ref>{{cita libro | last1 = Levmore | first1 = Saul X. | last2 = Cook | first2 = Elizabeth Early | título = Super strategies for puzzles and games | editorial = Doubleday & Company | place = Garden City, New York | año = 1981 | isbn = 0-385-17165-X | postscript = <!--None--> | url = https://archive.org/details/superstrategiesf00levm }}</ref> En todas estas variaciones, la estructura y la solución del rompecabezas siguen siendo los mismos.
+El problema se ha analizado completamente mediante métodos de [[Teoría de grafos|teoría de gráficos]], en el caso de que haya un número arbitrario de personas con tiempos de cruce arbitrarios y también que la capacidad del puente siga siendo igual a dos personas.<ref name=eatcs/>
+Martin Erwig de la Oregon State University ha utilizado una variación del problema para defender la usabilidad del lenguaje de programación Haskell sobre Prolog para resolver [[problema de búsqueda|problemas de búsqueda]].<ref name=ezurg>{{Cita web | apellido = Erwig | nombre = Martin | título = Escape from Zurg | url=http://web.engr.oregonstate.edu/~erwig/papers/Zurg_JFP04.pdf | año = 2004 | editorial = Journal of Functional Programming, Vol. 14, No. 3| páginas = 253–261  | postscript = <!--None-->|idioma=inglés}}</ref>
+El rompecabezas también se menciona en el libro de Daniel Dennett ''[[From Bacteria to Bach and Back]]'' como su ejemplo favorito de una solución que es contraria a la intuición.
 == Véase también ==
-* [[Acertijo del lobo, la cabra y la col]]
+* [[Acertijo del lobo, la cabra y la col]].
+* [[Acertijo de los misioneros y los caníbales]].
-* [[:en:Missionaries and cannibals problem]]
 == Referencias ==
 {{listaref}}
+==Enlaces externos==
+=== En inglés ===
+* Slides of the Capacity C Torch Problem [https://web.archive.org/web/20110811160332/http://aps.cs.nott.ac.uk/wp-content/uploads/2008/05/capacity-c-torch-problem-aps-club.pdf]
+* Paper discussing the Capacity C Torch Problem [http://www.cs.nott.ac.uk/~rcb/MPC/GeneralTorchProblem.ps]
+* Ted Ed Video and Exercise Based on Bridge and Torch Problem [https://ed.ted.com/lessons/can-you-solve-the-bridge-riddle-alex-gendler]
+* Paper discussing A Systematic Solution to the Bridge Riddle using Combinatorics [https://doi.org/10.21256/zhaw-4057]
 {{DEFAULTSORT:Bridge And Torch Problem}}
+{{Control de autoridades}}
 [[Categoría:Optimización]]
 [[Categoría:Acertijos lógicos]]
+[[Categoría:Optimización combinatoria]]