Bonjour,
voici une énigme inspirée du problème ouvert d'un rallye mathématique. A noter que les questions posées ne sont jamais exactement les mêmes.
On considère une grille bidimensionnelle de 9 x 5 cases.
On note A le point en haut à droite de la grille. Partant de A, un objet se déplace sur la grille suivant les segments.
Au début, à chaque déplacement il ne peut se déplacer que d'une case vers la gauche ou vers le bas.
Dès que cet objet atteint le bord gauche ou le bord du bas de la grille, les règles changent : il ne peut désormais que se déplacer d'une case vers la droite ou vers le haut à chaque déplacement.
On appelle "chemin" une suite ordonnée de déplacements au bout desquels l'objet revient sur A (c'est-à-dire, a fait une boucle).
Voici un chemin possible :
Questions
1) Quel est le nombre de chemins différents possibles sur cette grille ?
2) Donner une généralisation de la question précédente sur une grille bidimensionnelle de taille n x p (en termes de cases) où n, p 0. Le point A se situe toujours en haut à droite.
3) Donner une généralisation de la question précédente sur un "quadrillage" de dimension n de taille .
Indications :
- on pourra observer ce qui se passe en dimension 3 pour la généralisation.
- vérifier que les formules trouvées sont toujours valables en généralisant.
Bonsoir. Précision : le chemin jaune de retour peut-il couper le chemin de l'aller ? Si oui ce n'est plus vraiment une boucle. Si non, les chemins aller et retour peuvent-ils se toucher par un angle ?
Un début de réflexion : le nombre de trajets possibles pour relier 2 angles opposés est
(5+9)! / (5!9!) soit 2002 trajets.
Bonsoir derny :
oui, les chemins peuvent sans problème se croiser, du moment que les règles aller et retour sont respectées. C'est une boucle dans le sens où le point de départ et d'arrivée sont les mêmes.
C'est de ma faute, j'aurais dû donner un exemple plus quelconque.
Bonjour. Pour la question 1 :
2[((5+9)!/5!9!)+((5+8)!/5!8!)+...+((5+1)!/5!1!)+((5+0)!/5!0!)]=10010 sauf erreur de calcul
salut
pourquoi choisir A en haut à droite et pas en bas à gauche ... ce qui permet de travailler dans notre espace (plan) naturel et son orientation naturelle ...
H = haut, B = bas, G = ... et D = ...
un chemin de A à un point des côtés opposés est un mot du langage {D, H}
un chemin de A à B est le mot DDDDDDDDD
un chemin de A à C est un mot de dix lettres formé des neufs lettres D et de la lettre H celle-ci ne se trouvant pas à la fin
un chemin de A à D est un mot de onze lettres formé des neufs lettres D et de deux lettres H se terminant par un D
...
aucun chemin ne mène de A à F
....
Bonsoir. Carpediem je ne comprends pas ta démarche.
De plus ton rectangle fait 4 au lieu de 5 en largeur.
bon ok erreur sur la hauteur mais c'est un détail ...
je compte le nombre de chemins conduisant du point A à l'un des autres points
un chemin est alors un mot sur l'alphabet {D, H}
par exemple pour aller de A à K un chemin est DDDDHHHHH (en comptant 5 la hauteur)
je dois donc compter toutes les permutations possibles sans avoir un mot qui se termine par D par exemple DDDHHHHHD n'est pas valide car DDDHHHHH conduit à L
...
J'ai compris ta démarche mais il y a plus simple pour compter. Tu aurais pu prendre autre chose que D et H déjà pris dans ton tableau. Par ailleurs on peut aller de L à K contrairement à ce que tu dis.
Quels sont tes résultats chiffrés ?
Bonsoir à tous,
aucune bonne réponse pour le moment, mais des pistes intéressantes.
Petite indication : la réponse est inférieure à un million (sauf erreur évidemment mais j'ai pu vérifier l'exactitude sur un autre cas par un programme en utilisant la même méthode, ce qui me conforte) .
carpediem : le choix du placement de A est totalement arbitraire puisque la réponse ne dépend pas du coin où il se trouve.
Bonsoir Alishisap,
Pour qu'on soit clair: un parcours tel que celui ci est valable ?
Que donne ton programme pour, par exemple, une grille et plus généralement pour une grille ?
bonsoir,
j'ai un problème je ne peux plus cacher mes réponses ,le blank ne fonctionne plus,
Bonjour. Dans ma solution du 5 mars j'avais simplement multiplié par 2 considérant que le nombre de trajets pour le retour est le même que pour l'aller. C'est vrai mais pour le nombre à l'aller et pour le retour mais j'ai été trop vite sans réfléchir en multipliant simplement par 2. En fait, arrivé en bas, il faut "multiplier" par le nombre de trajets de retour. D'où ma solution (supérieure à un million) :
Pour ce qui est de compter le nombre de trajets aller (ou retours) il y a un moyen très simple sans passer par aucune formule. Il suffit de partir du point de départ, puis à chaque nœud proche on compte le nombre de façons d'y arriver. Ci-dessous la solution d'un problème similaire que je m'étais posé il y a déjà pas mal de temps.
** image supprimée **
Bonjour,
Bonsoir. La remarque de lake est judicieuse :
" Au retour, oui, mais à l'aller, il ne faut pas tenir compte des chemins qui passent par un point de la "base" puisque dès qu'on atteint un tel point, on commence le retour vers A. "
Donc il faut que je revois ma solution.
Pour le(s) modérateur(s) :
Par contre, je ne vois pas pourquoi on ne pourrait pas atteindre le point en bas à gauche.
Pour aller de A à B on doit passer par C. Par contre, pour le retour on peut passer par C ou D. Le nombre de chemins aller de A à B est donc (4+9)!/(4!9!) soit 715. Pour le retour de B à A (5+9)!/(5!9!) soit 2002. Le nombre de chemins différents de A à B et retour est donc de 715x2002=1431430. On fait le même genre de calcul pour tous les points du bas et j'arrive en tout à un total de 2 469 753.
bonsoir,
>>lake
je lis très mal sur l'écran,j'ai sauté la phrase en première lecture et je n'ai pas relu donc
mon dénombrement des "allers" est effectivement inexact
Bonsoir veleda,
Très heureux de te voir parmi nous!
Ma grande sœur souffre de la même gêne que toi; on lui fait des piqures dans les yeux qui apparemment stoppent l'évolution; j'imagine bien que ce n'est pas facile!
>>Lake
cela dépend des jours,j'ai déjà eu 26 injections mais il y a toujours récidive
j'ai cherché en vain à simplifier ton expression de N(n,p)
Bonsoir. Décidément lake a toujours raison. Je n'avais pas relu l'énoncé. Il faut encore une fois que je reprenne un peu mes calculs.
Voila mes chiffres point par point :
Pour chaque point le nombre de chemins possibles à l'aller par le nombre de chemins possibles au retour.
B 1x1=1
C 9x10=90
D 45x55=2475
E 165x220=36300
F 495x715=353925
G 495x1287=637065
H 330x792=261360
I 210x462=97020
J 126x252=31752
K 70x126=8820
L 35x56=1960
M 15x21=315
N 5x6=30
O 1x1=1
Soit un total de 1 431 114
Je crois que ce coup ci on est d'accord:
Bonjour. Si la réponse est inférieure à un million alors je repose ma demande du début. Si on veut une boucle les chemins aller et retour ne doivent pas ce toucher même pas par un point. Dans ces conditions, on arrivera peut-être à moins d'un million et le problème sera un peu plus difficile. Pour les points du bas le retour sera en dessous de l'aller et le contraire pour les points à gauche. Petite remarque facile : dans ces conditions mes points B et O ne seront plus accessibles non plus.
>> derny:
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :