diumenge, 27 de març del 2011

Problemes per passar un pont (II)

En una entrada anterior, Problemes per passar un pont (I), ja vam exposar el problema de quatre persones per passar d'una riba a l'altra riba d'un riu en la versió del matemàtic i divulgador argentí Adrián Paenza. En podem trobar d'altres versions, més o menys literàries o divertides, que no en canvien el fons, però són interessants o, si més no, curioses de conèixer.

En una versió de 2005, anterior a l'edició del llibre de Paenza, les quatre persones es diuen Pepe, Pablo, Felipe i Juan (feu clic a Cuatro amigos y un puente per veure'n la versió). Juan té la cama enguixada per justificar que tarda deu minuts per completar el recorregut i, per fer més assequible el problema, primer se'ns demana de quina manera poden passar el pont en dinou minuts.

Una de les variacions més estranyes, no sabem si forma part d'alguna campanya "humanitària" o crematística, hi fa participar els membres del grup de rock U2 (la podeu veure, entre d'altres llocs, a DivulgaMAT i a MathNerds). El redactat que apareix a DivulgaMAT és el següent:


El grupo U2 (DivulgaMAT)

"El grupo U2 ofrece un concierto que comenzará en 17 minutos pero los miembros del grupo deben cruzar un puente para llegar al lugar del concierto. Los cuatro componentes están en el mismo lado del puente. Es de noche. Sólo hay una linterna. Sólo pueden cruzar el puente un máximo de dos personas a la vez. Siempre que se cruce el puente debe llevarse la linterna para ver el camino. La linterna no puede lanzarse al otro lado ni alumbrar desde lejos. Cada miembro de la banda puede caminar a distinta velocidad. Cuando vayan dos juntos, la velocidad que lleven será la del más lento. Sabiendo que Bono tarda 1 minuto en cruzar, Edge tarda 2 minutos en cruzar, Adam tarda 5 minutos en cruzar y Larry tarda 10 minutos en cruzar, ¿cómo conseguirán llegar a tiempo al concierto?"



Si heu anat consultant els enllaços que hem donat, heu pogut llegir diverses vegades la solució al problema. Per als més mandrosos o per als encuriosits que volen llegir com la dóna Adrián Paenza en el seu llibre Matemática... ¿estás ahí? Episodio 3,14, la teniu a continuació en la seva versió original en castellà (recordem que Mujer 1 tarda un minut per passar el pont; Mujer 2, dos minuts; Mujer 3, cinc minuts i Mujer 4, deu minuts):

Solució del problema de passar un pont
(+/- Mostra/Oculta)

Solución al problema de las cuatro mujeres y el puente
Primer viaje: van las mujeres 1 y 2. En total usaron 2 minutos.
Segundo viaje: vuelve la mujer 2 con la linterna. Pasaron 4
minutos.
Tercer viaje: van las mujeres 3 y 4. Ellas tardan 10 minutos, más
los 4 que se habían usado antes, suman 14.
Cuarto viaje: vuelve la mujer 1 con la linterna (que había quedado
en la otra orilla luego del primer viaje). Total consumido: 15
minutos.
Quinto (y último) viaje: van las mujeres 1 y 2. Tardan 2 minutos
en este viaje, y en total, 17 minutos.
MORALEJA: no interesa si a usted se le ocurrió la solución o la leyó.
No importa. Lo que sí interesa es que descubra por qué le costó trabajo.
Piense: ¿usted no intentó todas las veces que las mujeres que tardan
más (5 y 10 minutos) vayan juntas de una orilla a la otra? Casi
seguro que sí. Pero, ¿dónde estuvo la diferencia? Es que en la solución
se advierte que una de las dos mujeres que tardan menos (las
de 1 y 2 minutos) ¡estaba ya esperando en la otra orilla para traer la
linterna de vuelta! De esa forma, uno ahorra minutos y no necesita
usar más ni a la de 5 ni a la de 10 minutos.
Y ésa es la clave. Haber hecho viajar a las de 1 y 2 minutos primero,
para que una de las dos (no importa cuál) se quede allá para
traer la linterna cuando hayan llegado las de 5 y 10 minutos. La manera
distinta de pensar el problema pasó por ahí.
Pero claro, como en la vida, ahora que uno sabe la solución, todo
es más fácil.

