Forum de mathématiques - Bibm@th.net

camille23

Invité

Ordonner 15 billes pesées 3 par 3

Bonjour,
J'ai vu un problème traité dans "The Mathematical Gazette" sous la référence :
https://www.dropbox.com/s/gjyvq2d7pub3vah/15billes.pdf 
Ce document examine le classement ordonné de 15 billes avec aussi peu de pesées que possible, et aux conditions de pesées suivantes (texte original en anglais !) :
" 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.
Traduction :"La balance indique alors laquelle des trois billes est la plus lourde, la plus légère, et en conséquence celle de poids intermédiaire"

Il y a en fin de ce document trois références que j'ai consultées :
BibM@ths, Enigmes, casse-têtes, curiosités et autres bizarreries, accessed December 2013, available at http://www.bibmath.net/forums/viewtopic.php?id=5141

Extrait : Par freddy post #1
" j'ai 15 boules parfaitement identiques, indiscernables ni au toucher, ni à la "soupesée". Elles sont toutes d'un poids distinct.
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 "

Cette pesée se fait sous condition quelque peu différente et plus stricte que dans le document en anglais ci-avant. Dans BibMaths on ne connaît pas pour chacune des 3 boules rendues classées quel était l'emplacement d'origine parmi les trois emplacements. Ce que confirme freddy (qui a posé le problème) :

Par freddy post #65
" …quand je donne au quidam trois boules à trier, il me les rend dans l'ordre, mais je ne sais plus dire où était mon pivot puisque le quidam ne me donne aucune autre indication que les trois boules ordonnées ..."

