Forum de mathématiques - Bibm@th.net

totomm

Invité

Cheminement vectoriel communicant

Bonjour,
Je présente ici une des solutions possibles au problème "Les vases communicants.." proposé par freddy.

Rappel de l'énoncé : " Face à nous, trois urnes transparentes. Dans la première se trouvent 3n boules, les deux autres sont vides. Je dois, en n étapes, arriver à avoir n boules dans chaque urne avec la règle de gestion suivante : à chaque étape p, je peux déplacer exactement p boules d'une urne vers une autre.
Comment fait on ?"

Il est plus facile de décrire une solution par des vecteurs en considérant un problème homomorphe :
" Soit l'espace affine ordinaire de dimension 3 muni d'un repère Oxyz. Soit I le vecteur de coordonnées (-1; 1; 0), J le vecteur (0 ;-1; 1) et K le vecteur (-1 ; 0 ; 1) (note : Puisse le modérateur yoshi m'excuser pour ne pas mettre de flèche au-dessus des vecteurs).
Soit N un entier > 0, on veut construire un chemin continu de vecteurs partant du point A de coordonnées (3N ; 0 ; 0) pour aboutir au point B de coordonnées (N ; N ; N).
Pour construire ce chemin on doit, à l'étape p, (p de 1 à N), déplacer et fixer au point de jonction (p-1), extrémité du chemin construit à l'étape (p-1), l'origine d'un des 6 vecteurs  (pI ou -pI ou pJ ou -pJ ou pK ou –pK). Les 3 coordonnées de chaque point de jonction doivent rester dans l'intervalle fermé [0 ; 3N]."

Le point de jonction initial étant le point A, le premier vecteur utilisable est soit vecteur I,  soit vecteur K.

On voit de suite qu'on peut donner une solution en utilisant des propriétés particulières à une partie de chemin prise entre 2 points de jonction (p-1) et (n-1) et constituée de (n-p) vecteurs Nous noterons {N,p,n} une telle partie de chemin où p < n.
Si l'on conserve pour origine de cette partie de chemin les coordonnées du point de jonction obtenu après l'étape (p-1), on pourra continuer à ajouter des parties de chemin du point de jonction (n-1) jusqu'à B.

Chemins pour N allant de 1 à 11 : On en suppose au moins une solution connue pour N=3, 5, 6, 7 à 11, trouvées en utilisant papier-crayon par exemple. (à défaut, me les demander)

Propriété N°1 du chemin {N,p,n} : Celle de n'utiliser que des vecteurs parallèles au vecteur I, sauf à utiliser un premier vecteur pJ ou –pJ.
Les solutions sont symétriques entre les vecteurs I et K : Si un chemin {N,p,n} n'utilise que des vecteurs parallèles au vecteur K, on en tiendra compte dans l'accrochage de {N,p,n} au point (p-1), et en remplaçant un éventuel vecteur pJ ou -pJ par son opposé.

Propriété N°2 : Celle que le chemin {N,p,n} ait pour coordonnées origine (3N -p ; p ; 0) et pour coordonnées extrémité : soit (3N -n ; n ; 0), soit (3N -n ; 0 ; n).   

Il faut initialiser un chemin du point A jusqu'à un premier point (p1-1) convenable.
Pour ce faire, on connaît pour n allant de 7 à 11, une solution pour un chemin {n,1,n} telle que le chemin se termine au point n-1 de coordonnées (2n ; n ; 0). (à défaut, me le demander).
Aors pour p1 allant de 7 à 11 et pour N > 11, on prendra le chemin connu {n, 1, n} de chaque n allant respectivement de 7 à 11 en le "raccrochant" au point de cordonnées (3N ; 0 ; 0), ce qui revient à ajouter 3(N-n) à la première coordonnée de tous ses points de jonction.

Nous sommes prêts pour démontrer l'existence d'au moins une solution utilisant des chemins {N,p,n} se "raccordant" par récurrence au chemin initial déterminé comme dit ci-avant.

Propriété N°3 : Avoir un écart minimal entre p et n pour les chemins {N,p,n} ayant la propriété N°2

Si l'on structure les nombres n de façon appropriée, il se trouve que la propriété N°3 entraîne qu'il existe au moins un chemin ayant la propriété N°1, plus :

Propriété N°4 : "Le chemin {N,p,n} peut-être établi suivant un algorithme simple qui comporte une séquence de début, une somme centrale et une séquence finale.

Ces 4 propriétés permettent (après étude non décrite ici) une répartition des nombres n :
A TOUT n entier positif, n >= 12, nous allons associer un nombre p entier positif tels que n=7k+3+i et p=5k+v(i). Pour k=1, i sera dans l'intervalle [2,6] ; pour k>1, i sera dans [0,6]. v(i) respectivement égale à 0,0,2,2,4,4,3 pour i de 0 à 6, ainsi on aura p >= 7.
Nous aurons aussi besoin de ChangeCoordonnée(i) égale respectivement à 0,1,0,1,0,1,1 pour i de 0 à 6