En la primera entrada dedicada a aquest enunciat ja vam discutir amb un comentarista el "caràcter matemàtic" o no del problema. Si voleu llegir uns comentaris assenyats sobre com arribem a la solució i la dificultat, diguem-ne "extramatemàtica", d'arribar-hi, feu clic a Solución del acertijo de las mujeres y el puente. Hi trobareu també una referència a com solucionar-lo per "força bruta" o, per a no ofendre els matemàtics discrets, per combinatòria.

4 comentaris:

  1. (1+2)+2+(10+5)+1+(1+2) també pot ser
    (1+2)+1+(10+5)+2+(1+2).
    Es pot resoldre a "lo burro" que es el camí més curt o amb taules dicotòmiques o sigui que es pot informatitzar i generalitzar-ho per a casos molt més complexes.
    Tota la tecnologia de les aplicaciones GPS es fonamenten en aquest tipus de càlcul o sigui que el problema no es tan trivial !!!!

    Especialistes en el tema

    http://soa.iti.es/

    ResponElimina
  2. Com que veig que la meva manera d'entendre el problema és diferent de la dels srs. Paenza i Bilinkis –suposo que, quien calla otorga, també deu ser-ho de la del sr. Montasell– us l'explico:
    L'única dada important que l'enunciat no diu explicitament (més aviat l'amaga amb la claror del fanal) és la quantitat total mínima de viatges a través del pont que cal fer. Ateses les regles de joc i el nombre de jugadors (jugadores!) és fàcil concloure que han de ser cinc. Ja està; la resta és absolutament trivial: si les durades dels viatges només poden ser de 10, 5, 2 o 1 minuts només hi ha una manera de sumar cinc d'aquest valors que donin 17, a saber: 10 + 2 + 2 + 2 + 1 (cal tenir en compte que les regles de joc "malmeten" la commutativitat d'aquesta suma i obliguen a descartar certes combinacions).
    ¿Puc demanar explicacions al sr. Frederic? No he entés això del GPS, però sembla molt interessant.

    ResponElimina
  3. Si haig de triar una notació per tal de donar la solució del problema, em quedo amb la d'En Frederic. És molt entenedora, encara que no és gens rigorosa des del punt de vista matemàtic. Ho analitzo tot seguit:

    (1+2)+2+(10+5)+1+(1+2)

    En l'expressió anterior s'utilitza el signe "més" amb dos significats diferents segons estigui dins o fora dels parèntesis. És millor indicar-ho:

    màx{1,2} + 2 + màx{10,5} + 1 + màx{1,2}

    On "màx" vol dir "valor màxim del conjunt" i el signe + és la suma aritmètica habitual sense la propietat commutativa.

    El Sr. Rovira abusa dels refranys amb això de suposar que quién calla otorga perquè també pot ser que qui calla no hagi entès res, no es digni contestar o com deia el filòsof Groucho Marx: Més val estar callat i semblar ximple que parlar i aclarir el dubte o... No sé quina combinació d'aquests factors ha fet que no comentés el seu apunt de solució que ja apareixia en una entrada anterior. La seva notació

    10 + 2 + 2 + 2 + 1

    i el fet de comentar que el mínim són cinc viatges pot ser una bona indicació per trobar la solució, però no és la solució! Efectivament la no commutativitat fa que el 10, precisament el 10, estigui on no ha d'estar i que la "suma" només l'entengui qui ja ha trobat la solució. De la resta del procés diu que és trivial o evident, que són paraules perilloses i relatives (més d'un professor universitari les utilitza per demostrar la seva suficiència mentre els pobres estudiants, que no han entès res, es graten el cap). Espero que el fet de "parlar" no sigui una prova a favor de la meva ximpleria.

    Finalment, agrair al company Frederic que ens doni a conèixer SOA (Sistemas de Optimización Aplicada) i ens demostri, als qui només ens dediquem a l'optimització teòrica, que hi ha vida allà fora. Si a més aclareix això dels GPS...

    ResponElimina
  4. Estic subscrit a un newsletter sobre temes geogràfics "Mundogeo" i a partir d'aqui he estat buscant aplicacions d'optimització en temes geogràfics i de "arcgis" que és el sw que normalment s'utilitza en temes de cartografia i si hi esteu interessats en el següent enllaç hi ha molta informació
    http://www.gabrielortiz.com/

    ResponElimina