Combien de trajets ?

Olympiades mathématiques, énigmes et défis
Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 19:39

Combien de trajets ?

par chan79 » 21 Fév 2017, 20:30

Voici une énigme dont je n'ai pas la réponse.
On dispose d'une grille 8 x8 et deux points A et B situés à l'intérieur comme sur le dessin.
Combien y a-t-il de trajets reliant A à B, de longueur 80, sachant que le trajet doit suivre les pointillés (bords de la grille compris) et ne doit pas passer deux fois par un même point ?
Par exemple:
Image



L.A.
Membre Irrationnel
Messages: 1709
Enregistré le: 09 Aoû 2008, 16:21

Re: Combien de trajets ?

par L.A. » 22 Fév 2017, 00:53

Bonsoir,

simple suggestion : compter les mots de 80 lettres sur un alphabet de 4 lettres {N,S,E,O} qui :
- ne contiennent aucun sous-mot avec autant de N que de S et autant de E que de O ;
- permettent d'aller de A à B sans sortir du cadre (ce qui se lit les deux "mots induits" sur {N,S} et sur {E,O})

Pseuda
Habitué(e)
Messages: 3222
Enregistré le: 08 Avr 2015, 12:44

Re: Combien de trajets ?

par Pseuda » 22 Fév 2017, 12:08

Bonjour,

Une précision : le trajet doit obligatoirement passer par l'ensemble des sommets de la grille, comme indiqué sur l'exemple ?

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 14:14

Re: Combien de trajets ?

par beagle » 22 Fév 2017, 12:16

Pseuda a écrit:Bonjour,

Une précision : le trajet doit obligatoirement passer par l'ensemble des sommets de la grille, comme indiqué sur l'exemple ?


a priori oui, il semblerait que cela soit la seule façon de faire du 80 de longueur.
J'en étais à si un carré 2x2 vide = un point non utilisé, alors on ne fait plus du 80.
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 14:14

Re: Combien de trajets ?

par beagle » 22 Fév 2017, 12:21

il ya 9x9 =81 points
un point un segment qui part
le dernier point atteint ne fait pas partir de segment
9x9x=81
81-1 =80
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Pseuda
Habitué(e)
Messages: 3222
Enregistré le: 08 Avr 2015, 12:44

Re: Combien de trajets ?

par Pseuda » 22 Fév 2017, 12:25

beagle a écrit:
Pseuda a écrit:Bonjour,

Une précision : le trajet doit obligatoirement passer par l'ensemble des sommets de la grille, comme indiqué sur l'exemple ?


a priori oui, il semblerait que cela soit la seule façon de faire du 80 de longueur.

En effet. :)

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 14:14

Re: Combien de trajets ?

par beagle » 22 Fév 2017, 12:34

question y a-t-il autant de solutions que si on partait d'un coin du carré 8x8 pour arriver au coin opposé.
bref on aurait fait cette variante pour embrouiller juste un peu.
et si oui comment on calcule les trajets qui ne se coupent pas.c'est-y plus simple si c'est idem.
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 19:39

Re: Combien de trajets ?

par chan79 » 22 Fév 2017, 16:32

beagle a écrit:question y a-t-il autant de solutions que si on partait d'un coin du carré 8x8 pour arriver au coin opposé.
.

salut beagle
l'idée de cette énigme m'est venue comme ça.
Je cherche. Pour l'instant, le n'ai rien de bien précis.
Le nombre de solutions est pair. (symétrie)

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 14:14

Re: Combien de trajets ?

par beagle » 22 Fév 2017, 17:29

L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 19:39

Re: Combien de trajets ?

par chan79 » 22 Fév 2017, 20:22

Super, ça devrait aider !
Je ne m'y connais pas trop en graphes. C'est peut-être par là qu'il faut regarder.

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 10:21

Re: Combien de trajets ?

par nodgim » 23 Fév 2017, 09:09

