Forum de mathématiques - Bibm@th.net

Bonjour,

par exemple (c'est bien plus rapide quand le langage permet d'accéder bit à bit) :

s peut ensuite être complétée avec k, que s soit une liste ou un tableau ou un tuple ou une chaine de caractères...
dans l'exemple ci-dessus pour i=11 on a s=[7, 7, 0, 7, 0]  et k=3
Conformément à une séquence de pesées (définie manuellement) on va appliquer ces pesées aux suites
[3, 7, 7, 0, 7, 0]
[7, 3 ,7, 0, 7, 0]
[7, 7, 3 ,0, 7, 0]
[7, 7, 0, 3 ,7, 0]
[7, 7, 0, 7, 3 ,0]
[7, 7, 0, 7, 0, 3]
qui vont donner chacune une des positions possibles de l'objet [tex]p_3[/tex].
Ayant défini des classes d'équivalence (quant aux positions possibles) sur l'ensemble de n! permutations, les [tex]N.2^{N-1}[/tex] suites ainsi définies sont chacune un représentant d'une de ces classes.

Je n'aurais plus guère de temps en juin pour m'occuper de ce problème qui pour moi est bien délimité.

Salut à tous, même peu nombreux,

D'abord je souhaite un bon rétablissement à freddy, même si difficile....

Je détaille pour ne pas décevoir, en espérant être assez clair :

Soit donc N billes d'aspects extérieur indiscernables, dont les poids [tex]p_1,...,p_N[/tex] sont tous différents, mais si peu entre eux que seule une balance de précision spéciale peut les discerner. Ces billes sont sur N emplacements [tex]e_1,...,e_N[/tex]. On ne peut les peser que 3 par 3 en désignant 3 emplacements [tex]e_i <e_j<e_k[/tex] et la balance redonne les 3 billes triés par poids croissants que l'on replace dans cet ordre en [tex]e_i, e_j, e_k[/tex], SANS CONNAITRE l'emplacement d'origine des 3 billes.

On cherche un algorithme qui validerait une suite de pesées ordonnant les billes par poids croissants quelle que soit la permutation d'origine des N billes.
Pour suivre la position possible de chaque bille au fil des pesées, il faudrait soumettre la suite des pesées aux N! configurations de départ possibles.

Mais pour chaque bille de poids [tex]p_k[/tex], sa position après pesée ne dépend que de son poids relatif par rapport aux poids des  2 autres. On peut donc, pour cette bille, définir sur l'ensemble des (N-1)! permutations dans laquelle elle figure une relation d'équivalence
[tex]p_i =0\ si\ i<k\  et\ p_i=1\ si\ i>k[/tex]
On n'a donc plus à considérer, pour la bille de poids [tex]p_k[/tex], que les configurations ayant (k-1) fois 0 (ou(N-k) fois 1) parmi les [tex]2^{N-1}[/tex] configurations binaires formées de N chiffres appartenant à {0,1}.

l'algorithme de validation d'une séquence de X pesées de N billes consiste donc à :
Pour chaque nombre de 0 à [tex]2^{N-1}-1[/tex]
    Créer une suite S formée des 0 et des (1 remplacés par N+1)
    k=(nombre de 0 dans S) +1
    Dans chacun des emplacements de S insérer k
        appliquer chaque pesée à S et noter l'emplacement où se retrouve k

Dans sa simplicité cet algorithme fournit pour N billes un tableau de N emplacements possibles. La séquence est valide si chaque bille ne peut se retrouver qu'en un seul emplacement.

Salut à tous,

Sympa ce forum,, mais on peine à se retrouver parmi les nombreux intervenants. :-))
Et on répond bien à vos questions !!

re bonjour,

@ yoshi : j'ai posé le post #1 en toute bonne foi et je n'ai pas eu de réponse justifiée dans les interventions d'amatheur² ni de freddy.
Même si amatheur² se voulait plus précis que freddy...(voir le post #4 ci-avant.

êtes-vous vous-même parti prenante sur ce problème ?

En étudiant le problème que j'ai trouvé sur Bibmath, j'ai effectivement développé un algorithme pour savoir où pouvait ou ne pouvait pas se trouver chacune des 15 billes en suivant la suite des pesées.
Pas évident mais efficace si on évite de balayer les 15! permutations initiales des billes.
Je pourrai vous en donner la clé, mais ce qui m'importe maintenant c'est de savoir si ordonner 6 billes est fait en 5 ou 6 pesées maximum, et quelle suite de pesées est alors proposée !

C'est la meilleure réponse qui puisse être apportée à la question : les conditions de pesées de freddy sont-elles, ou non, celles traitées dans l'article de  CHARLES AUDET dans THE MATHEMATICAL GAZETTE.

Re bonjour,

@ freddy : Le problème est que vos conditions de pesées définies sur bibmath sont plus restrictives
que celles qui permettent d'ordonner toute permutation de 15 billes en 23 pesées au maximum.
Ce pourquoi je vous invite à donner votre suite de pesées pour le cas de 6 billes seulement.
Si vous ne le faites pas, c'est que vous esquivez une réponse franche au post #1 ci-avant.

Bonjour,

Le premier lien envoie vers un document .pdf parfaitement encore accessible.
Sinon, essayez une recherche avec : THE MATHEMATICAL GAZETTE  CHARLES AUDET

Mais pour prouver que votre problème correspond bien à 23 pesées pour 15 billes,
il vous suffit de donner la suite des pesées que vous proposez pour 6 billes : Facile n'est-ce pas !

Salut,

je suis désolé, mais je ne suis pas en état actuellement pour me plonger sur ce sujet, comme d'autres d'ailleurs, qui a intéressé bien du monde.
Dans quelques mois, je pense que je pourrais faire un point et répondre aux légitimes questions.
Encore désolé, c'est indépendant de ma volonté.

Bonjour,

@ amatheur :  "The Mathematical Gazette" trie 6 billes en 5 pesées maximum.
En reprenant avec la condition Bibmath post #1 de freddy, je n'arrive pas à trier 6 billes en moins de 6 pesées
(contrôle exhaustif final fait sur les 6!=720 permutations initiales possibles).
Par contre 9 pesées suffisent effectivement pour trier 9 billes. !