salut

notons a, b, c, d, et e les 5 pièces et leur poids

pesée 1 : a et b  on suppose a < b

pesée 2 : c et d  on suppose c < d

pesée 3 : b et c  :

   si b < c

    si c < b on pèse a et c et

p... fait c... mauvaise manip !!


notons a, b, c, d, et e les 5 pièces et leur poids

 Cliquez pour afficher

pesée 1 : a et b  on suppose a < b

pesée 2 : c et d  on suppose c < d

pesée 3 : b et c  :

   si b < c   alors a < b < c < d

    si c < b on pèse a et c et b et d    (pesée 4 et 5)

dans tous les cas les pièces a, b, c et d sont ordonnées

à numérotation près supposons qu'on ait a < b < c < d

pesée 6 : c et e :

   si c < e  alors pesée 7 : d et e

   si e < c  alors pesée 7 : b et e

      si b < e fini

      si e < b alors pesée 8 :  a et e

il faut donc huit pesée au maximum pour comparer ces cinq pièces

 Cliquez pour afficher

peut-être peut-on améliorer d'une pesé en introduisant la pièce e à partir des pesées 4 et 5

Bonjour,
de façon théorique
avec 5 pièces on a 5! = 120 façons de les ordonner
chaque pesée donne 2 résultats possibles (vu que le cas "=" n'existe pas)
2⁷ = 128 > 120
donc 7 pesées devraient théoriquement suffire
lesquelles ? c'est une autre paire de manches...

Bonjour à tous les deux

@Carpediem : ça marche , peut-on faire mieux ?
@Mathafou : je ne comprends pas ton calcul , en plaçant par exemple les pièces A et B sur un plateau et C sur l'autre , les trois positions de la balance sont possibles .

Imod

mathafou et moi même avons raisonné sur des pesées d'une pièce sur chaque plateau

c'est un classique ... que j'ai oublié : chaque pesée divise par 2 le nombre d'issues

on devrait donc pouvoir y arriver avec sept pesées ...


mais tu proposes une alternative intéressante avec deux pièces dans un plateau et une dans l'autre qui laisse le choix à trois issues donc peut-être peut-on faire plus mieux bien


to be continued ...

en considérant toujours le pire cas

 Cliquez pour afficher

on peut aussi commencer par :

pesée 1 : a et b  on suppose a < b

pesée 2 : a et c  et on obtient a < c (pire cas)

pesée 3 : b et c   et les pièces a, b et c sont ordonnées

à permutation près on peut supposer a < b < c


pesée 4 :  b et d  :

si d < b alors on compare a et d   (pesée 5)
si b < d alors on compare c et d   (pesée 5)

dans tous les cas les pièces a, b, c et d sont ordonnées et comme pour ma première méthode il faut 5 pesées pour ordonner ces quatre pièces


à permutation près on peut supposer qu'on ait   a < b < c < d


si on veut finir en deux pesées c'est là qu'il faut agir différemment :

pesée 6 : a + e et c :

si a + e = c alors on a l'unique issue 1 + 3 = 4  ( 1 + 2 = 3 est impossible car a < b < c et 2 + 3 = 5 est impossible car c < d) donc a < b < e < c < d

si a + e < c alors c = 4 et on en conclut que a < e < b < c < d ou e < a < b < c < d et une pesée permet de conclure

si a + e > c alors  on a les issues 1 + 4 > 3  ou 2 + 3 > 4 ou  1 + 5 > 4

on peut conclure en une pesée

 Cliquez pour afficher

il semble même que "en moyenne" on conclut "presque" en 6 pesées

En partant de a<b<c<d , n'est-il pas plus simple de comparer a+d et b+c afin de savoir si a-c et d-b sont égaux à 2 ou 3 puis trouver la place de e en deux coup e ?

Imod  

Bonjour du Québec,

 Cliquez pour afficher

En trois pesées  de 4 pieces   ABCD on  classe par exemple
BADC ou BACD
Ce  qui donne soit 5432 soit 5431 soit 5321 soit 4321
4 /on doit peser B avec E  si  E>B --> E=5  B=4 A=3  
5/on classe D C  par exemple  D>C   on a   BACD=4321

Si E=4  B=5   on  change la  5/
5/   On a     BADC ou  BACD =5321
6/il reste  a classer  C et D

Bonjour,
Une stratégie consiste à essayer de diviser à chaque pesée les permutations possibles restantes après les résultats des pesées précédentes en trois tas de tailles les plus égales possibles suivant les trois réponses que peut donner la balance.
Au premier coup, mettre dans la balance deux pièces d'un côté, deux pièces de l'autre divise les 120 permutations en 48-48-24. On ne peut pas faire mieux.
Si la balance n'est pas restée à l'équilibre, on peut refaire une pesée en échangeant une pièce du plateau gauche avec une pièce du plateau droit, et les 48 permutations possibles d'après le résultat de la 1e pesée se divisent en 18-18-12. Pas trop mal.
Après, ça se corse.

En fait on peut faire en 7 étapes même en mettant une seule pièce par plateau mais les solutions sont pénibles à détailler . Je me demande si on arrive à faire en 6 étapes en acceptant plusieurs pièces sur un plateau . A priori ce n'est pas impossible .

Imod

Bonjour.

En utilisant les idées de GBZM, j'ai trouvé une solution en 5 pesées.

5 est un minimum théorique car . J'ai trouvé en 6 essais mais je n'ai pas encore tout essayé .

Imod

A la réflexion , la marge me semble extrêmement étroite pour réussir en 5 pesées car , on n'est pas loin de . De plus les premiers tris ne font pas des parts égales , tu as certainement trouvé une belle astuce

Imod

Je crois que je l'ai aussi en 5 pesées ( je n'y croyais pas ) .

On commence comme indiqué par GBZM  , on compare a+b avec c+d puis a+c avec b+d ce qui revient à comparer la mesure algébrique avec et . Dans le pire des cas il reste 18 possibilités que l'on peut réduire à 9 en comparant b et c . On reste donc avec par exemple : a<d , b<c et AD<BC  . On peut séparer les cas en trois parts égales en comparant a+d et b+c et on conclut aisément en une pesée pour un total de 5 .

Bien vu Perroquet

Imod