Je ne sais pas si ça peut t'aider, mais je sais que, sur une grille rectangulaire n*m, selon la parité de n et m, tu ne peux pas toujours joindre, depuis un point donné, n'importe quel autre point d'arrivée, avec la contrainte de devoir passer par tous les autres points de la grille.
Sinon, je vois bien, comme nombre de solutions, une puissance de 2 ou quelque chose d'approché. ...

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

Re: Combien de trajets ?

par fatal_error » 23 Fév 2017, 09:15

salut,

sauf erreur,
tu peux prendre une matrice d'adjacence, (avec des 0 sur la diago, des 1 au dessus, a droite, a gauche, en dessous) que j'appele M.
M*M te donne les chemins de longueur 1. tu veux éviter les cycles, donc tu fais
M1 = M*M - diag(M*M) (pour remettre le compte des cycles à 0)
M2 = M2*M - diag(M2*M)
et tu t'arrete à M80


edit, la matrice est de taille 81*81 (chaque cordo associe un noeud/index) il s'agit de calculer les bons index pour au dessus/droite/...
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 21:53

Re: Combien de trajets ?

par Ben314 » 23 Fév 2017, 09:43

Salut,
J'ai un peu des doutes concernant l'utilisation de matrices d'adjacences dans ce contexte.
De remettre la diagonale à 0 après chaque produit, ça va effectivement éviter de compter les les "cycles" style A-B-A dans M2=M²-diag(M²), mais si tu calcule ensuite M2xM, c'est vrai que tu n'aura pas compté les trajet du type A-B-A-C, mais par compte, tu aura compté ceux du type du style A-C-B-C qui sont tout aussi interdits.
Et réciproquement, si tu fait le produit dans le sens MxM2 alors tu ne compte pas les A-C-B-C, mais tu compte les A-B-A-C. . .

Perso, je procèderais plutôt comme ça :
test.gif
test.gif (4.12 Kio) Vu 614 fois
En ayant une liste de chaines de caractères et en la faisant "évoluer" comme çi dessus .
Le passage d'une étape à la suivant est élémentaire : chaque chaine en créé soit une, soit deux de la nouvelle génération.
A chaque "grosse fin d'étape", c'est à dire à la fin de 4,4 de 5,5 de 6,6, etc... on balaye le tableau pour compter le nombre de config. de chaque type et on met ces nombres dans un 2em tableau (pour limiter la taille du tableau et surtout gagner énormément de temps par la suite vu qu'arrivé à du 8,8, il y a des tas de façon d'obtenir une même "configuration de diagonale")
Arrivé à 9x9, c'est à dire à un demi carré, on regarde tout les couples possibles de demi carrés l'un en face de l'autre et on regarde si ça correspond à ce qu'on veut ou pas au niveau trajet (pas trop difficile à vérifier).
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 21:53

Re: Combien de trajets ?

par Ben314 » 24 Fév 2017, 02:33

J'ai testé le truc, mais vu le bordel, il risque d'y avoir des erreurs....
Par exemple, concernant le dessin de chan79 du 1er post., il se "code"
test.png
test.png (1.73 Kio) Vu 573 fois

Et j'obtiens qu'il y a 1799 façon d'obtenir la diagonale aX0abbc0c et aussi 1799 façon d'obtenir la diagonale a0abbc0Xc (normal, c'est la symétrique de l'autre).
Donc il y aurait 1 799 x 1 799 = 3 236 401 trajets de A à B ayant cette "disposition de diagonale" là.

Et si les calculs sont juste, il y a 1 448 "couples de dispositions de diagonale" possibles et au total, il y a
881 326 620 solutions.

Le "record haut" étant obtenu avec les "dispositions de diagonale" abbacc0dd et aa0bbcddc possédant chacune 3060 façon d'être obtenues donc donnant à elle seule 9 363 600 solutions.
Le "record bas" étant obtenu avec les "dispositions de diagonale" abcXcb00a et ab00bacXc possédant respectivement 14 et 66 façon d'être obtenues donc donnant 924 solutions.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Lostounet
Admin
Messages: 9665
Enregistré le: 16 Mai 2009, 11:00