Dans le document en anglais ci-avant il est dit que la balance qui a trois plateaux indique quels sont les poids relatifs des billes posées sur chaque plateau.
Sans avoir vraiment repris les interventions faites sous BibMaths, c'est bien sous cette dernière condition de pesée que freddy donne une solution (en 23 pesées) au post #99, solution qui ne correspond donc pas au problème posé au post #1.
La solution donnée par freddy (post #65) est identique à celle donnée par "The Mathematical Gazette" sous la référence :
Toppuzzle.eu, Enigmes: ordonner les 15 boules, accessed December 2013, available at http://toppuzzle.eu/enigmes-tres-difficiles.html

Le problème posé dans BibMath au post #1ne semble pas connaître, à ce jour, de solution avec moins de 26 pesées.

Il existe un algorithme qui permet, en temps très court (quelques secondes), de traiter sur ordinateur familial le problème posé dans BibMath par freddy, en suivant, peseés après pesées, les positions possibles des 15 billes ; sans explorer les 1 307 674 368 000 permutations des 15 billes.

amatheur²

Invité

Re : Ordonner 15 billes pesées 3 par 3

salut
Vieux sujet, et une nouvelle solution, j'en suis à la moitie du papier, et l'approche est à la fois simple et très intéressante...
@ suivre!

camille23

Invité

Re : Ordonner 15 billes pesées 3 par 3

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. !

amatheur²

Invité

Re : Ordonner 15 billes pesées 3 par 3

salut
A vrai dire, je crois qu'à l'époque, j'avais traité le problème exactement comme il est traité dans le papier que tu nous a présenté...
je crois qu'il faut attendre freddy pour qu'il te donne plus de précisions.
@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Ordonner 15 billes pesées 3 par 3

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é.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Ordonner 15 billes pesées 3 par 3

Salut,

j'ai pris connaissance de ton message. Le premier lien HTML est inaccessible. De fait, je ne comprends pas les objections que tu soulèves.
Si tu veux donc m'en dire plus, à toi d'être plus explicite. Pour moi, 23 "pesées" est un maximum, c'est prouvé.

camille23

Invité

Re : Ordonner 15 billes pesées 3 par 3

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 !

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Ordonner 15 billes pesées 3 par 3

Salut,

OK, trouvé.

Je lis : "Armed with this corollary, we can do better than 25 weighings to sort 15 marbles. Use the corollary twice to form a -chain containing nine marbles. This requires 8 weighings. Next, use the scale twice more to form two chains of length three with the 6 remaining marbles. Theorem 1 ensures that 13 more weighings suffice, for a total of 23."
QED.
Quel est le problème ?

Dernière modification par freddy (01-06-2015 11:21:15)

Camille23

Invité

Re : Ordonner 15 billes pesées 3 par 3

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.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Ordonner 15 billes pesées 3 par 3

Re,

Si vous ne le faites pas, c'est que vous esquivez une réponse franche au post #1 ci-avant.

Je ne sais pas comment freddy va le prendre, mais perso, je sais bien comment je percevrais le verbe "esquivez" : accusation de malhonnêteté intellectuelle sous-jacente...
Si c'est ça, c'est pô bien !

Il existe un algorithme qui permet, en temps très court (quelques secondes)

Et il est où cet algorithme que le traduise en Python ?

@+

    Yoshi
- Modérateur -

camille23

Invité

Re : Ordonner 15 billes pesées 3 par 3

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.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Ordonner 15 billes pesées 3 par 3

Salut yoshi,

je n'ai pas l'énergie nécessaire pour entrer dans la polémique. Le sujet que j'ai posé concernait 15 billes, je ne suis pas en mesure d'entrer dans plus de détails. Je ne comprends même pas pourquoi notre ami me pousse dans les cordes, je ne me sens pas aujourd'hui concerné par son problème.
Je n'esquive pas, je me repose. On regardera plus tard, quand je pourrai.

Camille23

Invité

Re : Ordonner 15 billes pesées 3 par 3

Salut à tous,

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

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Ordonner 15 billes pesées 3 par 3

Re,

fais contre mauvaise fortune bon cœur. Yoshi est le modérateur et le grand spécialiste du niveau secondaire ; Fred est l'administrateur et patron du site et grand spécialiste du niveau supérieur.
Moi, je ne suis qu'un modeste intervenant, comme quelques autres. Il se trouve que je sors d'une affection de longue durée qui m'a mis bien à plat. Je le suis encore un peu (beaucoup), donc sois patient, yoshi te confirmera que ma devise est "never an inch".

See you later

camille23

Invité

Re : Ordonner 15 billes pesées 3 par 3

Salut à tous, même peu nombreux,

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

Et il est où cet algorithme que le traduise en Python ?

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.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Ordonner 15 billes pesées 3 par 3

Salut,

J'ai peu de temps en ce moment (revue trimestrielle à boucler et je suis déjà en retard)...

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

En Python, avec les données de freddy, ça donnerait
N=15
for i in range (2**N):
    Créer une suite S formée des 0 et des (1 remplacés par N+1)

Là, je bloque...
Donc beaucoup beaucoup de questions...

Une suite ? Tu veux dire une liste ?
Une liste pour chaque nombre, pour chacun des 32768 nombres de 0 à 32767 ? Soit 32768 listes différentes ? fichtre... ça fait beaucoup !
Au départ chaque liste est initialisée comment ? avec combien d'éléments 0 et 1 ? Et tu remplaces chaque 1 (ou lesquels ?)  par 16 en fonction de quel(s) critère(s) ? Pourquoi 16 ?

Compter les 0, ça c'est facile :
k=S.count(0)

Dans chacun des emplacements de S insérer k
Je suppose que S contient n éléments (n= ? question posée ci-dessus) :
Je remplace S par une liste contenant n nombres k :
S=[k]*n
Dans quel but ?
D'autre part, pourquoi modifier la liste ainsi ?

Bref, je ne suis dans l'incapacité de traduire ton algo en Python : trop de non-dits...

Peu importe avec quel langage tu as écris ton algo, publie-le  et avec le code et le nom du langage, ce sera bien le diable si je n'arrive pas à l'adapter en Python ; ou alors, écris-le en pseudo-code complet avec commentaires.

Avec mes regrets et excuses si tu trouves que j'ai le cerveau lent (heureusement, très peu de vent chez moi...).

@+

Dernière modification par yoshi (06-06-2015 12:49:11)

camille23

Invité

Re : Ordonner 15 billes pesées 3 par 3

Bonjour,

En Python, avec les données de freddy, ça donnerait
N=15
for i in range (2**N):
    Créer une suite S formée des 0 et des (1 remplacés par N+1)

Là, je bloque...posée ci-dessus) :
@+

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

N=6
for i in range(2**(N-1)):
    s=[] #pour créer une suite formée de 0 et de (N+1)
    a=i
    for j in range(N-1):
        if a % 2 == 1:s.append(N+1)
        else:s.append(0)
        a//=2  #décalage à droite d'un bit
    print(i,s,s.count(0)+1)

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é.