Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

Un looping sur grille

Posté par
Alishisap
04-03-18 à 18:38

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 :

Un looping sur grille

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 d_0\times d_1\times...\times d_{n-1}.


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.

Posté par
derny
re : Un looping sur grille 04-03-18 à 22:42

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.

Posté par
Alishisap
re : Un looping sur grille 04-03-18 à 22:49

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.

Posté par
derny
re : Un looping sur grille 05-03-18 à 09:07

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

Posté par
carpediem
re : Un looping sur grille 05-03-18 à 11:15

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 ...

Posté par
lake
re : Un looping sur grille 05-03-18 à 12:03

Bonjour,

 Cliquez pour afficher

Posté par
lake
re : Un looping sur grille 05-03-18 à 15:17

 Cliquez pour afficher

Posté par
lake
re : Un looping sur grille 05-03-18 à 16:10

 Cliquez pour afficher

Posté par
carpediem
re : Un looping sur grille 05-03-18 à 17:06

H = haut, B = bas, G = ... et D = ...

Un looping sur grille

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

....

Posté par
derny
re : Un looping sur grille 05-03-18 à 17:20

Bonsoir. Carpediem je ne comprends pas ta démarche.
De plus ton rectangle fait 4 au lieu de 5 en largeur.

Posté par
carpediem
re : Un looping sur grille 05-03-18 à 17:32

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

...

Posté par
derny
re : Un looping sur grille 05-03-18 à 18:35

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 ?

Posté par
lake
re : Un looping sur grille 05-03-18 à 19:52

Citation :
Quels sont tes résultats chiffrés ?


En voilà une bonne question !

Posté par
Alishisap
re : Un looping sur grille 05-03-18 à 21:51

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.

Posté par
lake
re : Un looping sur grille 05-03-18 à 22:52

Bonsoir Alishisap,

  Pour qu'on soit clair: un parcours tel que celui ci est valable ?

Un looping sur grille

  Que donne ton programme pour, par exemple, une grille 4\times 1 et plus généralement pour une grille n\times 1 ?

Posté par
veleda
re : Un looping sur grille 06-03-18 à 00:40

bonsoir,
j'ai un problème je ne peux plus cacher mes réponses ,le blank ne fonctionne plus,

 Cliquez pour afficher


merci

Posté par
carpediem
re : Un looping sur grille 06-03-18 à 01:12

j'ai pensé comme veleda ...

Posté par
derny
re : Un looping sur grille 06-03-18 à 07:36

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) :

 Cliquez pour afficher

Posté par
derny
re : Un looping sur grille 06-03-18 à 07:48

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 **

Posté par
lake
re : Un looping sur grille 06-03-18 à 08:09

Bonjour,

  

Citation :
pour joindre A à un point de la base  distant  de x cases  du coin droit il y a

C_{x+5}^x    chemins  et  autant  pour  remonter en  A


A moins que j'aie mal interprété l'énoncé, je ne crois pas:

   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.

  Autre chose: le point en bas à gauche de la grille d'Alishisap n'est jamais atteint.

  J'avais obtenu une formule sommatoire:

    N(n,p)=\sum_{k=0}^{n-1}\binom{p+k-1}{k}\binom{p+k}{k}+\sum_{k=0}^{p-1}\binom{n+k-1}{k}\binom{n+k}{k}

   qui donne N(n,1)=\dfrac{n^2+n+2}{2}

  mais que j'ai été incapable de transformer en fonction explicite de n et p

Posté par
derny
re : Un looping sur grille 08-03-18 à 22:24

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) :

 Cliquez pour afficher

Posté par
derny
re : Un looping sur grille 09-03-18 à 03:39

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.

Un looping sur grille

Posté par
lake
re : Un looping sur grille 09-03-18 à 06:11

Citation :
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


Non, dès qu'on est en C, on attaque le retour:

Citation :
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.

Posté par
veleda
re : Un looping sur grille 09-03-18 à 20:20

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

Posté par
lake
re : Un looping sur grille 09-03-18 à 21:00

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!   

Posté par
veleda
re : Un looping sur grille 09-03-18 à 22:28

>>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)

Posté par
lake
re : Un looping sur grille 09-03-18 à 22:50

Citation :
j'ai cherché  en vain à simplifier ton expression de N(n,p)


Ce n'est pas faute d'avoir essayé: je n'y arrive pas non plus.

Je commence à douter qu' on puisse obtenir une formule explicite fonction de n et p.

A en croire Alishisap, il existerait une formule:

Citation :
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.


A moins que ce soit aussi une formule sommatoire....  

Posté par
derny
re : Un looping sur grille 09-03-18 à 23:27

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.

Posté par
derny
re : Un looping sur grille 10-03-18 à 00:30

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

Un looping sur grille

Posté par
lake
re : Un looping sur grille 10-03-18 à 00:39

Je crois que ce coup ci on est d'accord:

Citation :
 Cliquez pour afficher


Mais il semble que Alishisap n'est pas d'accord:

Citation :
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) .




Wait and see

Posté par
derny
re : Un looping sur grille 10-03-18 à 08:40

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.

Posté par
lake
re : Un looping sur grille 10-03-18 à 10:23

Plus simplement, je pense qu' Alishisap s'est planté.
Ça arrive aux meilleurs

Posté par
lake
re : Un looping sur grille 10-03-18 à 16:18

>> derny:

  

Citation :
Pour le(s) modérateur(s) :
 Cliquez pour afficher


La règle sur l' pas de scans de documents excepté pour des figures.

Que tu sois "propriétaire" ou non des documents en question, ils sont supprimés.

  Et tout document (même si tu en es l'auteur) scanné sera supprimé à l'avenir.

Tout ça pour te dire que si tu veux poster quelque chose, il faudra l'écrire en clair

Posté par
derny
re : Un looping sur grille 10-03-18 à 19:44

Bonsoir.
... ne doivent pas se toucher ... (je rectifie mon message précédent ...).

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !