Répondre à la discussion
Page 2 sur 2 PremièrePremière 2
Affichage des résultats 31 à 60 sur 60

Enigme : Le plus court chemin de la fortune



  1. #31
    saroumane

    Re : Enigme : Le plus court chemin de la fortune


    ------

    Salut

    Alors en partant du coin en bas à droite
    tu remontes au coin en haut à droite
    puis tu prend la diagonale vers le coin en bas à gauche
    tu retournes en bas à droite
    tu prends la diagonale vers le haut à gauche
    tu dessines le chapeau
    tu vas vers la gauche
    puis tu redescend

    OUF ! normalement c'est bon!

    Alors?

    -----

  2. Publicité
  3. #32
    KarmaStuff

    Re : Enigme : Le plus court chemin de la fortune

    En fait, il existe plusieurs méthodes, et la tienne fonctionne très bien...

    Moi je connais celle-ci :

    Connais-toi toi-même et l'Univers n'aura plus aucun secret pour toi...

  4. #33
    Coincoin

    Re : Enigme : Le plus court chemin de la fortune

    Salut,
    Pour l'énigme de la maison, il faut reprendre un argument qu'avait avancé Euler pour résoudre l'énigme des ponts de Königsberg : si on compte le nombre de chemins arrivant sur un point donné, on se rend compte qu'il ne peut être impair que pour le point d'arrivée et pour le point de départ (car sinon pour tout chemin entrant il y a un chemin sortant).
    Pour cette énigme, on voit donc qu'il faut partir du coin en bas à gauche ou à droite pour arriver à l'autre. Quand on sait ça, ça devient dur de se coincer...
    Encore une victoire de Canard !

  5. #34
    invité576543
    Invité

    Re : Enigme : Le plus court chemin de la fortune

    Bonjour,

    Un peu classique... Compliquons la question: combien de solutions différentes pour aller sous les conditions données du coin bas gauche au coin bas droite?

    Cordialement,

  6. #35
    invité576543
    Invité

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par mmy
    Bcombien de solutions différentes pour aller sous les conditions données du coin bas gauche au coin bas droite?
    Bonjour,

    Ma réponse est 16, ... à discuter!

    Cordialement,

  7. #36
    yat

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par mmy
    Ma réponse est 16, ... à discuter!
    Il y a un piège ? Tu as éliminé les symétriques, ou quelque chose de ce genre ?
    Sinon... au moins 26, sans même ouvrir un compilateur.

  8. Publicité
  9. #37
    invité576543
    Invité

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par yat
    Il y a un piège ? Tu as éliminé les symétriques, ou quelque chose de ce genre ?
    Sinon... au moins 26, sans même ouvrir un compilateur.
    Non, erreur de décompte... (Suis en réunion à l'étranger pour une fois... je fais de mémoire sur un bout de papier lors des pauses...). J'en ai 28 en fait!

    Cordialement,

    Note : Ma manière de compter donne 8 solutions, les autres s'en déduisent par des inversions de cycles...

  10. #38
    invité576543
    Invité

    Re : Enigme : Le plus court chemin de la fortune

    Comme je me demande si j'en ai pas raté (et je fait tout à la main, moyens limités!), je recopie mon brouillon. La notation est ABCDE en tournant dans le sens des aiguilles d'une montre. Faut aller de A à E. Entre parenthèses veut dire qu'on peut lire le cycle dans les deux sens.

    4 solutions (AEDA)(BCDB)E

    4 solution (AE(DCBD)A)BE

    2 solutions (AEDBA)DCBE

    2 solutions (AEDCBA)DBE

    4 solutions (ADBA)(EBCDE)

    4 solutions (ADCBA)(EDBE)

    4 solutions (A(DBCD)EBA)E

    4 solutions (ADE(BCDB)A)E

    Total 28

  11. #39
    Argyre

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par yat
    Il y a un piège ? Tu as éliminé les symétriques, ou quelque chose de ce genre ?
    Sinon... au moins 26, sans même ouvrir un compilateur.
    Bon, si on note A et E les sommets qui ont 3 branches et B, C, D ceux du haut, avec C le sommet isolé ayant seulement 2 branches, voici les solutions trouvées par ordinateur après une bonne heure de programmation et en commençant systématiquement par A et en finissant par E. Il y en a 44 ! Si on ajoute à ces chemins le symétrique qui commence de E et finit en A, ça en fait 2 fois plus, c'est à dire 88.
    Voici les solutions trouvées par ordinateur (sous réserve qu'il n'y ait pas eu de bug vicieux, faudrait vérifier, mais a priori, ça semble correct) :
    AEBCDBADE
    ABDAEBCDE
    AEDABDCBE
    AEBADCBDE
    AEBDABCDE
    ADBAEBCDE
    AEDCBDABE
    ADCBAEBDE
    ADEBDCBAE
    AEDABCDBE
    AEDBADCBE
    AEDCBADBE
    ADBEDCBAE
    ABCDEADBE
    ADBCDEABE
    ABDEADCBE
    ADCBAEDBE
    ADCBDEABE
    ABCDAEDBE
    AEDBCDABE
    ABEADBCDE
    ABCDBEDAE
    ADCBDEBAE
    ADBEABCDE
    ABDCBEADE
    ABDCBEDAE
    ADEBCDBAE
    ADCBEDBAE
    ABEDBCDAE
    ADEABCDBE
    ABEDCBDAE
    ABEADCBDE
    ABDEBCDAE
    ADBCDEBAE
    ADCBEABDE
    AEBDCBADE
    ABCDBEADE
    ADBAEDCBE
    ABCDEBDAE
    AEBCDABDE
    ADEABDCBE
    ABCDAEBDE
    AEBADBCDE
    ABDAEDCBE

    Connaissant le résultat (44), à vous de trouver maintenant une méthode de calcul plus subtile ... si elle existe.

  12. #40
    yat

    Re : Enigme : Le plus court chemin de la fortune

    J'ai utilisé une méthode bien plus basique, je trouve 44 solutions ( )
    J'ai ensuite coché pour chacune de tes lignes les solutions qui correspondent (mais là j'ai pu en zapper... je me suis arrété pour chaque ligne au nombre que tu indiquais). J'aurais bien aimé te donner les lignes manquantes, mais ta méthode me donne bien du fil à retordre...

    Par exemple, une de mes solutions supplémentaiers est ABCDBEADE... je ne trouve rien qui correspond dans tes solutions, mais je suis bien embété : est-ce que je dois l'écrire (A(BCDB)EA)DE ou A(BCDB)(EADE) ou encore ABC(DBEAD)E...

    La première se décline en
    -ABCDBEADE
    -ABDCBEADE
    -AEBCDBADE
    -AEBDCBADE

    La deuxième en
    -ABCDBEADE
    -ABDCBEADE
    -ABCDBEDAE
    -ABDCBEDAE

    Et la troisième en
    -ABCDBEADE
    -ABCDAEBDE

    Là ou je perds complêtement les pédales, c'est que les troisième et quatrième déclinaisons de la deuxième écriture entrent dans ta dernière ligne...

    EDIT : largement grillé par Agyre, je confirme donc ses solutions (et non l'inverse )

  13. #41
    Argyre

    Re : Enigme : Le plus court chemin de la fortune

    Pour infos, l'algorithme que j'ai utilisé est générique et consiste à effectuer une recherche de solutions dans l'espace d'états selon la stratégie du meilleur d'abord.
    L'algorithme de recherche (Dijkstra) était déjà implémenté, je n'avais qu'à définir les paramètres du problème, c'est à dire uniquement 5 fonctions + les structures de données définissant un état et aussi l'affichage.
    Ceci explique sans doute le peu de temps qu'il m'a fallu pour écrire le programme ...

  14. #42
    Argyre

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par yat
    Par exemple, une de mes solutions supplémentaiers est ABCDBEADE... je ne trouve rien qui correspond dans tes solutions,
    Si c'est la 37ème.

  15. Publicité
  16. #43
    yat

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par Argyre
    Si c'est la 37ème.
    Nan, nan ! Je répondais à mmy, ta réponse à toi est arrivée pendant que je tapais. Comme je l'ai dit, je confirme ta réponse.

  17. #44
    Argyre

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par Argyre
    Si c'est la 37ème.
    Ok, compris.

  18. #45
    invité576543
    Invité

    Re : Enigme : Le plus court chemin de la fortune

    J'avais fait ça il y a des années... Dur de tout retrouver, il me semble...

    Ma notation:

    Le premier cycle est toujours celui de A. Il y a en nécessairement un!

    Ensuite il ne dit plus y avoir d'ambiguité. S'il y en a, on prend le premier cycle possible...

    Donc (A(BCDB)EA)DE est l'un des compléments à ma liste. Et je vois pourquoi il manque...

    Sinon, je recommande ma notation, ça réduit quand même pas mal...

    Cordialement,

  19. #46
    yat

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par mmy
    Sinon, je recommande ma notation, ça réduit quand même pas mal...
    C'est sur que ça doit être vachement moins laborieux que mes petits dessins sous paintshop. Par contre là ou la récursivité était évidente (trois directions de départ, copier, coller deux fois, je prolonge chaque exemplaire de chaque trait dans les trois directions possibles, et ainsi de suite), pour ta méthode je ne vois vraiment pas de technique systématique pour énumérer les solutions... Comment tu as fait ?

  20. #47
    invité576543
    Invité

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par yat
    C'est sur que ça doit être vachement moins laborieux que mes petits dessins sous paintshop. Par contre là ou la récursivité était évidente (trois directions de départ, copier, coller deux fois, je prolonge chaque exemplaire de chaque trait dans les trois directions possibles, et ainsi de suite), pour ta méthode je ne vois vraiment pas de technique systématique pour énumérer les solutions... Comment tu as fait ?
    En gros cela consiste à extraire les cycles. Il y a nécessairement un cycle au début, puisqu'il faudra passer par A une deuxième fois. On commence par énumérer les cycles sans cycle interne. Il n'y en pas 36, et un simple parcours d'arbre les donne: AEDA, AEDBA, AEDCBA, ADBA, ADEBA et ADCBA. Ensuite pour chaque cas, on regarde s'il reste des cycles possibles. S'il n'y en a pas (comme en démarrant par AECDBA), c'est fini. S'il y en a on regarde toutes les combinaisons de cycles possibles et on fait tous les remplacements, par exemple si le cycle BDCB a été extrait, on peut soit remplacer B par BDCB ou D par DCBD.

    Exemple (ce sera plus clair): début (AEDA) il reste un ensemble d'arètes qui contient un seul cycle (BDCB). Je l'enlève, il reste le "squelette sans cycle" ABE, d'où la solution incomplète (AEDA)BE (en remplaçant A par son cycle). Et de là deux solutions en injectant le cycle restant, soit (AE(DCBD)A)BE en remplaçant D, soit (AEDA)(BCDB)E en remplaçant B. En gros un squelette et n cycles, ça fait 2n solutions (chaque cycle peut tourner dans un sens ou dans l'autre).

    Il faut juste faire attention de ne pas avoir deux fois la même solution vue avec des cycles distincts. Pour celui de A pas de pb, on commence par lui. Ensuite cela dépend de ce qui reste, mais pour le cas à 5 points, c'est facile...

    A tête reposée (je sors d'une réunion), je referai ma liste en rajoutant ce que j'ai oublié dans mon premier décompte, sous forme squelette/cycle...

    Michel

    Note: L'une de mes hobbys est la participation aux trucs de la FFJM, soit directement, soit en entraînant mes enfants (Championnat de la FFJM, Rallye mathématique, Euromath, ...). Je ne suis pas très intéressé par les solutions par programme, mais plutôt par les petits trucs qui permettent de résoudre "à la main", comme faire des dénombrements à la main, comme exposé ci-dessus, par exemple! Les programmes sont utiles pour vérifier que ça marche...

  21. #48
    invité576543
    Invité

    Re : Enigme : Le plus court chemin de la fortune

    Bonjour,

    Je ne sais pas si ma méthode est vraiment moins laborieuse, je me suis pas mal emmélé les pinceaux hier... Bon, l'esprit plus frais, et en suivant rigoureusement la méthode voilà ce que ça donne:

    Toute solution commence par un cycle de A à A. Les cycles possibles sans cycles internes sont ABCDA, ABCDEA, ABDA, ABDEA, ABEA, ABEDA, ADBEA, ADCBEA et ADEA ainsi que leurs inverses. (J'en avais oublié hier )

    D'où

    (ABCDA)(EDBE), AE 4x2 solutions
    (ABCDA)(EBDE)
    (ABC(DBED)A)E non compté, cycle B avant, = (A(BCDB)EDA)E
    (A(BEDB)CDA)E

    (ABCDEA), ADBE 2 solutions
    (ABCDEA)DBE

    (ABDA)(EBCDE), AE 4x2 solutions
    (ABDA)(EBCDE)
    (AB(DEBCD)A)E cycle B avant
    (A(BCDEB)DA)E

    (ABDEA), ADCBE 2 solutions
    (ABDEA)DCBE

    (ABEA)(BCDB), ADE 4x2 solutions
    (ABEA)(DBCD)E
    (A(BCDB)EA)DE

    (ABEDA)(BCDB), AE 4x1 solutions
    (A(BCDB)EDA)E
    (ABE(DBCD)A)E cycle B avant

    (ADBEA), ABCDE 2 solutions
    (ADBEA)BCDE

    (ADCBEA), ABDE 2 solutions
    (ADCBEA)BDE

    (ADEA)(BCDB), ABE 4x2 solutions
    (ADEA)(BCDB)E
    (A(DBCD)EA)BE


    Total : 44 solutions

    La liste est, regroup&#233;e diff&#233;remment pour v&#233;rifier la sym&#233;trie BCD <->BD

    (ABCDA)(EBDE)
    (ABDA)(EBCDE)

    (A(BEDB)CDA)E
    (A(BCDEB)DA)E

    (ABCDEA)DBE
    (ABDEA)DCBE

    (ADBEA)BCDE
    (ADCBEA)BDE

    (ADEA)(BCDB)E
    (A(DBCD)EA)BE
    (ABEA)(DBCD)E
    (A(BCDB)EA)DE
    (A(BCDB)EDA)E

    Cordialement,

  22. Publicité
  23. #49
    Argyre

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par mmy
    Toute solution commence par un cycle de A &#224; A. Les cycles possibles sans cycles internes sont ABCDA, ABCDEA, ABDA, ABDEA, ABEA, ABEDA, ADBEA, ADCBEA et ADEA ainsi que leurs inverses. (J'en avais oubli&#233; hier )
    J'ai plus simple !
    Il est en effet plus facile d'envisager AB, AD, AEB et AED puis pour chacun de ces triplets d'envisager les cycles &#224; partir de B et D.
    B et D &#233;tant parfaitement sym&#233;trique, l'&#233;tude de AD peut &#234;tre &#233;vit&#233;e, il suffira de multiplier par 2 le nombre de solutions trouv&#233;es avec AB.
    Idem, l'&#233;tude de AED peut &#234;tre &#233;vit&#233;e, il suffira de multiplier par 2 le nombre de solutions trouv&#233;es avec AEB.
    Reste donc &#224; &#233;tudier les cycles &#224; partir de AB et les cycles &#224; partir de AEB. Logiquement, on ne doit trouver que 22 solutions ... et les voici :

    Par AB :
    A(BCDB)(EDAE) en voil&#224; 4
    A(BEDB)CDAE 2 de plus
    A(BEDCB)DAE 2 de plus
    AB(DAED)CBE encore 2
    AB(DCBED)AE encore 2
    ABE(DCBD)AE encore 2

    Par AEB :
    AE(BADB)CDE en voil&#224; 2
    AE(BCDB)ADE 2 de plus
    AEB(DCBAD)E 2 de plus
    AEBA(DCBD)E et les 2 derni&#232;res

  24. #50
    Argyre

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par Argyre
    Par AB :
    A(BCDB)(EDAE) en voilà 4
    A(BEDB)CDAE 2 de plus
    A(BEDCB)DAE 2 de plus
    AB(DAED)CBE encore 2
    AB(DCBED)AE encore 2
    ABE(DCBD)AE encore 2

    Par AEB :
    AE(BADB)CDE en voilà 2
    AE(BCDB)ADE 2 de plus
    AEB(DCBAD)E 2 de plus
    AEBA(DCBD)E et les 2 dernières
    Petite erreur de ma part, faut que je vérifie ...

  25. #51
    invité576543
    Invité

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par Argyre
    Par AB :
    A(BCDB)(EDAE) en voil&#224; 4
    A(BEDB)CDAE 2 de plus
    A(BEDCB)DAE 2 de plus
    AB(DAED)CBE encore 2

    AB(DCBED)AE encore 2
    ABE(DCBD)AE encore 2

    Par AEB :
    AE(BADB)CDE en voil&#224; 2
    AE(BCDB)ADE 2 de plus
    AEB(DCBAD)E 2 de plus
    AEBA(DCBD)E et les 2 derni&#232;res
    Bonjour,

    Il y a s&#251;rement quelque chose &#224; faire avec la sym&#233;trie B/D (la m&#233;thode que j'ai utilis&#233;e est g&#233;n&#233;rique, c'est un vieux machin pour moi que j'avais regard&#233; pour un autre probl&#232;me de chemin hamiltonien).

    Mais dans ce que tu fais, je ne comprends pas par exemple pourquoi dans les deux en rouge l'un est trait&#233; comme commen&#231;ant par A et l'autre par AB... En fait, il sont au moins un cas commun, non?

    Amicalement,

    Michel

  26. #52
    Argyre

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par Argyre
    Petite erreur de ma part, faut que je v&#233;rifie ...
    J'ai tout m&#233;lang&#233;, alors reprenons :
    Il y a obligatoirement un cycle en B qu'il faut identifier, donc voil&#224; ce que &#231;a donne :
    Par AB :
    A(BEDB)CDAE en voil&#224; 2 (cycle de 4)
    A(BCDB)(EDAE) en voil&#224; 4 (2 cycles de 4)
    A(BCDEB)DAE 2 de plus (cycle de 5)
    A(BEADB)CDE 2 de plus (autre cycle de 5)
    A(BCDAEB)DE 2 de plus (cycle de 6)
    A(B(DEAD)CB)E 4 de plus (cycle de 7 avec 1 inclus)

    Pour AEB, c'est plus simple, il n'y a que 3 cycles possibles
    AE(BADB)CDE en voil&#224; 2 (cycle de 4)
    AE(BCDB)ADE 2 de plus (autre cycle de 4)
    AE(BCDAB)DE 2 de plus (seul cycle de 5)

  27. #53
    invité576543
    Invité

    Re : Enigme : Le plus court chemin de la fortune

    Ca a l'air bien! C'est effectivement plus simple comme ça!

    Michel

  28. #54
    Argyre

    Re : Enigme : Le plus court chemin de la fortune

    Optimisons encore un peu le raisonnement :
    Commen&#231;ons par AEB :
    AE(BADB)CDE en voil&#224; 2 (cycle de 4)
    AE(BCDB)ADE 2 de plus (autre cycle de 4)
    AE(BCDAB)DE 2 de plus (seul cycle de 5)

    Ces 6 solutions se retrouvent dans les solutions commen&#231;ant par AB et incluant E dans la boucle, car D est un passage de boucle oblig&#233; et on peut aller en E de D et revenir en B de E. Pour AB, on n'&#233;tudiera donc pas les boucles contenant E de 5 et 6 sommets, sachant qu'il y aura 6 solutions &#233;galement.

    Reste donc pour AB :
    A(BEDB)CDAE en voil&#224; 2 (cycle de 4)
    A(BCDB)(EDAE) en voil&#224; 4 (2 cycles de 4)
    A(B(DEAD)CB)E 4 de plus (cycle de 7 avec 1 inclus)

    Bilan :
    (6*2 + 10)*2=44 solutions

  29. Publicité
  30. #55
    Grimbal

    Re : Enigme : Le plus court chemin de la fortune

    Ouaip. Une solution triviale en 31 pas et une solution moins intuitive en 30 pas.

    euh.. c'est la r&#233;ponse au probl&#232;me de la 1e page...
    Dernière modification par Grimbal ; 21/01/2006 à 13h34.

  31. #56
    Grimbal

    Re : Enigme : Le plus court chemin de la fortune

    Je sais que je vais embêter tout ceux qui essaient de faire un décompte manuel, mais on n'est pas obligé d'aller tout droit quand on arrive au milieu du X dans le carré. Si on note par X le centre du carré, on peut très bien faire:
    ABCDBXAEXDE

    J'arrive à 120 chemins.

  32. #57
    yat

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par Grimbal
    on n'est pas obligé d'aller tout droit quand on arrive au milieu du X dans le carré.
    Voilà une subtilité que personne n'avait relevé. En effet, si on suit l'énoncé tel qu'il est donné ici, ça me parait tout à fait juste.

  33. #58
    Loup_solitaire

    Re : Enigme : Le plus court chemin de la fortune

    $********$
    **********
    **********
    X*********
    **********
    **********
    **********
    **********
    $********$
    $********$

    Question simple :
    On dispose d'un tableau de 10 fois 10 cases.
    En partant de X, et en se déplaçant horizontalement ou verticalement mais pas en diagonal et de 1 case à la fois, combien de déplacements faut-il faire au minimum pour passer sur toutes les cases marquées avec un $.

    NB : Il n'y a pas de piège, l'énoncé est limpide ... mais il faut quand même réfléchir un peu pour trouver la solution optimale.[/QUOTE]
    ______________________________ _________________
    Je ne vois pas comment il y a tant de réponses à 31:
    A partir du X je remonte jusqu'au $ NO (Nord Ouest) = 3
    puis vers la droite (ou vers l'est) jusqu'au $ NE = 10
    ensuite jusqu'au $ SE et je croque au passage le $ S-1;E
    = 10
    je continue jusqu'au $ SO =10
    enfin je remonte au dernier $ juste au dessus, soit 1.
    Total: 3 + 10 + 10 + 10 + 1 = 34
    Quelqu'un ayant trouvé 31 (ou moins) pourrait il m'expliquer son chemin ?
    Loup très solitaire!

  34. #59
    matthias

    Re : Enigme : Le plus court chemin de la fortune

    Citation Envoyé par Loup_solitaire
    Total: 3 + 10 + 10 + 10 + 1 = 34
    Quelqu'un ayant trouvé 31 (ou moins) pourrait il m'expliquer son chemin ?
    Ca fait plutôt 3 + 9 + 9 + 9 + 1 = 31 (pour le chemin que tu indiques).
    Et il y a une solution en 30 tout est expliqué dans les messages précédents.

  35. #60
    Loup_solitaire

    Re : Enigme : Le plus court chemin de la fortune

    Autant pour moi

Page 2 sur 2 PremièrePremière 2

Discussions similaires

  1. Géodésique, le plus court ou le plus long chemin ?
    Par benjy_star dans le forum Physique
    Réponses: 11
    Dernier message: 18/04/2007, 23h44
  2. isolation de fortune...
    Par ben47 dans le forum Habitat bioclimatique, isolation et chauffage
    Réponses: 2
    Dernier message: 23/01/2007, 09h12
  3. électricité et chemin le plus court
    Par j.g dans le forum Physique
    Réponses: 8
    Dernier message: 16/10/2005, 11h08
  4. quelle est le plus court chemin?
    Par stephone dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 12/02/2005, 00h20