salut

 Cliquez pour afficher

pour     9        8         21    -->on double l'urne du milieu avec la 3ieme
-->       9       16       13     ---> on double la 3ieme avec celle du milieu
-->       9           3        26   ---> on double celle du milieu avec la premiere
-->       6          6          26    ----> et pour finir on double celle du milieu avec la premiere  ou la premiere avec celle du milieu et on obtient :
             0           12        26           ( on a donc une urne vide)
              

dommage de ne pas blanker et les laisser les autres réfléchir ... comme d'hab ...

Bonjour à tous!

Le problème posé est voisin du vieux problème des "trois cruches".
Ce problème a fait l'objet d'une épreuve écrite du Concours Commun de Centrale.
Voir sur le site du Concours Centrale Supélec , à la page des "rapports et sujets",
l'épreuve de Mathématiques2 de la filière TSI de 2014.
On y présente une méthode généralisable à ces problèmes de transvasements entre trois récipients, basée sur des endomorphismes de l'espace vectoriel R^6.

>> carpediem

 Cliquez pour afficher

bien, exemple facile. Mais l'exemple aurait pu être 887, 79, 491 cm³ pris au hasard....
Reste à définir une méthode générale...

>> rogerd : vieux problème , c'est vrai. mais bien moins général que l'étude proposée sur le site du Concours Centrale Supélec , à la page des "rapports et sujets",
l'épreuve de Mathématiques2 de la filière TSI de 2014.
et une méthode généralisée à tous contenus initiaux en est de formulation bien plus simple.

>>flight : j'ai manqué votre réponse sous blank, Mon commentaire fait à carpediem (à 15;22) était pour vous...

ce serait un bon probleme à  programmer

