promenade

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

Le calcul de f(2,n) est sûrement faisable. Après, ça a l'air dur.

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

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 ?

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

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

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)

@Aldo : oui j'ai fait le même raisonnement.

Maintenant, pour $f(3,n)$ je crois que c'est encore possible de le calculer mais il faut être encore plus concentré pour ne rien oublier.

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.

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

@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

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.

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}$

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

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

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:

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

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)

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?

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.

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

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