Re: Combien de trajets ?

par Lostounet » 26 Fév 2017, 20:52

Salut Ben,

Malheureusement j'ai pas encore bien compris ton procédé de codage.. j'aimerais bien étudier ta solution du problème.
Merci de ne pas m'envoyer de messages privés pour répondre à des questions mathématiques ou pour supprimer votre compte.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 21:53

Re: Combien de trajets ?

par Ben314 » 27 Fév 2017, 06:16

A tout moment, dans la mémoire de l'ordi. j'ai deux variables entières n et m ainsi qu'un tableau de chaines de caractère qui décrit les disposition et un tableau d'entier "couplé" au premier qui dit pour chaque disposition combien de façon de l'obtenir il y a.
Le seul truc à comprendre, c'est comment les chaines de caractères "codent" les dispositions et je pensait que c'était clair avec les exemples donnés par les posts. précédents.
Les chaines sont formés des caractères 0, X , a , b ,c ,d et chaque caractère correspond à un point sur la grille, les ponts étant alignés sur une diagonale de longueur n lorsque l'on a m=n et, si m<n, les m premiers points sont ceux du début le la diagonale de longueur n et les suivants sont sur la diagonale d'au dessus.
Aprés, le codage est simple : un 0 signifie que le point n'a pas d'arête partant ni vers le haut, ni vers la gauche, un X qu'il a les deux et une lettre a,b,c,d signifie qu'il a un seul des deux (gauche ou haut) et que si on suit le parcours correspondant, le chemin "ressort" du triangle sur l'autre point (unique) ayant comme code la même lettre.
Par exemple, l'avant dernier post. te dit que, lorsqu'on en est à n=m=4, après "compactage", le tableau de chaine de caractères c'est :
[ "aabb" , "a0Xa" , "0aXa" , "aaX0" , "abba" , "0Xaa" , "aXa0" , "aX0a" ]
et que le tableau de décompte c'est
[2 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ]
i.e. que seule la premiére disposition a deux façon d'être obtenue.
Arrivé à ce point, le programme va créer deux nouveau tableaux (dispo + Nb) correspondant à n=5 , m=2 en partant de ces deux là. Le passage de n=m=4 à n=5 , m=2 consiste à mettre deux points suplémentaire sur la diagonale suivante, ce qui "isole" le premier point de la diagonale précédente à l'intérieur du triangle et il faut absolument compléter le nombre d'arêtes partant de ce point pour qu'il en ait 2 :
Dans la dispo. "aabb" , il y a déjà une arrête partant du premier point. Pour passer à 2, on peut soit en mettre une vers le bas ce qui "produit" la dispo. "a0abb", soit en mettre une vers la droite ce qui produit "0aabb". Dans les deux cas, on met évidement 2 comme "nombre des possibilités" vu qu'il y avait 2 possibilités pour "aabb".
De même, la dispo. "a0Xa" va produire "a00Xa" et "0a0Xa" avec 1 comme "nombre des poss." pour les deux.
La dispo. "0aXa" va produire "bbaXa" uniquement avec 1 comme "nombre des poss" pour les deux.
etc...
Et ça te donne le nouveau tableau correspondant à n=5 , m=2 (et tu peut jeter à la poubelle le précédent qui ne servira plus).
Idem, partant de ce tableau, tu va créer celui correspondant à n=5 , m=3 :
La dispo. "a0abb" va produire "aa0bb" et "a0abb" avec 2 comme "nombre des cas". (fait un dessin)
La dispo. "bbaXa" va produire "bX0Xb" et "bbaXa" avec 1 comme "nombre des cas". (fait un dessin)
etc...
A chaque fois, le but est de compléter le nombre d'arêtes partant du point qui va se retrouver à l'intérieur du triangle de façon à ce qu'il en ait exactement 2.
S'il en a 0, faut en ajouter 2 et y'a pas le choix. S'il en a 2, faut rien rajouter et y'a pas le choix. Et s'il en a 1, il faut en rajouter 1 et y'a deux possibilité : vers le bas ou vers la droite.

Après, vu que c'est ni très long (en temps), ni compliqué, ça peut se programmer avec n'importe quel langage de programmation, aussi basique soit il. Et ça serait pas con qu'il y ait au moins une autre personne qui le fasse pour confirmer le résultat...
Modifié en dernier par Ben314 le 28 Fév 2017, 22:25, modifié 1 fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Lostounet
Admin
Messages: 9665
Enregistré le: 16 Mai 2009, 11:00

Re: Combien de trajets ?

par Lostounet » 28 Fév 2017, 01:00

Merci bien Ben pour ces explications supplémentaires.
Je m'y consacre le weekend!
Merci de ne pas m'envoyer de messages privés pour répondre à des questions mathématiques ou pour supprimer votre compte.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

Re: Combien de trajets ?

par fatal_error » 05 Mar 2017, 19:50

hello,

j'ai testé l'implémentation naive et c'est assez intéressant (mais pas satisfaisant jusque là).
mes cuts sont:
| - |
| x |
^ v
le cellule représentée par x est 1 connectée donc dead end donc pas la peine de continuer
o a |
> f |
v b |
(o est un noeud non visité) la cellule en face est 2 connectée, donc obligatoirement si a et b ne sont pas connectées en enlevant f, alors il faut aller du côté où il n'y a pas end.
(j'ai échoué l'implémentation (lol), il faudrait que je passe un peu plus de temps)

Une autre approche un peu moins dead end, avec un peu de retard, j'ai aucune idée du tps nécessaire, j'ai bien envie de tenter le morpion en m'inspirant de l'idée de Ben:

prendre 9 grilles de 3x3, avec trois motifs différents: corners, middle et centre
avec la différence que chaque grille doit connecter avec ses adjacentes:
avec les connecteurs valant 1 ou 2
vu que dans le cas général, une cellule est 2 connectée, c'est pareil pour les connecteurs,
donc si le connecteur est 1-connecté, son connecteur "associé" provenant de lautre grille doit etre 1-connecté aussi
et si il est 2 connecté, idem.
Aussi, tout connecteur appartient à une chaine qui est liée à un autre connecteur de la grille (sauf celle liée à end ou start) et la gestion de cycle se check en prenant l'union des deux chaines "connectées" (id partagé entre cellules frontales par ex) et en regardant si le nombre d'id différents est "suspicieux"

Rien n'empêche de considérer les grille 3x9 résultantes, sauf l'emplacement mémoire, peut etre...
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 21:53

Re: Combien de trajets ?

par Ben314 » 05 Mar 2017, 21:28

En même temps que je tapais mon truc, je m'était posé la question de savoir si la façon dont je procédait, (à savoir couper en deux puis regarder les différentes paires possible parmi celles obtenues) était "plutôt bien" ou pas par rapport à ce que tu essaye consistant à couper en 9 puis à regarder les différents 9-uplets.

Sinon, au cas où ce soit pas ce que tu compte faire, je pense que tu as intérêt à coder tes 3x3 uniquement en fonction de ce qu'il y a "au bord" histoire de les regrouper par paquets.

Sauf qu'au niveau complexité, je me rend pas bien compte. Concernant mon truc de couper en deux, après test, ça répond quasi-instantanément (en C sous Linux) et ça doit se faire avec n'importe quel langage (40 passages sur un tableau de moins de 10 000 chaines de 10 caractères puis tentative de couplage 2 à 2 des éléments du dernier tableau d'environ 5 000 chaines)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite