Forum de mathématiques - Bibm@th.net

Bonsoir,

@ zorglub : c'est plutôt à freddy de répondre....
Je veux bien reprendre le problème, mais avec des notations non ambigües, et si l'on dit à quels emplacements on repose les trois boules pesées.

Bonjour,

Le lien donné par Zorglub : https://www.gerad.ca/Charles.Audet/PUB/15billes.pdf
Etudie le problème suivant :
We are given a set of marbles, whose weights are all different. The only way to distinguish them is to use a special kind of scale. The scale has three trays and each can accept exactly one marble. The scale then indicates which is the heaviest, the lightest and consequently the middle one of the three marbles.

Le problème pose par freddy est :
J'ai à ma disposition un dispositif curieux : à chaque fois que je lui transmets trois boules, il me les rend classées dans l'ordre croissant de leur poids (mais sans indiquer leur valeur, oubli probable de son concepteur).

Je doute que le lien cité étudie exactement le même problème que freddy avait proposé, car, dans ce lien la balance utilisée a 3 plateaux, MAIS elle indique quel plateau contient la bille la plus lourde, lequel la bille la plus légère…La pesée conserve apparemment la "provenance" de chacune des 3 billes, ce que ne donne pas la pesée de freddy.
Voir par exemple comment sont triées 6 billes en 5 pesées page 4…

Sauf incompréhension de ma part !

salut
la solution proposée par l'auteur de l'énigme se trouve dans le poste #99.

Bonjour,

J'ai depuis longtemps, en poche, deux jeux de petits cartons numérotés de 1 à 15; alors, quand j'ai l'occasion, je cherche « la solution » (23 coups).

J'ai « étudié » la solution apportée par Freddy (en 23 coups) mais j'arrive, en gros, aux mêmes remarques et questions formulées par Totomm. Ça m'a relancé donc.

En reparcourant les dernières avancées de Jpp et les remarques d'Amatheur, je ne sais plus trop à quels résultats il est parvenu à coup sûr. (28? 27? 24?).

J'arrive à ordonner (sans marquage) les 15 boules en 27 passages à la machine (ou tris).
Je travaille simultanément avec deux configurations ordonnées en trois lignes de cinq cartons; l'une est ordonnée suivant  les colonnes, l'autre suivant les lignes (deux configurations extrêmes).
Cette façon de travailler m'a permis de perfectionner la méthode que j'ai déjà exposée plus avant.
Ordonnancement des lignes et colonnes  =>
Configurations après  4*3 + 5 = 17 tris:
A                                                         B
1    2    3    4    5                                         1    4    7    10    13
6    7    8    9    10                                       2    5    8    11    14
11    12    13    14    15                             3     6    9    12    15
On écarte    1 et 15
On déplace la ligne 1 de deux rangs à gauche
On déplace la ligne 3 de deux rangs à droite
Pour A:
        2    3    4    5
            6    7    8    9    10
                    11    12    13    14   
Pour B:
        4    7    10    13
            2    5    8    11    14
                    3    6    9    12
Résultat:
    1......................15
On trie les trois diagonales
Configurations après  17+3 = 20  tris:
Pour A:
        2    3    4    5
            6    7    8    9    10
                    11    12    13    14   
Pour B:
        4    3    6    9
            2    5    8    11    14
                    7    10    13    12   
On teste les trois boules de gauche et les trois boules de droite.
Pour A:
    2    3    6                        10    13    14
Pour B:
    2    3    4                        12    13    14
On sort 2, 3 et 13, 14
Résultat:
    1 2 3..................13 14 15
Configurations après  17+3+2 = 22  tris:
Pour A:
            6    4    5
                7    8    9   
                    11    12    10   
Pour B:
            4    6    9
                5    8    11   
                    7    10    12   
On trie les trois boules verticales.
On trie les trois boules ligne 1.
On trie les trois boules ligne 3
On retire la boule extrême gauche.
On retire la boule extrême droite.
Configurations après  17+3+2+1+1+1 = 25  tris:
Pour A:
                5    6
                7    8    9   
                    10    11   
Pour B:
                6    7
                5    8    11   
                    9    10
Résultat:
    1 2 3 4................12 13 14 15
Il nous reste a trier les deux boules ligne 1 et la boule de gauche ligne 2 et
les deux boules ligne 3 et la boule de droite ligne 2.
La dernière boule vient combler les deux versants après 27  tris.

Je continue à chercher meilleure solution.

A+-*/

Salut,