>> flight : Oui, en démontrant que le programme va aboutir (s'arrêter avec une suite de manipulations finie) quels que soient les contenus initiaux...
Un programme de ce type existe.

voila le programme

 Cliquez pour afficher

Citation :
Sub compensation()

t = Array(8, 9, 21)
p = Application.Max(t)
  q = Application.Min(t)

1:
    a = ""
  
  For i = 0 To UBound(t)
   If t(i) = q Then
   t(i) = Replace(t(i), Val(t(i)), 2 * Val(t(i)))
   End If
  Next
  
  For j = 0 To UBound(t)
  If t(j) = p Then
  t(j) = Replace(t(j), Val(t(j)), Val(t(j)) - q)
  End If
  Next
  
  For n = 0 To UBound(t)
  If t(n) <> "" Then
  a = a & " " & t(n)
  End If
  Next
  MsgBox a
  Erase t
  t = Split(a, " ")
  'mise en ordre des elements et verification :
  For u = 0 To UBound(t) - 1
   For v = u + 1 To UBound(t)
    If Val(t(u)) > Val(t(v)) Then
    c = Val(t(u))
    b = Val(t(v))
    t(u) = Replace(t(u), Val(t(u)), b)
    t(v) = Replace(t(v), Val(t(v)), c)
    End If
   Next
  Next
  p = t(UBound(t))
  q = t(1)
  If (t(1) = t(2) Or t(1) = t(3) Or t(2) = t(3)) Then
  Exit Sub
  Else
    GoTo 1
  End If
  

End Sub

testé sous excel vba , il s'arrete lorsque deux urnes se retrouvent avec la meme quantité

bien sur il est possible de modifier les valeurs de départ

oups ! oublié de blanker  , dommage qu'on puisse pas remanipuler un message deja posté

non mais flight, il te faut une secrétaire !!

>>wham
L'idée du sujet de Centrale était de montrer qu'on peut traiter un tel problème avec les techniques de l'algèbre linéaire dans R^6:
3 variables pour les volumes occupés par l'eau et 3 variables pour les volumes vides.
A chaque transfert de liquide d'une cruche dans une autre on associe un endomorphisme de R^6.

Par ailleurs, la dernière partie de l'énoncé faisait appel à l'informatique (vérification d'un programme résolvant le problème posé).

Re Bonjour,

>>flight :

 Cliquez pour afficher

j'ai des scrupules à être un peu sévère, mais de ma pratique professionnelle (passée) il ressort :
               Un programme non commenté passe d'emblée à la poubelle.

Si la méthode adoptée est : égaliser les contenus de deux des récipients, il faut (dé)montrer comment le programme atteint cet objectif (ce qui est surement le cas) sans tourner indéfiniment.
Tout au moins indiquer en clair les différentes étapes suivies par le programme.

Dans votre exemple la ligne 6 13 9 est surement 16 13 9. je n'ai pas bien saisi le jeu entre p et q dans votre grande boucle (avec un goto )

mes sieurs un lien direct vers ce sujet serait la bienvenue ...

merci par avance

..quelques commentaire de mon programme pour vham

Citation :

 Cliquez pour afficher

t = Array(11, 15, 21)   'chargement des valeurs dans un tableau

p = Application.Max(t)  ' valeur maxi du tableau dans une variable p
q = Application.Min(t)  ' valeur min du tableau dans une variable q

1:
    a = ""      ' variable cumulative de présentation des resulats  initialisée vide
  ' recherche de q dans le tableau pour le modifier et lui donner 2 fois sa valeur
  For i = 0 To UBound(t)
   If t(i) = q Then
   t(i) = Replace(t(i), Val(t(i)), 2 * Val(t(i)))
   End If
  Next
  ' recherche de p dans le tableau pour le modifier et lui donner sa valeur moins q:
  For j = 0 To UBound(t)
  If t(j) = p Then
  t(j) = Replace(t(j), Val(t(j)), Val(t(j)) - q)
  End If
  Next
  
  For n = 0 To UBound(t)
  If t(n) <> "" Then
  a = a & " " & t(n)   'chargement des nouvelles valeurs
  End If
  Next
  MsgBox a  'présentation des valeurs obtenues
  Erase t  'ecrasement du tableau initial
  t = Split(a, " ")   ' a est transformé en tableau t
  'mise en ordre des elements :
  For u = 0 To UBound(t) - 1
   For v = u + 1 To UBound(t)
    If Val(t(u)) > Val(t(v)) Then
    c = Val(t(u))
    b = Val(t(v))
    t(u) = Replace(t(u), Val(t(u)), b)
    t(v) = Replace(t(v), Val(t(v)), c)
    End If
   Next
  Next
  p = t(UBound(t))  ' maxi du nouveau tableau
  q = t(1) 'mini du nouveau tableau
  If (t(1) = t(2) Or t(1) = t(3) Or t(2) = t(3)) Then  'contraintes d'arret
  Exit Sub
  Else
    GoTo 1  'sinon on reboucle avec le nouveau tableau
  End If

testé avec d'autres valeurs ca à l'air de bien marcher

Bonsoir,

>> flight

 Cliquez pour afficher

Si j'ai bien compris vous ordonnez croissant les 3 nombres
puis vous doublez le plus petit et compensez sur le plus grand
et recommencez...
par exemple :
12 15 18  qui donne 24 15 6 que vous ordonnez croissant
6 15 24  qui donne 12 15 18 et votre programme ne s'arrêtera pas...
votre programme traduit en Python :

t=[8,9,21] #données initiales dans une liste de 3 nombres entiers
while True: #boucle générale
    t[2]-=t[0] #diminuer le nombre le plus grand
    t[0]+=t[0] #doubler le nombre le plus petit
    print(t) #afficher
    t.sort() #ordonner la liste des 3 nombres
    if t[0]==t[1] or t[0]==t[2] or t[1]==t[2]:break #tester condition de fin

Pourquoi vous dites que mon programme ne s arrêtera pas ??.. Je vous ai montré un exemple de traitement avec des valeurs..

Mon programme s arrête des qu on a deux urnes identiquement remplies

Bonjour,

>> carpediem : Ubound(t) c'est le plus grand index du tableau qui contient donc Ubound(t) + 1 valeurs.

>> flight : je vous montre que votre programme tournera indéfiniment avec les valeurs initiales 12 15 18, car la succession des trois valeurs sera 24 15 6, 12 15 18, 24 15 6,..... Votre méthode ne répond pas au problème
           "Une méthode générale est demandée, pour tous contenus."

Avant de donner une solution, je précise les indices donnés précédemment pour une méthode générale :
utiliser un principe simple accessible aux lycéens (division euclidienne)
Ensuite une méthode facile à mettre en oeuvre  est utilisée dans un jeu d'allumettes célèbre.

Je vais tester ça, vham et vous dirait ça

Carpediem pourrais tu m expliquer ceci :

"cependant je dois dire que flight programmant ??"

C est quoi?...du rabaissement ?

>>carpediem

https://www.concours-centrale-supelec.fr/CentraleSupelec/2014/TSI/sujets/2011-086.pdf

Bonjour à tous.

 Cliquez pour afficher

Soient . On suppose .  On effectue des divisions euclidiennes successives et il vient :

on pose

on pose

On construit donc une suite strictement décroissante de reste entiers. Il va donc arriver un moment où elle va arriver à 0 et on pourra vider entièrement l'une des deux urnes.

Exemple :
102  16      .... 102 = 16*6 + 6
6        112   .... 112 = 18*6 + 4
114  4         .... 114 = 28*4 + 2
2         116  .... 116 = 58*2
118   0

Avec des nombres premiers (et un de Fermat)
257 17     ....  257 = 15*17 + 2
2        272 ....  272 = 136*2
274  0

Bonjour,

>> jsvdb

 Cliquez pour afficher

bien pour le principe de base : Utiliser les restes en valeurs strictement décroissantes
Reste à préciser comment s'organisent les transferts de liquide

Bonjour vham

 Cliquez pour afficher

Ah oui, pas de soucis :

A l'étape n, on transvase de la plus pleine vers la plus vide du montant du quotient trouvé dans la division euclidienne fois le volume de la moins vide

Exemple :

Urne 1 : 50 - Urne 2 : 173 avec 173 = 3*50 + 23 alors je transvase 150 de l'urne 2 vers l'urne 1. Résultat après opération :

Urne 1 : 200 - Urne 2 : 23 et ainsi de suite

Erratum :

 Cliquez pour afficher

A l'étape n, on transvase de la plus pleine vers la plus vide du montant du quotient trouvé dans la division euclidienne fois le volume de la plus vide ou de la moins pleine

Plus que t'es moins vide, plus que t'es plus plein, en gros

Bonjour.

>> jsvdb :

Bonjour,

>> jsvdb :

 Cliquez pour afficher

L'énoncé commence ainsi : trois urnes ....
Savoir s'il y a une solution ou non pour deux ne répond pas forcément au problème.

rogerd : merci

flight : nul rabaissement : seulement le constat que tu utilises un langage ... disons un peu désuet ... voire ""peu connu"" (enfin "peu utilisé" dans le milieu éducatif en tout cas) et je rejoignais seulement vham dans sa remarque blanckée de 17h52 plussoyée par jsvdb à 11h27 ...

je ne demande pas de détailler la logique de l'algo (ou plus tard) mais de préciser certains mots du langage

c'est l'avantage de l'algo qui peut être compris par tout le monde ... mais qui alors peut faire comprendre la logique de la solution

donc un pgm ok ... mais avec qq éléments d'explication surtout pour le vocabulaire utilisé

@ vham

 Cliquez pour afficher

Je suis bien d'accord, mais comprendre comment ça fonctionne sur deux va aider à trouver comment résoudre trois.

Maintenant, ma conjecture est fausse : admet une solution immédiate et n'est pas nécessairement une puissance de 2.

Donc on (je) continue mes recherches

Je pense avoir résolu complètement le problème à deux urnes :

 Cliquez pour afficher

Soit L le nombre d'unités de liquide du départ.
Pour tout entier a et b, je note le fait qu'une des deux urnes contienne unité(s) (ou des billes) de liquide et l'autre unité(s).
Ce n'est donc pas le "-" de soustraction, sauf avis contraire.

Si L = 0, le problème est ipso facto résolu.

Sinon, le but étant d'arriver à équilibrer les urnes selon le procédé décrit initialement, il est clair que si L n'est pas divisible par 2, alors le problème est irrésoluble. On suppose donc nécessairement que

On pose . P existe car

Autrement dit, est le plus grand entier tel que divise et ne divise pas .

Voyons les premiers cas :


Alors la seule possibilité de départ donnant une solution, est .
Par exemple, avec L=38 litres, la seule possibilité est de mettre 19 litres dans chacune des urnes pour avoir une solution.


Alors outre la solution de dessus, on a également la possibilité et c'est la seule.
Par exemple, avec 76 litres, on peut avoir comme possibilité ou bien .
Pour toute autre combinaison de départ, le problème n'a pas de solution.


Outre les deux solutions de dessus, on a également la possibilité et c'est la seule.
Par exemple, avec litres, on a comme départs : , et : ce sont les seules.
Pour toute autre combinaison de départ, le problème n'a pas de solution.


Outre les trois solutions de dessus, on a également la possibilité et c'est la seule.
Par exemple, avec litres, on a comme départs : , , et : ce sont les seules.
Pour toute autre combinaison de départ, le problème n'a pas de solution.

: on commence à voir apparaître un nœud.
Outre les quatre solutions de dessus, on a également les deux possibilités , mais aussi .
Par exemple, avec litres, on a comme départs :
, , , , et : ce sont les seules.
Pour toute autre combinaison de départ, le problème n'a pas de solution.

: outre toutes les solutions précédentes, nous avons solutions supplémentaires.

Je ne détaille pas la tête théorique des solutions. Mais par contre, le procédé d'obtention :

Si est une possibilité du problème pour un certain alors elle va générer deux possibilités pour .

En supposant alors première possibilité générée est .

La seconde est générée en posant le système

D'où la seconde possibilité :

Donc, à partir de P = 4, on passe des solutions de à celle de par :

- en reprenant les solutions

- divisant par 2 les plus petites jarres de P - 1 et mettant leurs contenus dans l'autre

- soit en résolvant le problème matriciel

Exemple :

pour , on avait la possibilité . Alors pour passer  à , cette possibilité va générer les deux suivantes :





Mais on avait également la possibilité . Alors pour passer  à , cette possibilité va générer les deux suivantes :





Et par suite, on a trouvé les 4 solutions possibles de départ qui font que le problème a une solution.

Exemple pour 320 = 2*160 avec P = 5 : les solutions sont les suivantes.

P = 0 donne

P = 1 donne

P = 2 donne

P = 3 donne

P = 4 donne ou

                           qui embraye sur

P = 5 donne ou
  
                           qui embraye sur ou

                           qui embraye sur ou

                           qui embraye sur

Il y  a donc 10 possibilités de départ quand n est divisible par 32 pour que le problème soit résoluble.

_________________________________________________
Inversement, on donne les jarres de départ . Peut-on en vider une.

Réponse : d'où et . Les seuls possibilités sont ou ou   ou

Donc, pas de solutions.

Il reste maintenant à voir comment ce procédé va pouvoir aider à résoudre le problème avec trois urnes.

Bonjour,

>> jsvdb : un indice simple :

 Cliquez pour afficher

prenons a=3 et b=32 pour exemple
Divisons b par a, q=10 et r=2. On veut garder r dans le vase B
Or en binaire q s'écrit 1010 et si on veut verser dans A, il faut que A reçoive 3 puis 6, 12 et 24

@vham

 Cliquez pour afficher

J'avoue ne pas comprendre ce que tu souhaites me dire
Le problème n'a pas de solutions puisque 3 + 32  = 35 qui n'est pas divisible par 2

Bonne nuit,

>> jsvdb : Solution

 Cliquez pour afficher

Ne pas oublier qu'il y a 3 vases A, B, C de contenus respectifs a, b, c que l'on a ordonnés a < b < c et que l'on veut obtenir que B ne contienne plus que r  provenant de b=aq+r
prenons a=3 et b=32 pour exemple, c étant supérieur à 32
Divisons b par a, q=10 et r=2. On veut garder r dans le vase B
Or en binaire q s'écrit 1010 et si on veut verser dans A, il faut que A reçoive 3 puis 6, 12 et 24
Il suffit d'examiner les bits successifs de q en commençant par le bit de poids faible ( à droite )
si ce bit est 0 on verse depuis C pour doubler A,
si ce bit est 1 on verse depuis B pour doubler A,
il ne restera plus que r dans B. On reordonne A, B, C pour diminuer (jusqu'à 0) les restes dans B.

Bonjour,

Rappel : Trois urnes de contenances illimitées contiennent chacune un nombre entier (en cm3) de liquide.
On ne peut transférer d'une urne dans une autre que la quantité présente dans l'urne réceptrice.
Pouvez-vous vider entièrement une des trois urnes ?

Solution en Python 3.5

def vidage(L): # les contenus de 3 vases A,B,C sont dans une liste indicée de 0 à 2
    print( L)
    while not L[1]==0: #tant que B ne sera pas vide
        L=sorted(L) # contenus ordonnés croissants : a <= b <= c
        q=L[1]//L[0] # quotient dans b = aq + r division euclidienne
        lg=len(bin(q))-2 #longueur de q exprimé en binaire
        for i in range(lg): #index des bits de q
            # transfert dans A depuis B si bit=1 ou depuis C si bit=0
            # le membre de gauche n'est mis à jour qu'après calcul à droite
            L[0],L[2-((q>>i)&1)]=L[0]*2,L[2-((q>>i)&1)]-L[0]  
            print( L)
vidage([887,79,491]) # pour exemple
print("***************")
vidage([8,9,21]) # pour exemple