Penons l'exemple de N=44, alors pour 44 : k=5, i=6, v(6)=3, p=5*5+3=28. Associons le couple (44,28) au chemin {44,28,44},
Puis prenons n=28 : k=3, i=4, v(4)=4, p=19. Associons le couple (28,19) au chemin {44,19,28}
Par récurrence nous obtenons une liste de couples (44, 28), (28,19),(19,12),(12,7) qui suffisent pour construire le chemin {44,1,44} en exploitant cette liste en dernier-entré-premier-sorti (LIFO).

Pour construire les chemins {N,p,n}, nous exprimons dans la suite p et n en fonction de k et ne considérons que les coordonnées Y suivant l'axe Oy

i=0 : Le chemin {N,p,n} comporte (n-p) = (7k+3)-5k = (2k+3) vecteurs et son premier vecteur a 5k pour coordonnées suivant l'axe Oy.
par hypothèses le point de jonction (p-1) a pour coordonnée Y=p= 5k
On ajoute 3 vecteurs, Y devient 5k+5k+(5k+1)+(5k+2)=20k+3
On ajoute (2k-4) vecteurs (opération -,+) ajoutant (k-2) à Y qui devient Y=21k+1
L'extrémité du dernier vecteur ajouté est celle du vecteur (5k+2)+(2k-4)=7k-2
On insère  4 vecteurs et Y=(21k+1)-(7k-1)-7k-(7k+1)+(7k+2)=7k+3
Le dernier point de jonction de {N,p,n} est celui du vecteur 7k+2=n-1 et Y =n

i=1 : Le chemin {N,p,n} comporte (n-p) = (7k+3+1)-5k = (2k+4) vecteurs et son premier vecteur a 5k pour coordonnées suivant l'axe Oy.
par hypothèses le point de jonction (p-1) a pour coordonnée Y=p= 5k
Attention : ChangeCoordonnée(1)=1 donc on ajoute à Y =0 un premier vecteur de coordonnées celle du point de jonction (p-1), puis
On ajoute 3 vecteurs, Y devient 5k+(5k+1)+(5k+2)+(5k+3)=20k+6
On ajoute (2k-4) vecteurs (opération -,+) ajoutant (k-2) à Y qui devient Y=21k+4
L'extrémité du dernier vecteur ajouté est celle du vecteur (5k+3)+(2k-4)=7k-1
On insère  4 vecteurs et Y=(21k+4) -(7k)-(7k+1)-(7k+2)+(7k+3)=7k+4 
Le dernier point de jonction de {N,p,n} est celui du vecteur 7k+3=n-1 et Y =n

i=2 : Le chemin {N,p,n} comporte (n-p) = (7k+3+2)-(5k+2) = (2k+3) vecteurs et son premier vecteur a (5k+2) pour coordonnées suivant l'axe Oy.
par hypothèses le point de jonction (p-1) a pour coordonnée Y=p= 5k+2
On ajoute 2 vecteurs, Y devient (5k+2)+(5k+2)+(5k+3)=15k+7
On ajoute (2k-2) vecteurs (opération +,-) retranchant (k-1) à Y qui devient Y=14k+8
L'extrémité du dernier vecteur ajouté est celle du vecteur (5k+3)+(2k-2)=7k+1
On insère  3 vecteurs et Y=(14k+8) -(7k+2)+(7k+3)-(7k+4)=7k+5
Le dernier point de jonction de {N,p,n} est celui du vecteur 7k+4=n-1 et Y =n

i=3 : Le chemin {N,p,n} comporte (n-p) = (7k+3+3)-(5k+2) = (2k+4) vecteurs et son premier vecteur a (5k+2) pour coordonnées suivant l'axe Oy.
par hypothèses le point de jonction (p-1) a pour coordonnée Y=p= 5k+2
Attention : ChangeCoordonnée(1)=1 donc on ajoute à Y = 0 un premier vecteur de coordonnées celle du point de jonction (p-1), puis
On ajoute 2 vecteurs, Y devient (5k+2)+(5k+3)+(5k+4)=15k+9
On ajoute (2k-2) vecteurs (opération +,-) retranchant (k-1) à Y qui devient Y=14k+10
L'extrémité du dernier vecteur ajouté est celle du vecteur (5k+4)+(2k-2)=7k+2
On insère  3 vecteurs et Y=(14k+10) -(7k+3)+(7k+4)-(7k+5)=7k+6 
Le dernier point de jonction de {N,p,n} est celui du vecteur 7k+5=n-1 et Y =n

I=4: Le chemin {N,p,n} comporte (n-p) = (7k+3+4)-(5k+4) = (2k+3) vecteurs et son premier vecteur a (5k+4) pour coordonnées suivant l'axe Oy.
par hypothèses le point de jonction (p-1) a pour coordonnée Y=p= 5k+4
On ajoute 3 vecteurs, Y devient (5k+4)+(5k+4)+(5k+5)+(5k+6)=20k+19
On ajoute (2k-2) vecteurs (opération -,+) ajoutant (k-1) à Y qui devient Y=21k+18
L'extrémité du dernier vecteur ajouté est celle du vecteur (5k+6)+(2k-2)=7k+4
On insère  2 vecteurs et Y=(21k+18) -(7k+5)-(7k+6)=7k+7
Le dernier point de jonction de {N,p,n} est celui du vecteur 7k+6=n-1 et Y =n

