Forum de mathématiques - Bibm@th.net

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 348

Le bar de Fred

Bonjour,

  C'est aujourd'hui le retour du bar de Fred, fréquenté naguère par des habitués du forum ...

  Après un match de football bien disputé, les joueurs de Lille et de Marseille se retrouvent au bar de Fred. Celui-ci a préparé le long du comptoir une file de 22 verres à moitié remplis : 11 verres de bière pour les joueurs de Lille, 11 verrres de pastis pour ceux de Marseille. Soudain, il se rend compte de sa bévue. Les verres à l'écusson de Lille sont remplis de pastis, ceux à l'écusson de Marseille de bière.

  N'écoutant que son courage, il se décide à procéder à l'échange le plus rapidement et le plus discrètement possible, sans utiliser d'autres verres. En particulier, il va respecter les règles suivantes :
* on ne mélange jamais les contenus !
* un verre à moitié plein peut être vidé dans un verre vide ou un autre verre à moitié plein.
* le contenu des verres plein peut être vidé complètement ou à demi dans des verres vides.

De combien de manoeuvres au minimum va-t-il avoir besoin ? Vider un verre plein dans deux verres compte pour deux manoeuvre.

A vous lire !

Fred.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Le bar de Fred

Bonjour,

une réponse ?

▼?

si 2n=N ( au moins égal à 4, sinon on ne peut rien faire) est le nombre de verres, le verre vide doit parcourir au moins tous les verres ( alternativement Lille-Marseille)  avant le dernier (demi) vidage,
donc cela fait N+1 opérations. ici 23 avec n = 11.
Sauf erreur.

Alain

Dernière modification par bridgslam (13-12-2024 12:26:09)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 348

Re : Le bar de Fred

▼@bridgslam

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

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Le bar de Fred

Bonjour,

▼@Fred

A la première étape, on vide le contenu d'un demi-verre dans un autre demi-verre de même type de breuvage, sans aucun problème.
On continu par la suite sans problème, en faisant voyager le verre vide d'une place à l'autre...
Par exemple à la première étape ( où les n de Marseille sont tous à gauche, les n de Lille  tous à droite ):
Le n°1 rend plein le n°2, ensuite le n° n+1 devient vide en étant transvasé dans le n°1 ( vidé à l'opération précédente) etc

Bonne journée
A.

Dernière modification par bridgslam (13-12-2024 12:30:02)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 348

Re : Le bar de Fred

▼@bridgslam

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.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Le bar de Fred

Bonjour

▼détails @Fred

Par exemple  1   2   3  4
                      L   L   M  M

vidage de 1 dans 2 , 1 devient vide, vidage de 3 dans 1 , 3 devient vide , vidage de 2 entier dans 3, 2 devient vide, vidage de 4 dans 2.
La dernière (et cinquième) opération consiste à vider la moitié de 3 dans 4.

On n'a pas fait de mélanges, ou alors je n'ai rien compris à la question ?

A.

Roro

Membre expert

Inscription : 07-10-2007

Messages : 1 801

Re : Le bar de Fred

Salut,

Je pense que je suis d'accord avec bridgslam...
mais je n'ai pas de preuve que c'est optimal.

Roro.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Le bar de Fred

Bonsoir,

Chaque verre devant changer de liquide, sans mélange, il doit forcément être vidé au moins une fois.
Dans ces échanges chaque verre est vidé exactement 1 fois et chaque vidage compte pour une autre  étape.

A.

Glozi

Invité

Re : Le bar de Fred

Bonsoir,

▼proposition

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 !

Bonne soirée

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Le bar de Fred

Bonjour,

▼une jolie récurrence

On peut raisonner aussi par récurrence, et il semble qu'il faille rajouter 3 étapes ( comme en informatique il faut 3 mouvements avec l'aide d'une variable annexe quand il est impossible d'échanger directement les deux concernées ) en rajoutant 1 verre de chaque catégorie ( donc avec N+2 verres) mais on se vole en fait d'une étape par rapport au rang N , car au lieu de vider à la fin un verre plein à moitié dans le verre vide du même écusson ( qui clôturait l'affaire au rang N), on peut directement le vider entièrement dans le verre vide de l'autre écusson, disponible au rang N+2, en gagnant 1 étape.
Au final, si le rang N conduisait à N+1 opérations , au rang N +2,
Il suffit d'en rajouter 2 ( 3-1 en tenant compte du raccourci qui épargne une étape inutile), donc cela donne N+1 +2 = N+3 manoeuvres licites au rang N+2, la propriété est vérifiée: toujours une manœuvre de plus que le nombre de verres.
Donc 4 ->5 vérifiable, puis 6 -> 5+2=7, 8 ->7+2=9, ....., 22 -> 23.

A.

Dernière modification par bridgslam (14-12-2024 02:09:33)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Le bar de Fred

Bonjour ,

Salut,
...
mais je n'ai pas de preuve que c'est optimal.

Roro.

▼optimisation

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.

A.

Dernière modification par bridgslam (15-12-2024 09:57:38)

Zeus20

Membre

Inscription : 13-12-2024

Messages : 9

Re : Le bar de Fred

Bonjour,

▼Ma réponse

Vider un verre de pastis (à moitié plein) dans un verre vide.

Vider un verre de bière (à moitié plein) dans le verre maintenant vide.

Vider le verre de pastis (à moitié plein) dans le verre de bière (à moitié plein).

Répéter ces étapes pour chaque paire de verres.

En suivant cette méthode, Fred aura besoin de 22 manoeuvres au minimum, car chaque verre doit être vidé et rempli une fois

Dernière modification par yoshi (15-12-2024 09:26:10)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Le bar de Fred

Bonsoir ,

@Zeus

C'est pas faux, c'est sûr qu'en dessous de 22 opérations on échouera, mais en dessous de 23 aussi !
Au mieux avec 22, on termine avec 1 plein et 1 vide du même breuvage, ce n'est pas vraiment le but.
Par-contre c'est la seule option de chaînage à coût minimum si on rajoute deux verres supplémentaires à permuter car ça nécessite un verre de transit : voir le fonctionnement de la récurrence dans un post précédent

A.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 348

Re : Le bar de Fred

Bravo à tous, et en particulier à Bridgslam !