Une fourmi baladeuse

[invite8ef897e4]

Bonjour,

je vous previens, je n'ai pas la solution numerique sous la main, juste le principe pour l'instant. Il s'agit d'un probleme auquel nous avons pense hier soir avec des amis, et que j'ai trouve interessant.

Une fourmi se balade le long des aretes d'un cube de cote unite. Le probleme est de compter le nombre de chemins de longueur n entre deux sommets.
Bah voila, c'est pas complique. La solution n'est pas tres compliquee non plus, en tout cas celle que je connais, mais encore faut-il la trouver

J'espere que ce probleme vous amusera autant que moi
-----

[dgidgi]

Bonjour,

Problème a priori amusant, mais je reste inquiet devant les données.

Peut-on avoir des précisions sur ce qu'est un chemin ?
Peut-on passer plusieurs fois par le même sommet ? Par la même arête ? Par la même arête et dans le même sens ? Par la même arête et dans des sens différents ?

Y a-t-il des limites à n ? Cette dernière question n'a pas lieu d'être si toutes les réponses aux questions qui la précèdent est non.

Merci de préciser les conditions d'existence du chemin.

[invite8ef897e4]

Peut-on passer plusieurs fois par le même sommet ?

Oui

Par la même arête ?

Oui

Par la même arête et dans le même sens ?

Oui

Par la même arête et dans des sens différents ?

Oui.

Un chemin est seulement restreint aux aretes du cube, mais c'est tout. Par exemple, un chemin admissible de longueur 40 du sommet A au sommet C (en passant par B) serait
ABABABABABABABABABABABABABABAB ABABABABABC
ce qui n'a strictement aucun interet pratique. L'interet de ce probleme est comment resoudre la question initiale, un probleme purement combinatoire

[ABN84]

bonjour,
ma petite contribution:
deux sommets distants de 1:
n=1:1
n=2:0
n=3:7
n=4:0
n=5:9+beaucoup

[A voir en vidéo sur Futura]

[Infra_Red]

faut juste faire un arbre
donne moi 15min

[Infra_Red]

j'ai 14 possibilités, en me limitant à 1 passage par A et 2 passages max par chaque autre sommet.
les pts A et B sont placés sur une diagonale d'une des faces.

[Infra_Red]

en fait y'a surement un poil plus, j'ai zappé qq passages.
suffit de faire un arbre ordonné et clair

[invite8ef897e4]

J'ai pas compris l'histoire de l'arbre !

[Infra_Red]

un arbre de probabilité :

je pars de A, j'ai 3 possibilités, qui elles ont également 3 poissiblités, ...

[invite8ef897e4]

je pars de A, j'ai 3 possibilités, qui elles ont également 3 poissiblités, ...

Non mais, ca va, je connais sept definitions equivalentes (caracteristiques) d'un arbre en theorie des graphes, ca va merci

En revanche, la dans le cas general je ne vois comment faire avec cette approche. C'est une sorte de "depliement" du cube a l'ordre n, bah apres quelques essais je trouve pas comment progresser... sauf a retomber sur l'autre approche que je connais deja !

[Infra_Red]

pourtant jtrouve ça adapté au problème.
après c'est peut-être moi qui n'est pas compris le problème.

[invite8ef897e4]

pourtant jtrouve ça adapté au problème.
après c'est peut-être moi qui n'est pas compris le problème.

Ah je ne voulais pas sembler dire ca !

L'idee, c'est quoi, c'est d'obtenir disons les 4 ou 5 premieres valeures, essayer de deviner une relation de recurrence, et la demontrer pour obtenir le cas general ?

[invite35452583]

On appellera les sommets ABCDEFGH avec la notation habituelle.
Pour un sommet Z on note Z(n)=nombre de chemins possibles de longueur n entre A et Z.

Soit Z un sommet et n un entier :

En effet, tout troncature de longueur n d'un chemin de longueur n+1 se termine en un et un seul des sommets adjacents.

Or, on a :

et


Puisque A(0)=1 et Z(0)=0 pour un sommet Z distinct de A, on a :
A(impair)=C(impair)=F(impair)= H(impair)=0
G(pair)=E(pair)=D(pair)=B(pair )=0
et



Reste à savoir calculer M^m(1,0,0,0) pour m entier où M est la matrice 4x4 ci-dessus.
Or, on voit facilement que -1 est valeur propre triple d'espace propre de dimension 3, que 3 est valeur propre simple. Les vecteurs propres sont tout aussi simples à trouver.
Ou plus simplement, en posant u=(1,1,1,1) et v=(3,-1,-1,-1), on a :
(1,0,0,0)=(u+v)/4
Or, M(u)=3u et M(v)=-v.
Donc M^m(1,0,0,0)=(3^mu+(-1)^mv)/4.

On en déduit alors :

[invite8ef897e4]

Avant meme de lire la reponse, je me suis dit qu'homotopie aurait surement trouve la solution.
C'est un probleme je crois assez classique mais tres interessant il me semble, parce qu'abordable a un niveau raisonnable avec pas mal de choses a approfondir potentiellement.

[JPL]

parce qu'abordable a un niveau raisonnable

En regardant le message d'homotopie j'ai pensé à Corneille "cette obscure clarté qui tombe des étoiles..." et je n'en ai retenu qu'un mot : obscure ! Faut dire que mon niveau en math...
Donc bravo à notre étoile pour cette solution si éclairante (à condition d'avoir un pré-requis minimum )

[invite35452583]

C'est un probleme je crois assez classique mais tres interessant il me semble, parce qu'abordable a un niveau raisonnable avec pas mal de choses a approfondir potentiellement.

C'est en effet un joli problème qui montre la puissance de l'algèbre linéaire à un niveau pas très élevé.
Pour l'approfondissement, je ne sais pas, peut-être en informatique. C'est en tout cas généralisable à toute sorte de réseau. Les calculs matriciels doivent être, en général, bien moins élégants par contre. Notamment la subdivision en deux groupes de sommets qui divise par 2 la dimension ne se généralise pas.

Merci JPL pour ce moment poétique.

[invite8ef897e4]

Pour l'approfondissement, je ne sais pas, peut-être en informatique. C'est en tout cas généralisable à toute sorte de réseau. Les calculs matriciels doivent être, en général, bien moins élégants par contre.

Je suis tout a fait d'accord que les calculs explicites ne sont pas tres interessant dans le cas general. Ce qui me semble interessant, c'est de comprendre que l'on obtiens une matrice de connectivite pour le cube considere comme un graphe, et que l'on peut facilement implementer des contraintes supplementaires sur les flux le long des aretes telles que "la fourmi va plus vite lorsqu'elle descend le long d'une arete verticale", ou "plus doucement lorsqu'elle monte". Cela est aussi utile pour les ingenieurs qui etudient les circuits electriques par exemple. Bah je vais pas argumenter pour dire que connaitre un peu de theorie des graphes est interessant