I=5 : Le chemin {N,p,n} comporte (n-p) = (7k+3+5)-(5k+4) = (2k+4) vecteurs et son premier vecteur a (5k+4) pour coordonnées suivant l'axe Oy.
par hypothèses le point de jonction (p-1) a pour coordonnée Y=p= 5k+4
Attention : ChangeCoordonnée(1)=1 donc on ajoute à Y = 0 un premier vecteur de coordonnées celle du point de jonction (p-1), puis
On ajoute 2 vecteurs, Y devient (5k+4)+(5k+5)+(5k+6)=15k+15
On ajoute (2k) vecteurs (opération +,-) retranchant (k) à Y qui devient Y=14k+15
L'extrémité du dernier vecteur ajouté est celle du vecteur (5k+6)+(2k)=7k+6
On insère  1 vecteurs et Y=(14k+15) -(7k+7)=7k+8 
Le dernier point de jonction de {N,p,n} est celui du vecteur 7k+7=n-1 et Y =n

I=6 : Le chemin {N,p,n} comporte (n-p) = (7k+3+6)-(5k+3) = (2k+6) vecteurs et son premier vecteur a (5k+3) pour coordonnées suivant l'axe Oy.
par hypothèses le point de jonction (p-1) a pour coordonnée Y=p= 5k+3
Attention : ChangeCoordonnée(1)=1 donc on ajoute à Y = 0 un premier vecteur de coordonnées celle du point de jonction (p-1), puis
On ajoute 2 vecteurs, Y devient (5k+3)+(5k+4)+(5k+5)=15k+12
On ajoute (2k-2) vecteurs (opération +,-) retranchant (k-1) à Y qui devient Y=14k+13
L'extrémité du dernier vecteur ajouté est celle du vecteur (5k+5)+(2k-2)=7k+3
On insère  5 vecteurs et Y=(14k+13)-(7k+4)+(7k+5)-(7k+6)-(7k+7)+(7k+8)=7k+9
Le dernier point de jonction de {N,p,n} est celui du vecteur 7k+8=n-1 et Y =n

En résumé : pour tout k, pour chaque i, existe un chemin, jonction de chemins récurrents bien définis.
Ne pas oublier d'insérer le dernier vecteur final.

C'est bien plus facile à décrire directement en langage Python !!

Espérant ne pas avoir laissé d'erreur…Cordialement

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Cheminement vectoriel communicant

Salut,

c'est qui, le nombre n, par rapport à N ?

totomm

Invité

Re : Cheminement vectoriel communicant

Bonjour,

Navré de ne savoir sans doute répondre correctement à votre question sans que vous ne m'ayez dit ce que vous ne comprendriez pas.
J'utilise, de façon libre, N à la place de n pour qu'il n'y ait pas de confusion avec les n des "sous-chemins" notés {N,p,n}.
Le chemin complet commence en A de coordonnées (3N ; 0 ; 0) pour aboutir au point B de coordonnées (N ; N ; N).

Cordialement

totomm

Invité

Re : Cheminement vectoriel communicant

Re,

je crois saisir ce qui vous a sans doute échappé : Un chemin complet noté {N,1,N} de A à B se décompose naturellement en sous-chemins successifs définis à partir de B : {N,p0,N},{N,p1,n1}...etc
n0=N décomposé en k et i donne p0, qui est le n1 du sous-chemin suivant.
n1 décomposé en k et i donne p1, qui est le n2 du sous-chemin suivant...
j'ai donné explicitement cette "récurrence" intuitive pour N=44.

Cette explication est-elle suffisamment claire ?

Cordialement

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Cheminement vectoriel communicant

Salut mon grand,

je ne sais de quelle génération tu es, mais on va arrêter là : tu es et reste incompréhensible pour moi. Je ne comprends rien à tes notations, à tes conventions d'écriture, à ta logique, à tes démonstrations ...

Désolé, mais il me manque un petit je-ne-sais-quoi qui m'illuminerait le côté obscur de ta démarche intellectuelle.

Une bonne continuation sur le site.

totomm

Invité

Re : Cheminement vectoriel communicant

Bonjour,

@freddy :
C'est sur votre insistance que j'ai rédigé une démonstration complète sur ce problème pas facile. Peut-être en publierez vous une de votre coté ?

Je n'ai pas à rougir de ma génération, je sais me servir des ordinateurs, je sais raisonner, mes résultats sont parfaitement vérifiables,
je comprends, moi, parfaitement vos notations et vos conventions,

Il ne suffit pas de prendre des positions "pour paraître",
chacun pourra vérifier qui est sincère.

Cordialement.