promenade
Bonsoir,
en se promenant dans un rectangle (casier rectangulaire) comportant m cases sur sa longueur et n cases sur sa largeur, combien y a-t-il de trajets possibles visitant toutes les cases ?
on passe d'une case à la suivante en faisant des pas parallèles aux côté du rectangle .
bien cordialement
kolotoko
en se promenant dans un rectangle (casier rectangulaire) comportant m cases sur sa longueur et n cases sur sa largeur, combien y a-t-il de trajets possibles visitant toutes les cases ?
on passe d'une case à la suivante en faisant des pas parallèles aux côté du rectangle .
bien cordialement
kolotoko
Réponses
-
Bonjour,
j'oubliais, on ne passe pas deux fois par la même case.
bien cordialement
kolotoko -
Problème très intéressant, mais qui me semblle difficile. Il rappelle les trajets du cavalier. Tu as trouvé des choses ?
Bonne nuit.
RC -
Bonjour oui super interressant Raymond Cordier je trouve pour ma part ...
sur un damier de m cases par n cases et en ne passant jamais deux fois sur une même case
on pose $\ f(m,n)\ =\ f(n,m)\ $ la quantitée de chemains différents
j'ai pas trop le temps mais pour commencer j'ai déjà ça (je verrai ça plus tard mais si vous trouvez une formule générale qui en plus est connue)
par contre il est évident que $\ f(m,n)\ $ dépend de $\ f(m,n-1)\ $
sinon il faudrait déjà que je vérifie ça mais j'ai pas trop le temps:
$f(1,1)\ =\ 1$
$f(2,1)\ =\ 2$
$f(2,2)\ =\ 8$
$f(3,1)\ =\ 2$
$f(3,2)\ =\ 16$
$f(3,3)\ =\ 32$
$f(4,1)\ =\ 2$
$f(4,2)\ =\ 24$
$f(4,3)\ =\ 84$
$f(4,4)\ =\ .. $ -
Le calcul de f(2,n) est sûrement faisable. Après, ça a l'air dur.
-
Vérifions f(3,3) :
Il y a quatre trajets commençant par a1-b1
Donc aussi quatre trajets commençant par a1-a2.
Donc huit trajets commençant par chacun des coins.
Aucun trajet commençant par b1.
Et huit trajets commençant par la case centrale b2.
Ce qui fait f(3,3) = (4x8)+8 = 40.
Aldo -
Bonsoir Aldo je doute beaucoup de ta réponse
j'ai fait
6 graphes partant d'un coin à multiplier par 4 coins = 24
+
2 graphes partant du centre et allant vers un bord (bord qui n'est pas un coin) à multiplier par 4 bord = 8
tout graphe partant d'un bord (bord qui n'est pas un coin) est impossible
total = 32 -
Je trouve la même chose qu'Aldo.
-
Partant d'un coin pour (3,3) j'en trouve 8 et non 6.
Pour f(4,2)
quatre chemins commençant par a1 : un commençant par a1-b1 et 3 par a1-a2.
trois chemins commençant par b1 : un commençant par b1-c1 et 2 par b1-a1.
Donc f(4,2) = (4x4)+(4x3)=28
Est-ce ok ? -
Oui.
-
tu en a trouvé 8 partant d'un coin Aldo?
je suppose que tu a dessiné le graphe parce que je vois pas du tout où sont les deux qui me manquent
franchement
sinon pour moi il y a une "manière" de voir comment aborder ce problème
il faut considerer le type de cases le resultat sera la somme des chemins par types de cases
le calcul de la quantitée de type de cases c'"est déjà plus abordable
et considerer aussi selon m est pair ou impair et n est pair ou impair
par exemple pour un damier de m=10 et n=6 j'ai compté 14 types de cases -
ça y est j'ai vu les deux qui me manque
ok merci à vous!! -
Bonsoir et bonjour
j'arrive après la bataille : je trouve effectivement 40.
bien cordialement
kolotoko -
C'est bien en considérant les types de cases qu'on se simplifie le problème.
Pour f(5,2) je trouve 40.
Quelle est la logique des f(m,2) : 2, 8, 16, 28, 40 ?
Edité : désolé erreur pour f(5,2) je n'avais vu que 2 chemins commençant par c1, alors qu'il y en a 4.
Donc f(5,2) = 44
f(m,2) devient 2, 8, 16, 28, 44 ... -
Kolotoko oui c'est moi qui en ai oublié deux
faut que je vois pour le reste(mais j'ai pas trop le temps)
en considérant le "type" de cases dans un damier car ton problème se décompose en un problème plus facile à résoudre
dénombrer le "type" de case dans un damier
pour ce faire il faut considérer les quatre cas
n et m pair
n et m impair
n pair et m impair avec n>m
n impair et m pair avec n>m
puis voir tous les chemins par "type" de case que l'on prend pour point de depart
on pourrait noter ces cases comme des composantes $c_{ij}$ d'une n-m matrice
super chouette ce problème...et super dur aussi pour moi -
Je trouve f(2,n)=4n+2(n-1)(n-2) mais je ne suis pas sur d'être assez concentre pour ne pas faire d'erreur.
-
Bonjour,
on dirait bien A137882.
bien cordialement
kolotoko -
J'approuve cette formule et j'explicite : 4n pour les 4 coins, n-1 pour chaque case non coin et il y a 2(n-2) cases de ce genre.
C'est cela ? -
c'est bon JLT
ou alors c'est ça
$\displaystyle f(2,n)\ =\ 4n\ +\ 2\prod_{i=1}^{n-2} (n-i)$
mais faudra verifier f(2,5) -
JLT ça a l'air d'être bon oui c'est 44
4.5+2.4.3=4n +2(n-1)(n-2)=44
la formule donnée par moi n'est pas bonne -
La remarque de kolotoko : "on dirait bien A137882", me semble du plus haut intérêt. On peut considérer que les centres des cases d'un $(n,2)$-rectangle sont les sommets d'un graphe connu comme le graphe-échelle $L_{n}$ (ladder graph). Alors, la question du nombre f(n,2) de nos "promenades" revient à la question du nombre de trajets hamiltoniens orientés sur ce graphe $L_{n}$.
Je ne veux pas me pousser du col, je n'y connais pas grand'chose en théorie des graphes, je viens de découvrir ce graphe-échelle suite à la remarque susdite : vous pouvez faire comme moi. J'ai quand même quelques lueurs sur cette théorie, je sais qu'un trajet hamiltonien sur un graphe est un trajet sur ce graphe qui passe par tous ses sommets, une fois chacun, en distinction avec un trajet eulérien, qui passe par toutes les arêtes de ce graphe, comme pour les ponts de Königsberg (la culture, c'est comme la confiture ).
Cette remarque permet de diriger notre réflexion vers la théorie des graphes. Dans le cas général d'un rectangle $m$ sur $n$, on peut aussi considérer les centres des cases comme les sommets d'un graphe, plus général que le graphe-échelle, et le nombre de nos "promenades" est le nombre des trajets hamiltoniens sur ce graphe. Cela n'apporte rien en soi, c'est juste une reformulation, mais peut-être notre graphe général a-t-il déjà été étudié, au moins partiellement, avec ses trajets hamiltoniens.
On peut aussi chercher le nombre des circuits hamiltoniens, c'est-à-dire le nombre de nos "promenades" où la dernière case est à un pas de la première. Ces circuits n'existent que si $m$ et $n$ ne sont pas tous deux impairs : le graphe est alors dit hamiltonien.
On peut aussi chercher le nombre de classes d'isométries de nos "promenades".
Les théoriciens des graphes qui lisent ceci peuvent donc faire avancer la recherche sur ce sujet.
Bonne journée, temps variable sur l'\`Ile-de-France.
RC
27/08/2013 -
Un programme en python qui cherche toutes les possibilités :
def g(m,n,L): if len(L)==m*n: return 1 else: r=0 (x,y)=L[-1] if x<(m-1) and ((x+1,y) not in L): r+=g(m,n,L+[(x+1,y)]) if y<(n-1) and ((x,y+1) not in L): r+=g(m,n,L+[(x,y+1)]) if x>0 and ((x-1,y) not in L): r+=g(m,n,L+[(x-1,y)]) if y>0 and ((x,y-1) not in L): r+=g(m,n,L+[(x,y-1)]) return r def f(m,n): s=0 for i in xrange(m): for j in xrange(n): s+=g(m,n,[(i,j)]) return s
Explications : g(m,n,L) calcule le nombre de possibilités sachant qu'on est sur un damier m x n, avec L la liste des cases déjà visitées. Pour calculer f(m,n), on fait la somme en envisageant toutes les cases de départ possibles.
Pour les f(n,2), avec n entre 1 et 15 on obtient alors :>>> print([f(n,2) for n in xrange(1,16)]) [2, 8, 16, 28, 44, 64, 88, 116, 148, 184, 224, 268, 316, 368, 424]
À part le premier terme, ça coïncide avec 2n^2-2n+4. -
Il me semble que notre graphe se dénomme "grid graph" :
http://mathworld.wolfram.com/GridGraph.html
et donc notre problème peut se rechercher comme "number of hamiltonian paths on a grid graph".
Bonne journée.
RC -
En français, graphe-grille, je pense.
J'ai trouvé ça :
http://enslyon.free.fr/rapports/info/Aline_Parreau_1.pdf
qui renvoie à ça :
http://www.sciencedirect.com/science/article/pii/0012365X9500330Y
Quel petit malin nous donnera ce dernier ?
La lutte continue.
RC -
Bonjour,
j'ai encore enfoncé une porte ouverte !
bien cordialement
kolotoko -
@kolotoko
Mais non ! Il aurait été bien étrange que ce problème n'ait pas été déjà abordé. Il n'est pas certain qu'il ait été complètement résolu. Et tu as eu le mérite de te le poser de ton propre chef, ce qui a eu pour effet de nous le mettre sous les yeux.
Et il reste les questions supplémentaires que j'ai posées.
Bravo pour ton esprit de recherche.
Bonne journée.
RC -
Bonjour à tous
Le rapport avec les graphes est clair mais il faut quand même bien préciser toutes les données.
Par exemple, nous avons f(1,1)=1 f(2,2)=8 et f(3,3)=40
Or, on trouve :
A120443 : Number of Hamiltonian paths on n X n square grid of points :
1, 4, 20 etc.
Les règles du jeu ne sont donc pas identiques.
Il me semble que nous considérions les graphes orientés.
Par exemple dans le carré (2,2), nous différencions a1-b1-b2-a2 de a2-b2-b1-a1, ce qui ne semble pas être le cas général.
Aldo -
L'article http://ac.els-cdn.com/0012365X9500330Y/1-s2.0-0012365X9500330Y-main.pdf?_tid=95afdc50-0f08-11e3-a4c0-00000aacb35d&acdnat=1377601709_ce22ab525920ef7531ead56cdd194264 s'intéresse au nombre $g(m,n)$ de chemins Hamiltoniens qui partent du carré en haut à gauche et qui finissent en bas à droite, pour $m\leqslant 5$. Ceci semble indiquer que le calcul de $f(m,n)$ pour $m=4,5$ est possible quoique difficile, et que sans doute la valeur de $f(m,n)$ pour $m,n$ arbitraires n'est pas connue.
-
Bonjour
ça va pas avancer à grand chose mais bon ...(sauf erreur j'ai vérifié plusieurs fois mais une fois de plus encore c'est pas un mal)
je considère qu'un "damier" de $m$ cases par $n$ cases je note $c_{ij}$ chacune des cases
selon $\ i \in [1,m]\ $ et $ \ j \in [1,n]\ $ de plus par symetrie on pose $\ m\ \leq \ n$
et je note $\ \bar {c}_{ij}\ $ la quantitée de chemins que l'on peut dénombrer en partant de la case $\ c_{ij}\ $
en considérant $m=n$ sont pairs on pose $\ \displaystyle l\ =\ \frac {m}{2}$
$ \displaystyle f(m,n)\ =\ 8\sum _{i=j,j=1}^{i=l,j=l} \displaystyle \bar {c}_{ij}\ -\ 4\sum _{i=1}^{l} \displaystyle \bar {c}_{ii}\ $
en considérant $m=n$ sont impairs on pose $\ \displaystyle l\ =\ \frac {m-1}{2}\ $ et $\ \displaystyle k\ =\ l+1$
$ \displaystyle f(m,n)\ =\ \bar {c}_{kk}\ +\ 8\sum _{i=j,j=1}^{i=l,j=l} \displaystyle \bar {c}_{ij}\ -\ 4\sum _{i=1}^{l} \displaystyle \bar {c}_{ii}\ +\ 4\sum _{i=1}^{l} \displaystyle \bar {c}_{ik}\ $
en considérant $m< n$ sont pairs on pose $\ \displaystyle l\ =\ \frac {m}{2}\ $ , $\ p\ =\ l+1\ $ et $\ \displaystyle q\ =\ \frac {n}{2}\ $
$ \displaystyle f(m,n)\ =\ 8\sum _{i=j,j=1}^{i=l,j=l} \displaystyle \bar {c}_{ij}\ -\ 4\sum _{i=1}^{l} \displaystyle \bar {c}_{ii}\ +\ 4\sum _{i=1,j=p}^{i=l,j=q} \displaystyle \bar {c}_{ij}$
en considérant $m< n$ sont impairs on pose
$\ \displaystyle l\ =\ \frac {m-1}{2}\ $ , $\ p\ =\ l+1\ $ , $\ \displaystyle q\ =\ \frac {n-1}{2}\ $ et $\ r\ =\ q+1$
$ \displaystyle f(m,n)\ =\ \ \bar {c}_{pr}\ +\ 8\sum _{i=j,j=1}^{i=l,j=l} \displaystyle \bar {c}_{ij}\ -\ 4\sum _{i=1}^{l} \displaystyle \bar {c}_{ii}\ +\ 4\sum _{i=1,j=p}^{i=l,j=q} \displaystyle \bar {c}_{ij}\ +\ 2\sum _{i=1}^{i=l} \displaystyle \bar {c}_{ir}\ +\ 2\sum _{j=1}^{j=q} \displaystyle \bar {c}_{pj}\ $
en considérant $m< n$ avec $\ m\ $ est pair et $\ n\ $ est impair on pose
$\ \displaystyle l\ =\ \frac {m}{2}\ $ , $\ p\ =\ l+1\ $ , $\ \displaystyle q\ =\ \frac {n-1}{2}\ $ et $\ r\ =\ q+1$
$ \displaystyle f(m,n)\ =\ \ \ 8\sum _{i=j,j=1}^{i=l,j=l} \displaystyle \bar {c}_{ij}\ -\ 4\sum _{i=1}^{l} \displaystyle \bar {c}_{ii}\ +\ 4\sum _{i=1,j=p}^{i=l,j=q} \displaystyle \bar {c}_{ij}\ +\ 2\sum _{i=1}^{i=l} \displaystyle \bar {c}_{ir}\ $
en considérant $m< n$ avec $\ m\ $ est impair et $\ n\ $ est pair on pose
$\ \displaystyle l\ =\ \frac {m-1}{2}\ $ , $\ p\ =\ l+1\ $ et $\ \displaystyle q\ =\ \frac {n}{2}\ $
$ \displaystyle f(m,n)\ =\ 8\sum _{i=j,j=1}^{i=l,j=l} \displaystyle \bar {c}_{ij}\ -\ 4\sum _{i=1}^{l} \displaystyle \bar {c}_{ii}\ +\ 4\sum _{i=1,j=p}^{i=l,j=q} \displaystyle \bar {c}_{ij}\ +\ 2\sum _{j=1}^{j=q} \displaystyle \bar {c}_{pj}\ $ -
en notant (voir le post précédent ) $\ c_{m,n,i,j} \ $ la quantitée de chemins que l'on peut dénombrer en partant de la case $\ c_{i,j} \ $ dans un damier de $\ m\ $ cases par $\ n\ $ cases
j'ai l'impression d'avoir $\displaystyle \ c_{m,m,i,j} \ =\ \frac {(m+1)!}{3}$ -
Erreur je voulais dire plutôt
En notant (voir le post précédent ) $\ c_{m,n,i,j} \ $ la quantitée de chemins que l'on peut dénombrer en partant de la case $\ c_{i,j} \ $ dans un damier de $\ m\ $ cases par $\ n\ $ cases
j'ai l'impression d'avoir $\displaystyle \ c_{m,m,1,1} \ =\ \frac {(m+1)!}{3}$ -
Les noms féminins terminés par le son 'té', qui expriment l'idée d'une qualité ou d'un état, s'écrivent 'té', comme qualité, quantité, liberté, égalité, fraternité, etc.
Bonne continuation.
RC -
Je suis impardonnable Raymond Cordier car en plus j'avais vu le lien que tu avais donné pour cette règle
et tu sais que pour moi c'est important
Les maths sont un langage au même titre que les autres enfin presque...
mes respects Raymond Cordier ...et merci
post modifié deux fois pour fautes -
Bonjour,
Il s'agit bien de chemins hamiltoniens.
Si on ne les oriente pas, cela en fait deux fois moins. Il n'y a pas de formule générale pour $g(m,n)=\frac12f(m,n)$.
Pour g(3,n) il y a une formule en distinguant les cas n pair et n impair (suite A3685).
Pour g(m,n) avec $4\leq m\leq 6$ il y a des formules de récurrence linéaire (d'ordre 14 pour m=4, d'ordre 36 pour m=5, d'ordre 114 pour m=6).
Référence: une page de F.Faase que l'on trouve ici: compter les parcours hamiltoniens.
Ce qui nous intéresse dans cette page ce sont les "HP" pour les graphes produits de $P_2, P_3,..., P_6$ par $P_n$. -
Oui, en effet, je me suis étonné que l'on cherche les chemins orirentés, qui sont le double des chemins non orientés. Dans mes recherches empiriques, j'avais plutôt énuméré ces derniers.
Pour un rectangle 2 sur $n$, la suite A137882 donne le " Number of (directed) Hamiltonian paths in the n-ladder graph", " directed", soit orientés.
Les dernières informations semblent montrer que c'est un problème difficile.
On peut aussi chercher ces chemins à isométrie près comme j'ai dit. Pour $(2,2)$ il y a une seule classe. Pour $(2,3)$ il y en a 3. Pour $(3,3)$ il y en a 3. Il n'y a pas autant de chemins dans chaque classe. Mais je n'ai aucune idée de la façon d'aborder cela en général.
On peut aussi chercher les circuits hamiltoniens, c'est-à-dire les chemins fermés, qu'on trouve parmi les chemins tout court en prenant ceux qui se terminent à un "pas" du point de départ.
Une curiosité à ce propos, c'est qu'il y a de tels circuits seulement si $m$ et $n$ ne sont pas tous deux impairs. En effet, supposons qu'on colorie alternativement en noir et blanc les cases, comme sur un damier. Alors, chaque pas fait changer de couleur de case. Le nombre de pas d'un chemin hamiltonien est : $mn-1$. Si ce nombre est pair, la case de départ et celle d'arrivée seront de même couleur, donc elle ne pourront être voisines. Ce genre de raisonnement était présenté dans "Le livre du problème de l'IREM de Strasbourg", volume sur la parité.
Maintenant, si $m$ et $n$ ne sont pas tous deux impairs, existe-t-il nécessairement de tels circuits ? Je pense que oui, mais je ne sais le prouver. Et combien ? Mystère ...
Bonne soirée.
RC
27/08/2013 -
Raymond a écrit:si m et n ne sont pas tous deux impairs, existe-t-il nécessairement de tels circuits ?
L'existence ne semble assez évidente:
-
Pour le dénombrement des circuits hamiltoniens il y a des formules de récurrence jusqu'au rectangle 8 fois n.
C'est donné dans la référence que j'ai citée: ce sont les "HC". -
Bonjour à tous
En utilisant les sommations précédentes (sur lequel on compte les parcours à partir d'un nombre restreint de points de depart -où l'ensemble de ces points de départ constitue un sous damier- et en considérant que certains depart de parcours (première case de départ -> deuxieme case du parcours) sont équivallents pour une même case de départ donnée dans ce sous-damier
et après de nombreuses vérifications relativements simples - mais toujours sous réserve - effectuées (ici tous ces calculs n'ayants nécessités aucuns graphes)
J'en suis arrivé là (ce qui diminue de beaucoup la quantitée de calcul de l'algorithme pour le dénombrement de $\ f(m,n) \ $ par rapport aux sommations du précédent post) :
On considère un "damier" de $m$ cases par $n$ cases et on note $c_{ij}$ chacune des cases
selon $\ i \in [1,m]\ $ et $ \ j \in [1,n]\ $ de plus par symetrie on pose $\ m\ \leq \ n$
on considère la notation $\ f(m,n) \ $ désigne la quantitée de parcours différents passant par toutes les cases en ne passant jamais deux fois sur la même sur un même parcours et en effectuant ce parcours en partant depuis toute case de ce damier
et considérant que le passage d'une case à l'autre s'effectue dans une direction parallèle à l'un des coté de ce damier
on considère la notation $\ a_{ij}\ $ désigne la quantitée de parcours différents passant par toutes les cases en ne passant jamais deux fois sur la même sur un même parcours et en effectuant ce parcours en partant depuis la case $\ c_{ij}\ $
et considérant que le passage d'une case à l'autre s'effectue dans une direction parallèle à l'un des coté de ce damier
pour le dénombrement des valeurs $\ a_{ij}\ $ -il n'est pas necessaire de les determiner toutes mais uniquement selon ce que commande les sommations données en fin de post
on distingue 17 cas suivants:
1)Lorsque : $\ m-i\ =\ n-j\ =\ i-1\ =\ j-1$
on considère $\ D \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
On obtiens $\ a_{ij}\ =\ 4D $
2)Lorsque : $\ j-1\ \neq \ 0\ $ ET $\ m-i\ =\ n-j\ =\ i-1\ \neq \ 0\ $ ET $\ m-i\ =\ n-j\ =\ i-1\ \neq \ j-1\ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
on considère $\ D_3 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{i1}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ D_2\ +\ D_3 $
3)Lorsque : $\ i-1\ \neq \ 0\ $ ET $\ m-i\ =\ n-j\ =\ j-1\ \neq \ 0\ $ ET $\ m-i\ =\ n-j\ =\ j-1\ \neq \ i-1\ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
on considère $\ D_3 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{1j}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ D_2\ +\ D_3 $
4)Lorsque : $\ n-j\ \neq \ 0\ $ ET $\ m-i\ =\ i-1\ =\ j-1\ \neq \ 0\ $ ET $\ m-i\ =\ i-1\ =\ j-1\ \neq \ n-j\ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{i1}\ $
on considère $\ D_3 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ D_2\ +\ D_3 $
5)Lorsque : $\ m-i\ \neq \ 0\ $ ET $\ n-j\ =\ i-1\ =\ j-1\ \neq \ 0\ $ ET $\ n-j\ =\ i-1\ =\ j-1\ \neq \ m-i\ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{1j}\ $
on considère $\ D_3 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ D_2\ +\ D_3 $
6)Lorsque : $\ j-1\ = \ 0\ $ ET $\ n-j\ =\ m-i\ =\ i-1\ \neq \ 0\ $
on considère $\ D \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
On obtiens $\ a_{ij}\ =\ 3D $
7)Lorsque : $\ i-1\ = \ 0\ $ ET $\ n-j\ =\ m-i\ =\ j-1\ \neq \ 0\ $
on considère $\ D \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
On obtiens $\ a_{ij}\ =\ 3D $
8)Lorsque : $\ n-j\ = \ 0\ $ ET $\ m-i \ =\ i-1\ =\ j-1\ \neq \ 0\ $
on considère $\ D \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
On obtiens $\ a_{ij}\ =\ 3D $
9)Lorsque : $\ m-i\ = \ 0\ $ ET $\ n-j\ =\ i-1\ =\ j-1\ \neq \ 0\ $
on considère $\ D \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
On obtiens $\ a_{ij}\ =\ 3D $
10)Lorsque : $\ m-i =\ i-1 \neq \ 0\ $ ET $\ m-1 =\ i-1 \neq \ n-j \ $ ET $\ n-j \neq \ 0 \ $ ET $\ j-1 = \ 0 \ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ D_2 $
11)Lorsque : $\ m-i =\ i-1 \neq \ 0\ $ ET $\ m-i =\ i-1 \neq \ j-1 \ $ ET $\ j-1 \neq \ 0 \ $ ET $\ n-j = \ 0 \ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{i1}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ D_2 $
12)Lorsque : $\ n-j =\ j-1 \neq \ 0\ $ ET $\ n-j =\ j-1 \neq \ m-i \ $ ET $\ m-i \neq \ 0 \ $ ET $\ i-1 = \ 0 \ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ D_2 $
13)Lorsque : $\ n-j =\ j-1 \neq \ 0\ $ ET $\ n-j =\ j-1 \neq \ i-1 \ $ ET $\ i-1 \neq \ 0 \ $ ET $\ m-i = \ 0 \ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{1j}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ D_2 $
14)Lorsque : $\ n-j =\ j-1 \neq \ 0\ $ ET $\ m-i =\ i-1 \neq \ 0\ $ ET $\ m-i \neq n-j\ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ 2D_2 $
15)Lorsque : $\ n-j =\ i-1 \neq \ 0\ $ ET $\ m-i =\ j-1 \neq \ 0\ $ ET $\ m-i \neq n-j\ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{i1}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ 2D_2 $
16)pour $\ a_{11}\ $ on considère $\ D \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{11}\ $ lorsqu'on se dirige en direction de la case $\ c_{m1}\ $
On obtiens $\ a_{ij}\ =\ 2D $
17)Dans tous les autres cas on doit dénombrer tous les parcours en partant de la case $\ c_{ij}$
LES SOMMATIONS
Disposant des valeurs $\ a_{ij}\ $ nécessaires selon les sommations suivantes on obtiens :
en considérant $m=n$ sont pairs on pose $\ \displaystyle l\ =\ \frac {m}{2}$
$ \displaystyle f(m,n)\ =\ 8\sum _{i=j+1,j=1}^{i=l,j=l-1} \displaystyle a_{ij}\ +\ 4\sum _{i=1}^{l} \displaystyle a_{ii}\ $
en considérant $m=n$ sont impairs on pose $\ \displaystyle l\ =\ \frac {m-1}{2}\ $ et $\ \displaystyle k\ =\ l+1$
$ \displaystyle f(m,n)\ =\ a_{kk}\ +\ 8\sum _{i=j+1,j=1}^{i=l,j=l-1} \displaystyle a_{ij}\ +\ 4\sum _{i=1}^{l} \displaystyle a_{ii}\ +\ 4\sum _{i=1}^{l} \displaystyle a_{ik}\ $
en considérant $m< n$ sont pairs on pose $\ \displaystyle l\ =\ \frac {m}{2}\ $ , $\ p\ =\ l+1\ $ et $\ \displaystyle q\ =\ \frac {n}{2}\ $
$ \displaystyle f(m,n)\ =\ 8\sum _{i=j+1,j=1}^{i=l,j=l-1} \displaystyle a_{ij}\ +\ 4\sum _{i=1}^{l} \displaystyle a_{ii}\ +\ 4\sum _{i=1,j=p}^{i=l,j=q} \displaystyle a_{ij}$
en considérant $m< n$ sont impairs on pose
$\ \displaystyle l\ =\ \frac {m-1}{2}\ $ , $\ p\ =\ l+1\ $ , $\ \displaystyle q\ =\ \frac {n-1}{2}\ $ et $\ r\ =\ q+1$
$ \displaystyle f(m,n)\ =\ \ a_{pr}\ +\ 8\sum _{i=j+1,j=1}^{i=l,j=l-1} \displaystyle a_{ij}\ +\ 4\sum _{i=1}^{l} \displaystyle a_{ii}\ +\ 4\sum _{i=1,j=p}^{i=l,j=q} \displaystyle a_{ij}\ +\ 2\sum _{i=1}^{l} \displaystyle a_{ir}\ +\ 2\sum _{j=1}^{q} \displaystyle a_{pj}\ $
en considérant $m< n$ avec $\ m\ $ est pair et $\ n\ $ est impair on pose
$\ \displaystyle l\ =\ \frac {m}{2}\ $ , $\ p\ =\ l+1\ $ , $\ \displaystyle q\ =\ \frac {n-1}{2}\ $ et $\ r\ =\ q+1$
$ \displaystyle f(m,n)\ =\ \ \ 8\sum _{i=j+1,j=1}^{i=l,j=l-1} \displaystyle a_{ij}\ +\ 4\sum _{i=1}^{l} \displaystyle a_{ii}\ +\ 4\sum _{i=1,j=p}^{i=l,j=q} \displaystyle a_{ij}\ +\ 2\sum _{i=1}^{l} \displaystyle a_{ir}\ $
en considérant $m< n$ avec $\ m\ $ est impair et $\ n\ $ est pair on pose
$\ \displaystyle l\ =\ \frac {m-1}{2}\ $ , $\ p\ =\ l+1\ $ et $\ \displaystyle q\ =\ \frac {n}{2}\ $
$ \displaystyle f(m,n)\ =\ 8\sum _{i=j+1,j=1}^{i=l,j=l-1} \displaystyle a_{ij}\ +\ 4\sum _{i=1}^{l} \displaystyle a_{ii}\ +\ 4\sum _{i=1,j=p}^{i=l,j=q} \displaystyle a_{ij}\ +\ 2\sum _{j=1}^{q} \displaystyle a_{pj}\ $
@+ Bonne journée à tous
eh oui 17 cas car j'avais oublié le cas unique $\ a_{11}\ $ qu'on ne retrouve pas ailleurs dans le sous damier -
Bonjour
faut que je fasse l'algorithme mais je crois que le cas 15) ne tiens pas la route...
j'en profite pour reformuler les cas 14) et 15) car ils sont mal présentés
14)Lorsque : $\ n-j =\ j-1 \neq \ 0\ $ ET $\ m-i =\ i-1 \neq \ 0\ $ ET $\ m-i \neq n-j\ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{mj}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ 2D_2 $
LE CAS 15) N'EST PAS TRES LOGIQUE EN Y REFLECHISSANT
15)Lorsque : $\ n-j =\ i-1 \neq \ 0\ $ ET $\ m-i =\ j-1 \neq \ 0\ $ ET $\ m-i \neq n-j\ $
on considère $\ D_1 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{in}\ $
on considère $\ D_2 \ $ qui désigne la quantitée de parcours que l'on peut dénombrer en partant de la case $\ c_{ij}\ $ lorsqu'on se dirige en direction de la case $\ c_{i1}\ $
On obtiens $\ a_{ij}\ =\ 2D_1\ +\ 2D_2 $ -
pour précision le cas 15) n'est valable que si m=n
mais en attendant que je fasse l'algo qui le vérifiera je le laisse écrit tel quel avec ce commentaire
(mais franchement non il est pas très logique sauf si m=n) -
je viens de me rendre compte que justement tel que décrit le cas 15) est possible que si justement m=n
-
Sans la queue d'une idée pour la suite à donner à votre réponse à ma question, je la pose quand-même:
Le problème serait-il plus simple si au lieu du rectangle "à plat" on demandait le nombre de promenades sur le tore obtenu en lui recollant ses côtés opposés? -
bonjour Pdepasse je n'en sait rien là je suis en train de faire l'algo (il est pas terminé mais bien entamé) qui va utiliser les sommations que j'ai posté ici
apres il restera à verifier qu'il est correct puis et c'est là l'idée de voir les valeurs qui composent le resultat je suis sûr qu'en faisant varier m et n on arrivera à trouver des formulations
il ne s'agit pas de voir le rapport entre f(m,n) et f(m+1,n) mais plutôt de voir le rapport entre les differentes valeurs a_ij
donc poursuivant mon idée je le saurai quand j'aurai fait l'algo -
Chamath,
à quoi te sert-il de répondre à ma question que tu n'en sais rien?
Est-ce une marque d'attention (facile!) à mon égard ou un besoin d'être le plus souvent possible cité dans les derniers messages envoyés?
Dans la première hypothèse, et si la seconde est fausse, je te présente mes excuses pour avoir eu la paranoïa d'envisager que ton désir était d'envahir le site par des textes dont je doute que quiconque les lise. -
une marque d'attention pour que tu sache que même si ce fil n'avance pas rapidement on oublie pas
et en ce qui concerne ta question je crains avoir de gros problème car mon approche du problème est tres différente et si j'ai bien compris ta question:
en lui recollant ses côtés opposés
tu change les conditions données au depart
mon approche serait elle aussi utilisable pour les conditions que tu donne?
ce fil est long et difficile mais ta condition est aussi interessante
j'espere terminer et il restera pour moi de voir (si je peux) comment le resoudre selon ce que tu dit et en utilisant la même méthode
ne t'excuse pas je suis rien qu'un chat... -
...je me suis trompé Pdepasse
à la reflexion tu ne change pas les conditions données
car si on fait comme tu le propose en allant d'un bord à l'autre selon ce que tu propose est equivallent à aller dans la direction opposée jusqu'à ce bord
ton approche est equivallente et pour te répondre la difficultée reste la même -
ben non
-
et là tu a encore raison puisque effectivement dans ton approche on limite les directions à deux
oui c'est vrai(je suis parti je fais plusieurs choses en même temps et je manque de concentration)
en terme d'algo ton approche est meilleure
je te présentes mes sincères excuses je ne suis qu'un chat après tout
comme je suis sûr qu'il sera tres difficile de trouver des formulations generales pour les a_ij ton approche sera tres utile
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.1K Toutes les catégories
- 58 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 58 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 83 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 337 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 801 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres