enigme du tunnel

[invited2566f1a]

Bonjour


Voici une énigme dont je connais la réponse empirique.
Par contre comment mettre en équation ce problème si c'est possible?????

Une famille de 4 personnes doit traverser un tunnel. Chacun en fonction de
son âge met un temps différent à traverser :

le grand-père met 5h
le père met 4h
le fils met 2h
le petit fils met 1h

Sachant qu'ils n'ont qu'une seule lampe de poche qui a une autonomie de 12h
et qu'ils ne peuvent se déplacer qu'à 2, quelle sera la combinaison à
utiliser pour que toute la famille ait traversé le tunnel en 12h ?
A noter : Quand 2 personnes sont ensemble, on ne compte que le temps le plus long bien sûr, et une personne à le droit de rebrousser chemin complètement pour aller en chercher une autre.

Merci
-----

[Deedee81]

Salut,

Voici une énigme dont je connais la réponse empirique.
Par contre comment mettre en équation ce problème si c'est possible?????

"En équations", je ne sais pas. Mais tu peux aborder ça par la théorie des graphes. La réponse revient à rechercher le chemin (pondéré) le plus court entre deux sommets donnés.

[invitea3eb043e]

Au pifomètre, on voit que si on fait partir successivement le grand-père et le petit fils, qui revient puis refait le chemin avec le père, etc.. on n'y arrive pas en moins de 13 heures.
On peut faire partir ensemble :
1 le fils et le petit-fils : 2 heures
2 le fils revient : 2 heures
3 le grand père et le père ensemble : 5 heures
4 le petit fils revient : 1 heure
5 le fils et le petit fils ensemble : 2 heures
Total : 2 + 2 +5 +1 + 2 = 12 heures et ça colle !

Mettre en équation, je ne vois pas trop.

[invited2566f1a]

Salut,



"En équations", je ne sais pas. Mais tu peux aborder ça par la théorie des graphes. La réponse revient à rechercher le chemin (pondéré) le plus court entre deux sommets donnés.

Pourriez-vous m'expliquer comment vous faites avec cette théorie que je ne connais pas mais que je vais découvrir par ailleurs


merci

[A voir en vidéo sur Futura]

[invitec7217a00]

Pour le résoudre par la théorie des graphes il te faudra 1 sommet apr différent état du système.
Ici il faudra donc sommets.
En effet, si tu décides que le sommet correspond à ce qui se trouve de l'autre côté du tunnel, tu devras avoir toutes les possibilités de ce qui peut s'y trouver, parmi le petit-fils, le fils, le père, le grand-père, et la torche (-2 car on ne peut pas avoir la torche seule d'un côté ni de l'autre)
Une fois que tu as ces sommets, tu les relie par des arêtes pondérées (par exemple l'arête entre le sommet fils-petitFils-torche et le sommet fils a pour valeur 1 car cela signifie que le petit-fils est parti seul ramener la torche)
Une fois que tu as placé toutes les arêtes tu pourras chercher un plus court chemin qui va de l'état vide à l'état où tout le monde est là (par l'algorithme de Dijkstra par exemple).
Une fois la solution obtenue tu n'as plus qu'à regarder le chemin de sommets parcouru pour savoir dans quel ordre faire passer la famille.

[invited2566f1a]

Pour le résoudre par la théorie des graphes il te faudra 1 sommet apr différent état du système.
Ici il faudra donc sommets.
En effet, si tu décides que le sommet correspond à ce qui se trouve de l'autre côté du tunnel, tu devras avoir toutes les possibilités de ce qui peut s'y trouver, parmi le petit-fils, le fils, le père, le grand-père, et la torche (-2 car on ne peut pas avoir la torche seule d'un côté ni de l'autre)
Une fois que tu as ces sommets, tu les relie par des arêtes pondérées (par exemple l'arête entre le sommet fils-petitFils-torche et le sommet fils a pour valeur 1 car cela signifie que le petit-fils est parti seul ramener la torche)
Une fois que tu as placé toutes les arêtes tu pourras chercher un plus court chemin qui va de l'état vide à l'état où tout le monde est là (par l'algorithme de Dijkstra par exemple).
Une fois la solution obtenue tu n'as plus qu'à regarder le chemin de sommets parcouru pour savoir dans quel ordre faire passer la famille.

pour moi qui ne connais pas cette théorie c'est très abstrait est-il possible que tu ailles plus dans le détail avec un schéma par exemple?

[invitea3eb043e]

Ce n'est pas une mauvaise idée de mettre en oeuvre la théorie des graphes mais dans ce cas on voit assez bien qu'il ne faut pas faire voyager séparément le grand-père et le père car cela prend 9 heures plus les retours de torche. D'où l'idée de les faire voyager ensemble après avoir pris la précaution d'envoyer des émissaires rapides pour rapporter la torche, d'où la solution proposée.

[invitec7217a00]

Oui on peut le résoudre par la méthode des graphes, mais c'est un algorithme et non une équations qui donnera la solution

pour le schéma (incomplet, mais pour te montrer le principe) :