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?
En fait, il existe plusieurs méthodes, et la tienne fonctionne très bien...
Moi je connais celle-ci :
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 !
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,
Bonjour,Envoyé par mmy
Ma réponse est 16, ... à discuter!
Cordialement,
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!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.
Cordialement,
Note : Ma manière de compter donne 8 solutions, les autres s'en déduisent par des inversions de cycles...
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
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.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.
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.
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)
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 ...
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.
Ok, compris.
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,
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...
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ée différemment pour vérifier la symé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,
J'ai plus simple !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
Il est en effet plus facile d'envisager AB, AD, AEB et AED puis pour chacun de ces triplets d'envisager les cycles à partir de B et D.
B et D étant parfaitement symétrique, l'étude de AD peut être évitée, il suffira de multiplier par 2 le nombre de solutions trouvées avec AB.
Idem, l'étude de AED peut être évitée, il suffira de multiplier par 2 le nombre de solutions trouvées avec AEB.
Reste donc à étudier les cycles à partir de AB et les cycles à partir de AEB. Logiquement, on ne doit trouver que 22 solutions ... et les voici :
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 ...
Bonjour,
Il y a sûrement quelque chose à faire avec la symétrie B/D (la méthode que j'ai utilisée est générique, c'est un vieux machin pour moi que j'avais regardé pour un autre problè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é comme commençant par A et l'autre par AB... En fait, il sont au moins un cas commun, non?
Amicalement,
Michel
J'ai tout mélangé, alors reprenons :
Il y a obligatoirement un cycle en B qu'il faut identifier, donc voilà ce que ça donne :
Par AB :
A(BEDB)CDAE en voilà 2 (cycle de 4)
A(BCDB)(EDAE) en voilà 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à 2 (cycle de 4)
AE(BCDB)ADE 2 de plus (autre cycle de 4)
AE(BCDAB)DE 2 de plus (seul cycle de 5)
Ca a l'air bien! C'est effectivement plus simple comme ça!
Michel
Optimisons encore un peu le raisonnement :
Commençons par AEB :
AE(BADB)CDE en voilà 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çant par AB et incluant E dans la boucle, car D est un passage de boucle obligé et on peut aller en E de D et revenir en B de E. Pour AB, on n'étudiera donc pas les boucles contenant E de 5 et 6 sommets, sachant qu'il y aura 6 solutions également.
Reste donc pour AB :
A(BEDB)CDAE en voilà 2 (cycle de 4)
A(BCDB)(EDAE) en voilà 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
Ouaip. Une solution triviale en 31 pas et une solution moins intuitive en 30 pas.
euh.. c'est la réponse au problème de la 1e page...
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.
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.
$********$
**********
**********
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!
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.
Autant pour moi
