Forum de mathématiques - Bibm@th.net

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : A faire perdre la boule à totomn !!!

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.

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : A faire perdre la boule à totomn !!!

Bonjour,

Je réitère :

Si dans les positions de 1 à 15 on a , par exemple, les boules 13g, 14g, 15g, 1g, 2g, ,…,12g
(g étant mis pour grammes), les 5 premières pesées qui permettent d'obtenir un  classement du type :
(1,2,3) ; (4,5,6) ; (7,8,9) ; (10,11,12) ; (13,14,15) donnent, dans cet exemple,
(13g,14g,15g) ; (1g,2g,3g) ; (4g,5g,6g) ; (7g,8g,9g) ; (10g,11g,12g)

Si maintenant, en 4 étapes, on classe les boules médianes,
on sait qu'on a obtenu l'ordre suivant :
2 < 5 < 8 < 11 < 14 contenant (sous forme cachée) respectivement 2g, 5g, 8g, 11g, 14g.

et il reste inchangé : : (1,_,3) ; (4,_,6) ; (7,_,9) ; (10,_,12) ; (13,_,15) contenant (sous forme cachée)
respectivement : (13g, _,15g) ; (1g,_ ,3g) ; (4g,_ ,6g) ; (7g, _,9g) ; (10g,_ ,12g)

Comment, donc, assurer que le classement partiel suivant , après 9 pesées, :
1 < 2 < 5 < 8 < 11 < 14 < 15 est correct sans opération de pesées supplémentaires portant sur les boules 1 et 15 ?

Cordialement

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : A faire perdre la boule à totomn !!!

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)  ?

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : A faire perdre la boule à totomn !!!

re-Salut freddy : Je ne cherche qu'à comprendre la méthode expliquée au post #99...

D'abord la 6ème pesée porte sur 2, 5 et 8 et non  sur 1, 5 et 8 et les notations sont celles du post #99 ainsi que les 9 premières pesées.

Les notations en 1g, 2g, ... sont toujours les valeurs cachées des boules qui sont indiscernables !
Changer la position des triplets, à l'aveugle, n'apporte ni n'enlève rien sur ce qui est des ordres partiels obtenus!

Mais quand on pèse 2, 5, 8 et si on appelle toujours 2, 5, 8 les boules rendues dans cet ordre après pesée,
on peut juste dire que la boule 1, qui était plus légère que la 2 dans la première pesée de 1, 2, 3,  est maintenant plus légère que la boule 8, et pas forcément plus légère que la boule maintenant appelée 2.

Juste encore  : Il serait remarquable que l'on puisse faire mieux sans marquer les boules plutôt qu'en les marquant, ce serait une révolution dans la théorie de l'information ! mais le meilleur résultat donné en marquant les boules n'est sans doute pas l'optimum !

Cordialement

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : A faire perdre la boule à totomn !!!

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+-*/

Arioch

Invité

Re : A faire perdre la boule à totomn !!!

Bonjour !

J'ai survolé les messages de ce sujet qui m'a bien intéressé et pour lequel j'aimerais essayer une approche algorithmique basée sur des techniques utilisées en intelligence artificielle... (au moins pour trouver des bornes supérieures sur la solution optimale). Je constate que la discussion s'est brutalement arrêtée en avril 2012. Quelqu'un sait s'il y a eu des avancements depuis et quelles les meilleurs bornes connues à ce jour sur le nombre optimal de pesées (dans le pire des cas) ?

Merci d'avance pour vos réponses.

amatheur

Membre

Inscription : 02-10-2011

Messages : 299

Re : A faire perdre la boule à totomn !!!

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

Zorglub

Invité

Re : A faire perdre la boule à totomn !!!

La solution #99 n'est pas optimale. 

Le lien suivant
https://www.gerad.ca/Charles.Audet/PUB/15billes.pdf
mène à une publication dans la revue Mathematical Gazette qui détaille un façon de procéder qui mène à 20 pesées, dans le pire des cas.  Mais on ne sait toujours pas si cette solution est optimale.

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : A faire perdre la boule à totomn !!!

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 !

Zorglub

Invité

Re : A faire perdre la boule à totomn !!!

Totomm,

je crois que tu te trompes.  Lorsque Freddy affirme que la balance rend les boules classées, il ne dit pas qu'on perd la provenance.  Voici un extrait du message 99 de Freddy:

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.

Les 5 premières pesées ne posent pas de problèmes.  Les 4 suivantes classent les boules médianes.  En renumérotant, la 2 est désormais la plus légère des médianes. Mais si on perdait la provenance, alors il serait impossible de savoir laquelle entre la 1 et la 2 est la plus lourde.  Or, Freddy affirme qu'on a toujours le classement partiel 1 < 2 < 5 < 8 < 11 < 14 < 15.

Et donc, ceci suggère que la provenance n'est pas perdue.

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : A faire perdre la boule à totomn !!!

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.