Forum de mathématiques - Bibm@th.net

Un système S constitué de N constituants part d'un état A pour arriver dans un état B, en suivant une transformation.
Si pour toute transformation permise, les N constituants doivent  obligatoirement passer non simultanément ( sinon au moins un temps est perdu) au moins une fois par des états connus $E_1, E_2, .... , E_N $  entre A et B, on peut affirmer que le (ou les ) chemin(s)  parmi les  transformations permises pour passer de A à B sont de longueur au moins N+1:
A permutation près $A \rightarrow E_1 \rightarrow E_2 \rightarrow ... \rightarrow E_N \rightarrow B$.
On comprendra cette analogie directement avec le bar de Fred, vu que deux verres distincts ne peuvent avoir l'état vide simultanément, mais qu'en tous les cas chaque verre  doit être vide à moment donné, on ne peut y échapper...
Tous les chemins permis ( par forcément unique)  passant juste une unique fois  par ces stades ( sans ordre chronologique imposé d'ailleurs ) sont forcément de longueur minimum.
Il suffit donc d'en trouver un seul pour obtenir le minimum, quitte  à cogiter un peu pour trouver un algorithme répondant à la question:
Je l'ai donné d'ailleurs schématiquement dans l'approche par récurrence: une fois réussi avec N verres, on esquive la dernière étape inutile ( qui  concluait pour N) qu'on remplace par une utile au rang N+2, et donc on n'a besoin de n'en rajouter que deux connues au rang N+2 en regard du rang N. L'algorithme est alors connu pour tous les rangs, celui au rang 4 étant à la portée d'un cm2.

Notons $N$ le nombre de verres de Lille qui est égal au nombre de verres de Marseille.
Pour un verre je dis qu'il a une valeur 1 s'il contient une moitié de Bierre, 2 s'il est plein de Bierre, -1 pour une moitié de Pastis, -2 pour un verre plein de Pastis et 0 pour un verre vide.
Au début on a une configuration de la forme
$$+1,+1,\dots, +1$$
$$-1,-1,\dots, -1$$
(chaque ligne a $N$ verres pour un total de $2N$ verres.

On commence par faire une étape pour se ramener à
$$+2, 0,1,\dots,+1$$
$$-1,-1,-1,\dots, -1$$
Ensuite en $N-1+N-2=2N-3$ étapes (en alternant le versage d'un $-1$ dans le $0$ du dessus et d'un $+1$ vers le $0$ du dessous) on peut obtenir la configuration
$$+2,-1,-1,\dots,-1,-1 -1$$
$$+1,+1,+1,\dots +1,0,-1$$
Il y a un $+2$ et $N-1$ verres $-1$ sur la première ligne, il y a $N-2$ verres $+1$ un $0$ et un $-1$ sur la ligne du bas. Il suffit alors de quatre étapes (deux pour transvaser le +2 en bas, 1 pour mettre le dernier -1 en haut et une pour diviser le +2 en deux +1).

Finalement on a utilisé $1+2N-3+4=2N+2$ étapes.
Cette stratégie est certainement optimale, on peut se convaincre qu'il faut au moins $2N$ étapes car aucun des $2N$ verre n'est du bon signe au début. De plus il y a besoin d'une étape de fusion car on ne peut que faire ça au début, ceci fait au moins $2N+1$ étapes. Il reste à voir qu'avec une seule fusion il y a au plus un seul 0 parmi les $2N$ verres. Ainsi quand on va faire un transfert d'une des deux doses du verre à $+2$, on va soit créer un autre $+2$ soit supprimer l'unique autre $0$ (et alors la dose restante dans le verre à $+2$ sera fusionnée dans un autre verre pour créer un autre $+2$). Ainsi dans tous les cas on va créer un autre verre à $+2$ à un moment ou à un autre et donc on aura besoin d'une étape supplémentaire pour diviser ce verre en deux. D'où $2N+2$ étapes au minimum.

Pour $N=11$ ça fait $24$ étapes au minimum.

En espérant que je n'ai pas oublié une étape dans cette stratégie !

Je suis désolé, je ne comprends toujours pas ...
Pourrais-tu écrire le détail pour $n=2$, si j'ai bien compris, tu ne devrais écrire que 5 manoeuvres.

Je ne comprends pas ce que tu veux dire par : "le verre vide doit parcourir au moins tous les verres".
Il n'y a pas de verre vide au départ, on ne rajoute pas de verre et on peut vider le contenu d'un verre
dans un verre aussi éloigné que l'on veut, pour peu que l'on respecte les règles de ne pas mélanger".