une toute petite suggestion : quand, reprenant tes notations, tu fais peser 1, 5 et 8 et qu'on te rend dans l'ordre 5, 8 et 1, qui t'empêche de reprendre les trois premiers triplets et les mettre dans le sens (1g,2g,3g) ; (4g,5g,6g) ; (13g,14g,15g)  ?

Salut,

non, non, le 1 du début n'est peut être pas le 1 de la fin, on peut permuter les premiers triplets si besoin est.

Salut,

bon, alors comment fait on en 23 pesées maxi ?

5 premières pesées permettent d'obtenir un classement du type :

(1,2,3) ; (4,5,6) ; (7,8,9) ; (10,11,12) ; (13,14,15).

Bien entendu, les numéros sont là pour aider à bien suivre le raisonnement. A chaque étape, on change les numéros implicites des boules pour maintenir le classement obtenu.

Ensuite, on a besoin de 4 étapes au plus pour classer les boules médianes, savoir les triplets (2,5,8) ; (5,11,14) ; (2,11,14) et (8,11 14).

En renumérotant correctement les boules, on sait qu'on a obtenu l'ordre suivant 2 < 5 < 8 < 11 < 14 et donc le classement partiel suivant : 1 < 2 < 5 < 8 < 11 < 14 < 15.

En faisant peser le triplet (1,2,4) on sait où va se ranger la boule 4 ; en faisant peser le tripler (12,14,15), on sait où se range la boule 12.

Total des pesées : 5+4+2 = 11.

En renumérotant implicitement, on a le classement partiel : 4 < 5 < 8 < 11 < 12 < 14 < 15

Pour savoir ou se range la boule 3, on soumet à la pesée le triplet 3, 8 et 14. Selon la réponse, une seconde et dernière pesée est nécessaire pour déterminer son poids comparatif.

En renumérotant le cas échéant, on a en particulier : 1 < 2 < 3 < 4 < 5 < 8 < 11 < 12. On peut alors, en deux pesées supplémentaires, ranger la boule 13, en commençant par la comparer aux boules n° 3 et n° 8 ci dessus.

Une seconde pesée permet de déterminer l'ordre partiel relatif suivant 3 < 8 < 11 < 12 < 13 < 14 < 15.

Ceci permet de positionner la boule n° 6 en deux étapes.

Ceci fait, on trouve en deux étapes supplémentaires le placement de la boules n° 10 dans le groupe (1,2,3,4,5,6,8,13), puis en deux étapes supplémentaires le placement de la boule n° 9 parmi le groupe (3,6,10,11,12,13,14,15) et on termine en deux dernières pesées la position de la boule n° 7 dans le groupe (1,2,3,4,5,6,10,13).

Total 11 + 12 = 23 pesées.

PS : je me suis fait un peu beaucoup aidé par ma petite famille !!!

salut.

je me demande si on doit ranger les boules sur les lignes ou sur les colonnes ; à moins qu'il faille définir une liste de 23 triplets qui sera nécessaire et suffisante pour que quelque soit la position de chacune des 15 boules sur la matrice ou peut-etre sur une autre géomètrie comme le triangle ou le carré écorné 4 x 4 -1 , on obtienne un ordonnancement parfait des 15 boules . 

Pour ça je pense à un truc que je vais exploiter.  Je duplique ma matrice 3 x 5 et je l'éparpille façon puzzle comme ceci:

[tex]\begin{matrix}a&b&c&a&b&c&a&b&c\\d&e&f&d&e&f&d&e&f\\g&h&i&g&h&i&g&h&i\\j&k&l&j&k&l&j&k&l\\m&n&o&m&n&o&m&n&o\\a&b&c&a&b&c&a&b&c\\d&e&f&d&e&f&d&e&f\\g&H&i&g&H&i&g&h&i\\j&k&L&j&k&l&j&k&l\\M&n&o&m&n&o&m&n&o \end{matrix}[/tex]

à partir du point M  je vais tracer toutes les droites passant par la plus proche des boules dans la matrice d'origine 3 x 5. ça me rappelle un autre problème récemment posé.

ces droites ont pour coefficients directeur [tex] 0  , \frac12 , 1 , \frac32 , 2 , 3 et 4[/tex]

à partir de ces droites je prend par exemple les boules L & H  se situant sur la droite à coefficient directeur 0.5 .

je les teste et je suis une logique de placement  comme : plus légère en haut   ou à gauche  et plus lourde au dessous ou  à droite.
je vais donc chercher ces 23 triplets puis tester ensuite.
                                                                                           à plus.

(...)